How to Apply Sliding Window in 2D / Matrix Problems

You've mastered sliding window on 1D arrays. You can solve "longest substring" problems in your sleep. Then you see: "Find the maximum sum of a submatrix of size $k\times k$."

And suddenly, you're lost. Do you slide in both dimensions? How do you track state efficiently? Can you even use sliding window here?

The answer is yes, but with a twist. 2D sliding window requires rethinking the pattern—you can't just add another loop. In this guide, I'll show you how to extend sliding window to matrices without falling into the complexity traps.

You'll learn:

• Why 2D sliding window is fundamentally harder
• The most common 2D problem types you'll encounter
• The dimension compression technique that reduces 2D to 1D
• A generalized approach with working code
• Common pitfalls and how to avoid them

By the end, you'll handle matrix problems with confidence instead of panic.

TL;DR — 2D Sliding Window Essentials

• Never enumerate all rectangles: That's $O(R^2\cdot C^2)$ — too slow
• Core technique: Fix two row boundaries, compress columns to 1D array, apply 1D sliding window
• Fixed-size problems: Use 2D prefix sums for $O(1)$ queries after $O(R\cdot C)$ preprocessing
• Variable-size problems: Fix rows [r1, r2], compress columns, run Kadane's or 1D window
• Complexity: $O(R^2\cdot C)$ for most variable-size problems
• Common pitfall: Forgetting to reset col_sums when moving to new r1
• Prerequisites: Master 1D sliding window first (15-20 problems)

Why 2D Sliding Window is Harder

In 1D, sliding window is intuitive: expand right, shrink left, track a single range. In 2D, everything gets more complex.

Two Dimensions, Compressing One Dimension

The Challenge: In a 2D matrix, a "window" is now a rectangular region defined by:

• Top row and bottom row
• Left column and right column

That's four boundaries to manage instead of two. Naively, you might think:

# WRONG: Trying to slide in both dimensions simultaneously
for top in range(rows):
    for bottom in range(top, rows):
        for left in range(cols):
            for right in range(left, cols):
                # This is O(R^2 * C^2) - way too slow!

This brute force approach works, but it's $O(R^2\cdot C^2)$. For a $100\times 100$ matrix, that's 100 million operations—too slow for most interview constraints.

The Key Insight: You fix two boundaries (usually the rows) and apply 1D sliding window on the compressed columns.

Higher Complexity, Pointer Logic

Even with compression, you're dealing with:

• Nested loops for fixing boundaries
• Column-wise accumulation
• State management across row iterations

The conceptual leap from 1D to 2D is significant. But once you see the pattern, it becomes mechanical.

Typical Problem Types

Let's categorize the most common 2D sliding window problems.

Sum of Submatrix of Size k x k (Fixed Size)

Problem Type: Find the maximum sum of any $k\times k$ submatrix.

Example: Given a grid:

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

Find the max sum of a $2\times 2$ submatrix.

Approach: Use a true 2D sliding window:

1. Precompute prefix sums for $O(1)$ range queries
2. Slide the $k\times k$ window across the matrix

Complexity: $O(R\cdot C)$ preprocessing, $O(1)$ per query

Template:

def maxSumSubmatrix(matrix: List[List[int]], k: int) -> int:
    rows, cols = len(matrix), len(matrix[0])
    
    # Build 2D prefix sum
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            prefix[r][c] = (matrix[r-1][c-1] + 
                           prefix[r-1][c] + 
                           prefix[r][c-1] - 
                           prefix[r-1][c-1])
    
    max_sum = float('-inf')
    
    # Slide the k x k window
    for r in range(k, rows + 1):
        for c in range(k, cols + 1):
            # Sum of submatrix from (r-k, c-k) to (r-1, c-1)
            total = (prefix[r][c] - 
                    prefix[r-k][c] - 
                    prefix[r][c-k] + 
                    prefix[r-k][c-k])
            max_sum = max(max_sum, total)
    
    return max_sum

Variable Size: Maximum Submatrix Sum / Kadane's 2D Extension

Problem Type: Find the maximum sum of any submatrix (no size constraint).

Example: LeetCode 363 - Max Sum of Rectangle No Larger Than K

Approach: Fix top and bottom rows, compress columns into a 1D array, apply Kadane's algorithm (or 1D sliding window variant).

Complexity: $O(R^2\cdot C)$ or $O(R^2\cdot C\log C)$ with binary search

