💻 Maximum Square Sub-Matrix of 1s with DP

Explore dynamic programming to uncover the largest square island of land in a binary sea — visualize and extract the maximal all-1s square!

🗺️ The Island Mapper's Challenge

🎯 The Challenge:

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

📋 Problem:

Read the matrix, use DP to locate the largest square of 1s, and print the sub-matrix itself (its rows with space-separated values).

Problem Specifications

  • Input: First line: R C (1 ≤ R, C ≤ 1000). Next R lines: C space-separated 0s/1s.
  • Output: The rows of the maximal square sub-matrix, space-separated, one row per line.

Example: Input 1

6 5
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1 1 1 1 1

🔄 Dynamic Programming Strategy

Key Idea

  1. DP[i][j] = side length of largest square with bottom-right at (i,j).
  2. Boundaries: DP[i][0] = matrix[i][0], DP[0][j] = matrix[0][j].
  3. Inner: 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 length and position; extract sub-matrix from top-left (i-max+1, j-max+1).

Note: Print only the square's rows/columns, in order.

DP Table Fill

Time: O(R * C)

Brute Force

O(R^2 * C^2) — too slow for 1000x1000

🔍 Step-by-Step DP Demo

Ready. Use controls below to start demo.

Original Matrix

DP Table State (side lengths)

Max square will appear here after completion

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. Track max length & position
6. Extract & print sub-matrix

🎮 Build Your Square Extractor

Enter R, C, matrix and press Generate

Examples

Sample 1 (6x5)
→ 3x3 square printed
Sample 2 (6x5 extended)
→ Still 3x3 (first occurrence)

📊 Analysis & Optimization

Time

O(R * C)

Single pass over matrix for DP.

Space

O(R * C)

DP table; O(min(R,C)) possible with rolling array.

Optimization Ideas

  • 1D DP for space savings on large grids.
  • Track only max during fill, no full table if memory tight.
  • Fast input parsing for 1000x1000 in languages like C++.