💻 Largest Square of 1s in Binary Matrix with DP

Discover dynamic programming to find the maximal square of land in a watery matrix — input your grid and uncover the largest island square!

🗺️ The Land Surveyor's Quest

🎯 The Challenge:

You are given a binary matrix representing a piece of land, where each cell contains either a 1 (land) or a 0 (water). Your task is to identify the largest square sub-matrix that contains only 1s, and print the coordinates of its top-left cell along with the size of the square.

📋 Problem:

Write a program in C++ that reads a matrix from input, processes it using dynamic programming, and finds the largest square region fully composed of land (1s). If there are multiple squares of the same maximum size, print the one that appears first in top-to-bottom, left-to-right order.

Problem Specifications

  • Input: First line: two integers R and C (1 ≤ R, C ≤ 1000). Next R lines: C space-separated 0s or 1s.
  • Output: Three integers: row index, column index (0-based) of top-left corner, and size of the square.

Example: Input 1

3 3
1 1 1
1 1 1
1 1 1

Output: 0 0 3

Example: Input 2

4 5
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
00000
01110
01110
00000

Output: 1 1 2

🔄 Dynamic Programming Strategy

Key Idea

  1. Create a DP table where dp[i][j] = size of largest square with bottom-right at (i,j).
  2. For boundaries: dp[i][0] = matrix[i][0], dp[0][j] = matrix[0][j].
  3. For others: if matrix[i][j] == 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1; else 0.
  4. Track max size and top-left position (scan top-to-bottom, left-to-right).

Note: Top-left of square is (i - size + 1, j - size + 1).

DP Table Fill

Time: O(R * C)

Brute Force

Check all squares: O(R^2 * C^2)

🔍 Step-by-Step DP Demo

Ready. Use controls below to start demo.

Original Matrix

DP Table State (size at bottom-right)

Current Max: 0 at top-left (0, 0)
Click Start to run demo

Progress Tracker

1. Initialize boundaries of DP table
2. Process cell (i,j) row-by-row
3. If matrix[i][j] == 0, dp[i][j] = 0
4. Else, dp[i][j] = min(above, left, diagonal) + 1
5. Update max size & top-left if improved
6. Repeat until table filled

🎮 Build Your Maximal Square Finder

Enter R, C, matrix and press Generate

Examples

Minimal Case
1x1 with 1 → 0 0 1
3x3 All 1s
→ 0 0 3

📊 Analysis & Optimization

Time

O(R * C)

Each cell processed in constant time.

Space

O(R * C)

For DP table; optimizable to O(C).

Optimization Ideas

  • Use 1D array for space optimization (update in-place).
  • Early exit if max size == min(R,C).
  • Fast I/O for large 1000x1000 inputs in C++.