Lecture 57: How Do Stacks Solve the Celebrity Problem and Maximum Rectangle in a Binary Matrix?

TL;DR

Solve the celebrity problem in O(n) by using a stack to eliminate non-candidates, then verify that the survivor knows nobody and is known by everyone else. For the maximum all-ones rectangle, accumulate consecutive ones as histogram heights for each matrix row, resetting a height when a zero appears, and calculate the largest histogram rectangle after every update. Read on for the elimination, verification, and histogram steps.

Transcript

Hello ji , how are you all? this is Love Babbar And welcome to the channel Code help , we have reached lecture no-57 , here we are going to do two good questions These are famous questions , asked in interviews , somewhere it is marked hard , here it is marked medium Don,t worry about that , logic will be same 1. Celebrity problem Celebrity is a p... Read More

Key Insights

• The celebrity condition is defined by two facts: the celebrity knows nobody at the party, and every other person knows the celebrity. In the relationship matrix, the candidate’s row must contain zeros, while the candidate’s column must contain ones except at the diagonal position.
• The diagonal of the relationship matrix is ignored conceptually because entries such as whether person 0 knows person 0 do not help determine celebrity status. Verification therefore expects an all-zero candidate row and exactly n-1 ones in the candidate column.
• The brute-force celebrity approach is O(n^2) because it considers each of the n people and checks that person’s row and column. Although each individual row or column scan is O(n), repeating those scans for every possible candidate produces quadratic work.
• Stack elimination works by comparing two people at a time. If person a knows person b, then a cannot be the celebrity, so b remains under consideration. Otherwise, b is discarded and a remains, reducing the candidate set by one during every comparison.
• The final stack element is only a potential celebrity, not a guaranteed answer. Its complete row must be checked for n zeros, and its column must be checked for n-1 ones. If either condition fails, the correct result is -1.
• The stack-based celebrity algorithm runs in O(n) time because pushing the people, eliminating candidates, checking the remaining row, and checking the remaining column each require linear work. These linear stages add together without creating a nested scan over all candidates.
• The maximum all-ones rectangle problem becomes a histogram problem when each matrix row is treated as a base. Consecutive vertical ones contribute to column heights, allowing every rectangle ending at the current row to be evaluated with the largest-rectangle-in-a-histogram logic.
• A zero resets its column’s accumulated histogram height because an all-ones rectangle cannot extend vertically through that position. After updating the heights for each row, the largest histogram area is calculated, and the maximum across all processed rows becomes the answer.

Questions & Answers

Q: What is the celebrity problem in a binary matrix?

The problem asks whether one person among n people is known by everyone else but knows nobody. A matrix value of 1 means one person knows another. A celebrity’s row contains only zeros, while the celebrity’s column contains ones for every other person.

Q: How do you solve the celebrity problem using a stack?

Push every person’s index onto a stack, then repeatedly pop two people, a and b. If a knows b, discard a and push b back; otherwise, discard b and push a back. When one index remains, verify that person’s complete row and column.

Q: Why can one person be eliminated after each celebrity comparison?

If a knows b, then a cannot be the celebrity because a celebrity knows nobody. If a does not know b, then b cannot be the celebrity because everyone must know the celebrity. Therefore, each comparison safely removes one candidate.

Q: How do you verify the final celebrity candidate?

Check that every entry in the candidate’s row is zero, confirming that the candidate knows nobody. Then check that the candidate’s column contains n-1 ones, excluding the diagonal entry. Return the candidate only if both conditions hold; otherwise, return -1.

Q: What is the time complexity of the celebrity solutions?

The brute-force method takes O(n^2) time because it checks the row and column of every possible candidate. The stack method takes O(n) time because candidate elimination and the final row-and-column verification each require linear work.

Q: How is the maximum rectangle in a binary matrix reduced to a histogram problem?

Treat each matrix row as the base of a histogram whose heights represent consecutive vertical ones. Add to a column’s previous height when its current cell is 1, then apply the largest-rectangle-in-a-histogram method to the updated heights. Repeat this for every row.

Q: Why do histogram heights reset when a binary matrix cell is zero?

A zero breaks the vertical sequence of ones in its column. Because the rectangle must contain only ones, it cannot extend through that cell. The corresponding histogram height must therefore reset to zero.

Q: How is the maximum all-ones rectangle area found across the matrix?

Calculate the largest histogram rectangle for the initial row. For every later row, accumulate heights where ones continue and reset heights where zeros appear, then calculate the largest histogram rectangle again. The greatest area found across all rows is the maximum all-ones rectangle.

Summary & Key Takeaways

• The celebrity problem uses a binary relationship matrix in which a value of 1 means one person knows another. A celebrity must have a row containing only zeros and a column containing ones for every other person. The diagonal is treated separately because whether a person knows themselves is irrelevant.

• The brute-force celebrity solution checks every person’s complete row and column, producing O(n^2) time. The stack solution repeatedly compares two people and discards one who cannot be the celebrity. When one potential candidate remains, scanning that person’s row and column verifies whether both celebrity conditions actually hold.

• The maximum rectangle problem is reduced to repeated largest-rectangle-in-a-histogram calculations. Each matrix row becomes a histogram base. Heights accumulate where ones continue vertically, while a zero resets its height. Computing the largest histogram rectangle after each row and retaining the greatest result reveals the maximum rectangle containing only ones.