LeetCode 3643 - Flip Square Submatrix Vertically

This problem gives us an m x n matrix called grid and three integers: x, y, and k. The values x and y specify the top-left corner of a square submatrix, while k specifies the side length of that square.

leetcodeeasyarraytwo-pointersmatrix

LeetCode Problem 3643

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Matrix

Solution

LeetCode 3643 - Flip Square Submatrix Vertically

Problem Understanding

This problem gives us an m x n matrix called grid and three integers: x, y, and k.

The values x and y specify the top-left corner of a square submatrix, while k specifies the side length of that square. Therefore, the submatrix occupies:

Problem Understanding

We are given an m × n matrix grid and three integers x, y, and k.

The values x and y specify the top-left corner of a square submatrix, and k specifies the side length of that square. Therefore, the submatrix occupies:

  • Rows x through x + k - 1
  • Columns y through y + k - 1

The task is to flip this square submatrix vertically. A vertical flip means reversing the order of its rows while keeping the contents of each row in the same column positions.

For example, if the selected square contains: The task is to flip this square submatrix vertically. A vertical flip means reversing the order of the rows inside the square while keeping the contents of each row in the same column positions.

For example, if the selected square contains rows:

Row A
Row B
Row C

After the vertical flip it becomes: after the vertical flip it becomes:

Row C
Row B
Row A

Only the cells inside the selected square are modified. Everything outside the square remains unchanged.

The output should be the modified matrix after performing this operation.

The constraints are quite small:

  • m, n ≤ 50
  • The square size k is at most 50

This tells us that even relatively straightforward approaches will run comfortably within the limits. We do not need sophisticated data structures or advanced optimization techniques.

Several edge cases are worth noting:

  • k = 1, meaning the square consists of a single cell. Flipping it changes nothing.
  • The square may touch the bottom or right boundary of the matrix.
  • The square may cover the entire matrix.
  • The square may have an odd size, meaning the middle row remains in place after the flip.
  • The problem guarantees the square is valid, so we never need to check for out-of-bounds access.

Approaches

Brute Force Approach

A straightforward solution is to create a completely new copy of the matrix.

For every cell inside the selected square, we determine where its vertically flipped counterpart should come from. Specifically, row x + i should receive values from row x + (k - 1 - i).

We copy all values into a new matrix and return it.

This approach is correct because every cell in the square is explicitly reassigned according to the vertical flip definition. However, it requires allocating an entire duplicate matrix even though only part of the matrix changes.

Optimal Approach

The key observation is that a vertical flip simply swaps rows within the selected square.

The first row of the square swaps with the last row, the second row swaps with the second-last row, and so on.

Since only the columns inside the square should be affected, we swap only those k columns rather than entire matrix rows.

Using a two-pointer approach:

  • One pointer starts at the top row of the square.
  • One pointer starts at the bottom row of the square.
  • Swap corresponding cells within the square columns.
  • Move the pointers toward each other.

This performs the transformation directly in the original matrix without needing an extra matrix.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force O(mn) O(mn) Creates a full copy of the matrix
Optimal O(k²) O(1) Swaps rows inside the square in place

Algorithm Walkthrough

Optimal Algorithm

  1. Identify the top row of the square as top = x and the bottom row as bottom = x + k - 1.
  2. While top < bottom, swap the corresponding rows of the square.
  3. For each column inside the square, from y to y + k - 1, swap:
  • grid[top][col]
  • grid[bottom][col]

This exchanges the selected portion of the two rows while leaving cells outside the square unchanged. 4. After finishing all column swaps for the current row pair:

  • Increment top
  • Decrement bottom
  1. Continue until the pointers meet or cross.
  2. Return the modified matrix.

Why it works

A vertical flip reverses the order of rows inside the square. The algorithm directly performs that reversal by swapping the first row with the last row, the second row with the second-last row, and so on. Every row moves exactly to its flipped position, and only columns belonging to the square are modified. Therefore the resulting square is exactly the vertically flipped version of the original square, while all other matrix cells remain unchanged. Only the cells inside the selected square are affected. All cells outside the square remain unchanged.

The constraints are very small. Both dimensions are at most 50, so even solutions that touch every element of the square are easily fast enough. The problem guarantees that the square is valid:

1 <= k <= min(m - x, n - y)

Therefore, the square always fits completely inside the matrix and no boundary checking beyond the given indices is necessary.

Important edge cases include a square of size 1, where no changes should occur, a square that spans the entire matrix, and squares with an odd number of rows where the middle row remains in place after the reversal.

Approaches

Brute Force

A straightforward solution is to create a temporary copy of the entire k × k submatrix. After copying, write the rows back into the original matrix in reversed order.

This approach is correct because each row of the square is explicitly placed into its vertically flipped position. However, it requires additional memory proportional to the size of the square.

Since the constraints are small, this solution is acceptable, but it uses unnecessary extra space.

Optimal Approach

The key observation is that a vertical flip is simply a reversal of the rows inside the square.

To reverse rows, we only need to swap:

  • First row with last row
  • Second row with second-last row
  • And so on

Because only the square portion should be modified, each swap is performed only across the columns belonging to the square.

Specifically, for each pair of corresponding rows inside the square, we swap the entries in columns y through y + k - 1.

This performs the reversal in place and requires only constant extra memory.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k²) O(k²) Copy the entire square, then write rows back in reverse order
Optimal O(k²) O(1) Swap corresponding rows of the square in place

Algorithm Walkthrough

  1. Identify the row range of the square, which is from x to x + k - 1.
  2. Use two pointers:
  • top = x
  • bottom = x + k - 1

These pointers represent the pair of rows that should be exchanged. 3. While top < bottom, swap the square portions of those two rows. 4. To swap only the selected square, iterate through columns from y to y + k - 1. 5. For each column inside the square, exchange:

grid[top][col]
grid[bottom][col]
  1. After finishing the row swap, increment top and decrement bottom.
  2. Continue until all row pairs have been processed.
  3. Return the modified matrix.

Why it works

A vertical flip of a square submatrix is exactly the reversal of its row order. The algorithm swaps the first and last rows of the square, then the second and second-last rows, and continues inward. This is precisely the standard in-place row-reversal operation. Since every cell inside the square is moved to the row it occupies after the reversal and no cells outside the square are modified, the resulting matrix is exactly the desired vertical flip.

Python Solution

from typing import List

class Solution:
    def reverseSubmatrix(
        self,
        grid: List[List[int]],
        x: int,
        y: int,
        k: int
    ) -> List[List[int]]:
        top = x
        bottom = x + k - 1

        while top < bottom:
            for col in range(y, y + k):
                grid[top][col], grid[bottom][col] = (
                    grid[bottom][col],
                    grid[top][col]
                )

            top += 1
            bottom -= 1

        return grid

The implementation follows the algorithm directly.

The variables top and bottom represent the current pair of rows that need to be swapped. For every such pair, we iterate through the square's columns and exchange the corresponding values.

Notice that we only swap columns from y through y + k - 1. This is important because the flip should affect only the selected square, not the entire rows of the matrix.

After processing one pair of rows, the pointers move inward until all necessary swaps are completed. The modified matrix is then returned. The implementation follows the algorithm directly. Two pointers, top and bottom, track the rows that must be exchanged. For each pair of rows, only the columns belonging to the square are visited. The swap is performed in place using Python's tuple assignment syntax. After each row pair is processed, the pointers move inward until all necessary swaps have been completed. The modified matrix is then returned.

Go Solution

func reverseSubmatrix(grid [][]int, x int, y int, k int) [][]int {
	top := x
	bottom := x + k - 1

	for top < bottom {
		for col := y; col < y+k; col++ {
			grid[top][col], grid[bottom][col] =
				grid[bottom][col], grid[top][col]
		}

		top++
		bottom--
	}

	return grid
}

The Go implementation is nearly identical to the Python version.

The matrix is represented as a slice of slices. Since slices provide reference-like behavior, modifying grid directly updates the original matrix in place. No additional memory allocation is required. Integer overflow is not a concern because all indices are bounded by the small constraints. The Go implementation mirrors the Python solution. Since slices are reference-like structures, modifications to grid occur in place. No additional memory proportional to the square size is allocated. Integer overflow is not a concern because all indices are bounded by the problem constraints.

Worked Examples

Example 1

Input:

grid =
[
 [1, 2, 3, 4],
 [5, 6, 7, 8],
 [9,10,11,12],
 [13,14,15,16]
]

x = 1
y = 0
k = 3

Selected square:

[5, 6, 7]
[9,10,11]
[13,14,15]
[
 [5, 6, 7],
 [9,10,11],
 [13,14,15]
]

Initial pointers:

top bottom
1 3

Swap columns 0..2:

Before After
row 1 = [5,6,7] row 1 = [13,14,15]
row 3 = [13,14,15] row 3 = [5,6,7]

Matrix becomes:

[
 [1,2,3,4],
 [13,14,15,8],
 [9,10,11,12],
 [5,6,7,16]
]

Swap rows 1 and 3 within columns 0..2.

Result:

Matrix State
[1,2,3,4]
[13,14,15,8]
[9,10,11,12]
[5,6,7,16]

Update pointers:

top bottom
2 2

Loop stops because top >= bottom. Loop terminates.

Output:

[
 [1,2,3,4],
 [13,14,15,8],
 [9,10,11,12],
 [5,6,7,16]
]

Example 2

Input:

grid =
[
 [3,4,2,3],
 [2,3,4,2]
]

x = 0
y = 2
k = 2

Selected square:

[2,3]
[4,2]
[
 [2,3],
 [4,2]
]

Initial pointers:

top bottom
0 1

Swap columns 2..3:

Position Before After
(0,2) ↔ (1,2) 2 ↔ 4 4 ↔ 2
(0,3) ↔ (1,3) 3 ↔ 2 2 ↔ 3

Matrix becomes:

[
 [3,4,4,2],
 [2,3,2,3]
]

Swap columns 2 and 3 between the two rows.

After swap:

Matrix State
[3,4,4,2]
[2,3,2,3]

Update pointers:

top bottom
1 0

Loop terminates.

Output:

[
 [3,4,4,2],
 [2,3,2,3]
]

Complexity Analysis

Measure Complexity Explanation
Time O(k²) We swap approximately k/2 row pairs, each involving k columns
Space O(1) All swaps are performed in place

The square contains exactly k² cells. Every cell in the square participates in at most one swap operation, so the total work is proportional to the area of the square. No auxiliary data structures are used, giving constant extra space usage.

Test Cases

from typing import List

s = Solution()