Other Variants

• Max rectangle of 1's: LeetCode 85 (Maximal Rectangle)
• Count subarrays with sum ≤ target: Use TreeMap for ordered sums
• Largest square of 1's: DP + sliding window hybrid

General Approach / Template

Here's the universal pattern for 2D sliding window with variable size.

Compress Rows → Turn into 1D Sliding Window

Core Idea:

1. Fix the top row (r1) and bottom row (r2)
2. Compress all rows between r1 and r2 into a single 1D array by summing each column
3. Apply 1D sliding window (or Kadane's, or prefix sum) on this compressed array

Visual Example:

Matrix:

 [1,  2, -1,  4]
 [3, -2,  2,  1]
 [2,  1,  3, -3]

Fix rows 0 to 1 (top two rows). Compress columns:

Column sums: [1+3, 2+(-2), -1+2, 4+1] = [4, 0, 1, 5]

Now solve the 1D problem: "Find max subarray sum in [4, 0, 1, 5]" → Answer: 10 (entire array)

Maintain Window Height + Width

For variable-size windows, you maintain:

• Height: The range [r1, r2] (fixed in each iteration)
• Width: The 1D sliding window on compressed columns

Code Snippet (Pseudo-code)

Maximum Sum Submatrix (Variable Size)

def maxSumSubmatrix(matrix: List[List[int]]) -> int:
    if not matrix:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')
    
    # Fix top row
    for r1 in range(rows):
        # Column sums for rows [r1, r2]
        col_sums = [0] * cols
        
        # Expand bottom row
        for r2 in range(r1, rows):
            # Add current row to column sums
            for c in range(cols):
                col_sums[c] += matrix[r2][c]
            
            # Now solve 1D problem: max subarray sum in col_sums
            # Using Kadane's algorithm
            current_sum = 0
            for val in col_sums:
                current_sum = max(val, current_sum + val)
                max_sum = max(max_sum, current_sum)
    
    return max_sum

Complexity Analysis:

• Outer loop (r1): $O(R)$
• Middle loop (r2): $O(R)$
• Inner loop (columns): $O(C)$
• Kadane's: $O(C)$

Total: $O(R^2\cdot C)$

When to Use: Most 2D sliding window problems with variable size. Make sure you understand 1D sliding window intuition before attempting 2D problems.

Advanced: Maximum Sum Rectangle No Larger Than K

This is LeetCode 363—the final boss of 2D sliding window.

Problem: Find the max sum of a submatrix where sum ≤ k.

Challenge: Kadane's doesn't work because you need to stay under a threshold.

Solution: Use an ordered set (TreeSet in Java, SortedList in Python) to track prefix sums.

from sortedcontainers import SortedList

def maxSumSubmatrix(matrix: List[List[int]], k: int) -> int:
    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')
    
    for r1 in range(rows):
        col_sums = [0] * cols
        
        for r2 in range(r1, rows):
            for c in range(cols):
                col_sums[c] += matrix[r2][c]
            
            # Find max subarray sum <= k in col_sums
            max_sum = max(max_sum, maxSubarraySumLessThanK(col_sums, k))
    
    return max_sum

def maxSubarraySumLessThanK(arr: List[int], k: int) -> int:
    prefix_sums = SortedList([0])
    current_sum = 0
    max_sum = float('-inf')
    
    for val in arr:
        current_sum += val
        
        # Find smallest prefix such that (current_sum - prefix) <= k
        # Which means prefix >= current_sum - k
        target = current_sum - k
        idx = prefix_sums.bisect_left(target)
        
        if idx < len(prefix_sums):
            max_sum = max(max_sum, current_sum - prefix_sums[idx])
        
        prefix_sums.add(current_sum)
    
    return max_sum

Complexity: $O(R^2\cdot C\log C)$

Why It Works: The TreeSet maintains sorted prefix sums, allowing binary search for the best split point.

Common Pitfalls & Tips

Forgetting to Reset State on Row Shift

The Mistake: When you move from r2 = 1 to r2 = 2, you forget to reset col_sums for the new r1.

Example:

# WRONG
col_sums = [0] * cols  # Should be inside r1 loop!
for r1 in range(rows):
    for r2 in range(r1, rows):
        # col_sums carries stale data from previous r1

The Fix: Initialize col_sums inside the r1 loop:

for r1 in range(rows):
    col_sums = [0] * cols  # CORRECT: Fresh for each r1
    for r2 in range(r1, rows):
        # ...

Off-by-One Boundaries in 2D

The Mistake: Confusing inclusive vs exclusive boundaries.

When using prefix sums:

• prefix[r][c] represents sum from (0, 0) to (r - 1, c - 1) (exclusive indexing)
• To get sum of submatrix (r1, c1) to (r2, c2) (inclusive):

  total = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

  python

Tip: Draw a small 3×3 matrix and manually trace indices to verify.

Using Kadane's When You Need Bounded Sums

The Mistake: Applying Kadane's algorithm when the problem asks for "sum ≤ k" or "sum closest to k."

Kadane's finds the maximum sum subarray, not the maximum under a constraint.

The Fix: Use the TreeSet/SortedList approach shown above.

Example: Debugging a Failed Case

Problem: Your code works on small matrices but fails on:

[[ 5, -4,  -3,   4],
 [-3, -4,   4,   5],
 [ 5,  1,   5,  -4]]

Debug Steps:

1. Print col_sums for each (r1, r2) pair
2. Verify the 1D solution is correct for those compressed arrays
3. Check if col_sums is being reset properly
4. Manually compute the expected answer for one submatrix

Common Issue: col_sums not reset, causing sums to accumulate across different r1 values.

Takeaways & Practice Plan

Key Principles

1. Never enumerate all rectangles: That's $O(R^2\cdot C^2)$. Always compress.
2. Fix two boundaries, slide the other dimension: Usually fix rows, slide columns.
3. Reset state carefully: Initialize fresh arrays for each outer loop iteration.
4. Use prefix sums for fixed-size: $O(1)$ sum queries after $O(R\cdot C)$ preprocessing.
5. Use compression + 1D for variable-size: Reduces to a problem you already know.

Practice Plan

Week 1: Fixed-Size Windows

• Implement 2D prefix sums from scratch
• Solve: "Max sum of $k\times k$ submatrix"
• Verify correctness on $3\times 3$ and $100\times 100$ matrices

Week 2: Variable-Size with Kadane's

• Learn Kadane's algorithm if you haven't
• Solve: "Maximum Sum Submatrix" (no constraints)
• Practice: LeetCode 85 (Maximal Rectangle)

Week 3: Advanced Constraints

• Implement TreeSet-based bounded sum solution
• Solve: LeetCode 363 (Max Sum Rectangle No Larger Than K)
• Understand why TreeSet is $O(\log C)$ per operation

Daily Practice: 1 problem every 2 days. 2D problems require deeper understanding than 1D—don't rush.

Important: Only attempt 2D problems after mastering 1D. See our top sliding window problems list for a structured progression.

Related Patterns to Study

• 1D Kadane's Algorithm: Foundation for max subarray
• Prefix Sums: Essential for range queries
• Sliding Window Template: 1D foundation
• Monotonic Deque: For "max in every window" problems

FAQ

Q: Is 2D sliding window actually common in interviews?
A: Less common than 1D, but it appears in senior-level interviews at top companies. If you're targeting Google, Meta, or competitive programming, you should know it.

Q: Can I use the same template for all 2D problems?
A: The compression approach (fix rows, slide columns) works for 90% of problems. Fixed-size problems are easier with 2D prefix sums.

Q: What if the matrix is very large ($10^4\times 10^4$)?
A: $O(R^2\cdot C)$ might be too slow. Look for problem-specific optimizations (e.g., sparse matrices, monotonic properties) or alternative approaches.

Q: Do I need to memorize the prefix sum formula?
A: Yes. The formula prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1] is worth memorizing. Or use the principle of inclusion-exclusion to derive it.

Q: What's the difference between DP and 2D sliding window?
A: They can overlap. Some DP problems (like "Maximal Rectangle") use sliding window as a subroutine. DP is about optimal substructure; sliding window is about maintaining a range efficiently.

Q: Should I practice 2D problems if I'm a beginner?
A: No. Master 1D sliding window first. Solve at least 15-20 1D problems before attempting 2D. The jump is significant.

Q: How do I know if a matrix problem is sliding window vs DP?
A: If you're optimizing a contiguous rectangular region (e.g., "max sum submatrix"), think sliding window. If you're building solutions from smaller subproblems (e.g., "unique paths"), think DP.