Let’s pretend we’re working on a computer vision project. In this project, librarians sent us videos of their bookshelves. Based on frames from these videos, we want to quickly and efficiently find the spine tags on the books. For the purpose of the interview, we will be simplifying this to the following problem:
Given an m x n binary matrix, find the largest square containing only 1s and return its area.
Example:
Input matrix:
0000000000000000
0000000000000000
0000000000000000
0000001111100000
0000001111100000
0000001111100000
0000001111100000
0000001111100000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000This is a classic dynamic programming problem on a binary matrix. For each cell, compute the side length of the largest square of 1s that ends at that cell using the minimum of its top, left, and top-left neighbors plus one. Track the maximum side length across the matrix, then return its square as the area. It is a common OA/interview question that tests how well you model a 2D DP state.
