Largest Plus Sign

Largest Plus Sign

1. What is this problem about?

The Largest Plus Sign coding problem involves a grid that contains some "mines" (0s) and mostly empty spaces (1s). You are asked to find the order of the largest axis-aligned plus sign of 1s. The "order" of a plus sign is the distance from the center to any of its four ends (inclusive of the center). A plus sign of order k has a total of 4k - 3 ones arranged in a cross shape.

2. Why is this asked in interviews?

Uber and Twitter use this problem to test a candidate's proficiency with Dynamic Programming and grid-based optimizations. It requires you to precompute values for each cell to avoid redundant counting. It's a great test of whether you can break down a geometric search into four independent directions (Up, Down, Left, Right) and then synthesize those results to find the final answer.

3. Algorithmic pattern used

This problem follows the Array and Dynamic Programming interview pattern. For every cell (r, c) in the grid, we want to know the maximum number of consecutive 1s extending in each of the four directions. We can use four 2D arrays (or a single optimized one) to store these counts. The maximum order for a cell (r, c) is the minimum of its four directional counts. The answer is the maximum of these orders across the entire grid.

4. Example explanation

Imagine a 5x5 grid of all 1s except a mine at (2, 2). For cell (3, 3):

• Continuous 1s to the Left: 4 (cells (3,0) to (3,3))
• Continuous 1s to the Right: 2 (cells (3,3) to (3,4))
• Continuous 1s to the Up: 4 (cells (0,3) to (3,3))
• Continuous 1s to the Down: 2 (cells (3,3) to (4,3)) The order for (3, 3) is min(4, 2, 4, 2) = 2. This means at (3, 3) we can form a plus sign of order 2.

5. Common mistakes candidates make

A common pitfall is using a brute-force approach that checks all four directions for every single cell, leading to O(N³) or O(N⁴) complexity. Another mistake is incorrect boundary handling when precomputing the directional sums. Candidates also sometimes struggle with space optimization, not realizing they can often solve this using a single 2D array to track the running minimum.

6. Interview preparation tip

In "Array, Dynamic Programming interview pattern" grid problems, try to identify if the "optimal" property for a cell depends on its neighbors. Here, the "Left" count of a cell is just 1 + Left count of the previous cell. Recognizing these recursive relationships is the key to designing an efficient DP solution.