Why it works
- Every quarter is the same problem on a square half as wide, and a single cell is always a leaf: the recursion always reaches an answer.
- A square is all one value exactly when its four quarters are all leaves with that value, so checking the four children is enough: no cell is looked at twice.
- A quarter that holds both values comes back as a node, and then its parent has to stay a node too.
Complexity
Time O(n²): each cell becomes a leaf once, and each larger square only compares its four children. Memory O(log n) besides the tree: the call stack is as deep as the number of halvings.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