I am going through one problem, https://leetcode.com/problems/maximal-square/
In this problem, we need to find the largest square of matrix having 1 only.
So my thinking approach like:
- Came with brute force like going each grid point, if its 1 then check the largest square we can form starting from this corner.
- Directly, I jump over to solve it using line sweep algorithm. Never came up with the solution though but I think it can be made.
When I looked into the solution tab, its solved using dynamic programming. I couldn’t have thought using DP(unless looking at solution). It its time complexity is also very efficient(efficient over linesweep)
So my question is, how one should approach this problem. Like what would have been clicked in your mind when you are looking this problem and dynamic programming approach strike.