# Example 1
assert s.reverseSubmatrix(
    [
        [1,2,3,4],
        [5,6,7,8],
        [9,10,11,12],
        [13,14,15,16]
    ],
| Time | O(k²) | Roughly `k/2` row swaps, each touching `k` columns |
| Space | O(1) | Only a few index variables are used |

The algorithm processes each element of the selected square at most once. Since the square contains `k²` elements, the running time is `O(k²)`. All modifications are performed in place, so only constant auxiliary memory is required.

## Test Cases

sol = Solution()

Example 1

assert sol.reverseSubmatrix( [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 1, 0, 3 ) == [ [1,2,3,4], [13,14,15,8], [9,10,11,12], [5,6,7,16] ]

Example 2

assert s.reverseSubmatrix( [ [3,4,2,3], [2,3,4,2] ], assert sol.reverseSubmatrix( [[3,4,2,3],[2,3,4,2]], 0, 2, 2 ) == [ [3,4,4,2], [2,3,2,3] ]

Single cell square, no change

assert s.reverseSubmatrix( [[5]], 0, 0, 1 ) == [[5]]

Entire matrix flipped

assert s.reverseSubmatrix( [ [1,2], [3,4] ],

k = 1, no change

assert sol.reverseSubmatrix( [[1,2],[3,4]], 0, 0, 1 ) == [ [1,2], [3,4] ]

Entire matrix selected

assert sol.reverseSubmatrix( [[1,2],[3,4]], 0, 0, 2 ) == [ [3,4], [1,2] ]

Odd-sized square, middle row remains unchanged

assert s.reverseSubmatrix(

Odd-sized square, middle row remains

assert sol.reverseSubmatrix( [ [1,2,3], [4,5,6], [7,8,9] ], 0, 0, 3 ) == [ [7,8,9], [4,5,6], [1,2,3] ]

Square at bottom-right corner

assert s.reverseSubmatrix( [ [1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16] ], 2, 2, 2 ) == [ [1,2,3,4], [5,6,7,8], [9,10,15,16], [13,14,11,12] ]

Single row affected inside larger matrix

assert s.reverseSubmatrix( [ [1,2,3], [4,5,6], [7,8,9] ], 1, 1, 1 ) == [ [1,2,3], [4,5,6], [7,8,9] ]

Square located in middle of matrix

assert sol.reverseSubmatrix( [ [1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20] ], 1, 1, 3 ) == [ [1,2,3,4,5], [6,17,18,19,10], [11,12,13,14,15], [16,7,8,9,20] ]

Single-row matrix with k = 1

assert sol.reverseSubmatrix( [[5,6,7]], 0, 1, 1 ) == [[5,6,7]]

Single-column matrix

assert sol.reverseSubmatrix( [[1],[2],[3],[4]], 1, 0, 2 ) == [[1],[3],[2],[4]]


### Test Summary

| Test | Why |
| --- | --- |
| Example 1 | Validates a 3×3 square inside a larger matrix |
| Example 2 | Validates a 2×2 square at the right edge |
| Single cell square | Verifies `k = 1` behavior |
| Entire matrix flipped | Tests square covering whole matrix |
| Odd-sized square | Ensures middle row remains unchanged |
| Bottom-right square | Tests boundary positioning |
| Another `k = 1` case | Confirms no-op behavior inside larger matrix |

## Edge Cases

### Square Size Equals One

When `k = 1`, the selected square contains only a single cell. A vertical flip has no visible effect because there is only one row. A common bug is performing unnecessary swaps or incorrectly adjusting pointers. In this implementation, `top` and `bottom` start equal, so the loop never executes and the matrix is returned unchanged.

### Odd-Sized Squares

For odd values of `k`, there is a middle row that should remain in the same position after the flip. For example, a 3×3 square swaps the first and last rows while leaving the middle row untouched. The condition `while top < bottom` naturally stops before the middle row is processed, which correctly preserves it.

### Square Touching Matrix Boundaries

The selected square may begin near the bottom or right edge of the matrix. A careless implementation might accidentally access columns or rows outside the matrix bounds. The problem guarantees that `k <= min(m - x, n - y)`, ensuring the square always fits. By iterating only through rows `x` to `x + k - 1` and columns `y` to `y + k - 1`, the implementation remains safely within bounds.

### Square Covering the Entire Matrix

When the square spans the entire matrix, every row participates in the reversal. The algorithm still behaves correctly because it is fundamentally reversing the order of rows within the selected region. Since the selected region is the whole matrix, the result becomes a complete vertical flip of the matrix.
| Example 1 | Validates the primary example |
| Example 2 | Validates a square not starting at column 0 |
| `k = 1` | Tests the smallest possible square |
| Entire matrix selected | Tests maximum square coverage |
| Odd-sized square | Ensures middle row remains unchanged |
| Interior square | Ensures only selected cells are modified |
| Single-row matrix | Boundary condition on rows |
| Single-column matrix | Boundary condition on columns |

## Edge Cases

### Square of Size 1

When `k = 1`, the square contains exactly one cell. A vertical reversal of a single row produces no change. This can be a source of bugs if code assumes at least one swap must occur. In the implementation, `top` and `bottom` are initially equal, so the loop condition `top < bottom` is false and the matrix is returned unchanged.

### Odd-Sized Square

For odd values of `k`, there is a middle row that should remain in place after the reversal. A buggy implementation might accidentally process this row twice. The two-pointer approach avoids this issue because the loop stops when `top == bottom`, leaving the middle row untouched.

### Square Not Covering Entire Rows

A common mistake is to swap entire matrix rows instead of only the square portion. Doing so would modify cells outside the selected submatrix. The implementation explicitly iterates only over columns `y` through `y + k - 1`, ensuring that cells outside the square remain unchanged.

### Square Touching Matrix Boundaries

The square may begin at the last valid position that still allows a size `k` square. Incorrect index calculations can produce out-of-bounds accesses. The problem guarantees that

k <= min(m - x, n - y)


so the ranges

x .. x + k - 1 y .. y + k - 1


are always valid, and the implementation safely accesses every required cell.