The problem
A railway yard is drawn as a grid: rows is a list of strings of the same length, where "." is a free cell and "#" is a cell with track on it. Return the side length of the largest square made only of free cells. The square’s sides run along the grid.
largest_square(["#..#.",
".....",
".#...",
".#..."]) # 3
largest_square(["##", "##"]) # 0
largest_square([]) # 0
Limits
- Up to 700 rows of 700 cells. Aim for one pass over the cells, a few steps each.
Builds on DYNP-5 Grids and 2-D DP.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
9 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | All track | Not run | |
| 3 | One free cell | Not run | |
| 4 | No rows | Not run | |
| 5 | One row | Not run | |
| 6 | A long strip is not a square | Not run | |
| 7 | In the bottom-right corner | Not run | |
| 8 | 700 × 700, all free | Not run | |
| 9 | 700 × 700 yard | Not run |