Problem Description

You are given a 2D integer matrix grid with dimensions m x n, along with three integers x, y, and k.

The parameters represent:

• x and y: The row and column indices of the top-left corner of a square submatrix within grid
• k: The size (side length) of the square submatrix

Your task is to flip the square submatrix vertically by reversing the order of its rows. This means:

• The first row of the submatrix becomes the last row
• The second row becomes the second-to-last row
• And so on, until all rows in the submatrix are reversed

For example, if you have a 3×3 submatrix:

1 2 3
4 5 6
7 8 9

After flipping vertically, it becomes:

7 8 9
4 5 6
1 2 3

The operation only affects the k × k submatrix starting at position (x, y). All other elements in the grid remain unchanged.

Return the modified matrix after performing the vertical flip operation on the specified submatrix.

Intuition

To flip a submatrix vertically, we need to reverse the order of its rows. Think of it like flipping a stack of cards - the top card goes to the bottom, the bottom card goes to the top, and the middle cards swap positions accordingly.

The key insight is that we don't need to process all k rows. We only need to swap pairs of rows that are equidistant from the center. The first row swaps with the last row, the second row swaps with the second-to-last row, and so on. This means we only need to iterate through half of the rows: k // 2.

For each row i that we process (starting from row x), we need to find its corresponding row to swap with. If i is the current row index, then its distance from the starting row x is (i - x). The corresponding row from the bottom would be at distance (i - x) from the last row of the submatrix. Since the last row of the submatrix is at index x + k - 1, the corresponding row index i2 can be calculated as: i2 = x + k - 1 - (i - x).

Once we identify the two rows to swap, we need to exchange all elements in those rows within the submatrix bounds. This means swapping elements from column y to column y + k - 1 between rows i and i2.

The beauty of this approach is that it modifies the matrix in-place without requiring extra space for a temporary matrix. By swapping rows pairwise, we achieve the vertical flip efficiently in O(k²) time, where we visit each element in the submatrix exactly once.

Learn more about Two Pointers patterns.

Solution Approach

The implementation follows a straightforward simulation approach to flip the submatrix vertically by swapping rows.

Step 1: Determine the rows to swap

We iterate from row x to row x + k // 2 - 1. This gives us exactly ⌊k/2⌋ rows to process. We use integer division k // 2 because:

• If k is even (e.g., 4), we swap 2 pairs of rows
• If k is odd (e.g., 5), we swap 2 pairs of rows, and the middle row stays in place

Step 2: Calculate the corresponding row index

For each row i in the range [x, x + k // 2), we calculate its mirror row i2:

i2 = x + k - 1 - (i - x)

This formula works because:

• (i - x) gives us the offset of row i from the start of the submatrix
• x + k - 1 is the index of the last row in the submatrix
• Subtracting the offset from the last row index gives us the corresponding row from the bottom

Step 3: Swap elements between the two rows

For each column j in the range [y, y + k), we swap the elements at positions grid[i][j] and grid[i2][j]:

grid[i][j], grid[i2][j] = grid[i2][j], grid[i][j]

This Python syntax performs the swap in a single line without needing a temporary variable.

Step 4: Return the modified matrix

After all swaps are complete, we return the modified grid. Since we're modifying the matrix in-place, the original matrix is directly updated.

Time Complexity: O(k²) - We visit each element in the k × k submatrix exactly once.

Space Complexity: O(1) - We only use a constant amount of extra space for loop variables and temporary swapping.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• A 4×4 grid:

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

• Parameters: x = 1, y = 1, k = 3

This means we need to flip a 3×3 submatrix starting at position (1,1).

Step 1: Identify the submatrix The 3×3 submatrix starting at (1,1) contains:

6  7  8
10 11 12
14 15 16

Step 2: Determine rows to swap Since k = 3, we need to process k // 2 = 3 // 2 = 1 row pair.

• We'll iterate with i from x = 1 to x + k//2 - 1 = 1 + 1 - 1 = 1
• So we only process row i = 1

Step 3: Calculate mirror row For i = 1:

• Calculate i2 = x + k - 1 - (i - x)
• i2 = 1 + 3 - 1 - (1 - 1) = 3
• So row 1 will swap with row 3

Step 4: Swap elements For columns j from y = 1 to y + k - 1 = 3:

• When j = 1: Swap grid[1][1] (6) with grid[3][1] (14)
• When j = 2: Swap grid[1][2] (7) with grid[3][2] (15)
• When j = 3: Swap grid[1][3] (8) with grid[3][3] (16)

After swapping row 1 with row 3:

1  2  3  4
14 15 16 8    (was: 5  6  7  8)
9  10 11 12   (middle row stays in place)
6  7  8  16   (was: 13 14 15 16)

Wait, let me recalculate - the columns should be from y to y + k - 1:

• Column range: from 1 to 3 (inclusive)

Correcting the swaps:

• j = 1: Swap grid[1][1] (6) with grid[3][1] (14)
• j = 2: Swap grid[1][2] (7) with grid[3][2] (15)
• j = 3: Swap grid[1][3] (8) with grid[3][3] (16)

Final Result:

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

The submatrix has been flipped vertically:

• Original submatrix rows: [6,7,8], [10,11,12], [14,15,16]
• Flipped submatrix rows: [14,15,16], [10,11,12], [6,7,8]

Note that row 2 (containing 10,11,12) remains in its original position since it's the middle row of an odd-sized submatrix, and elements outside the submatrix (like 1,2,3,4,5,9,13) remain unchanged.

Solution Implementation

Time and Space Complexity

The time complexity is O(k^2), where k is the side length of the submatrix. This is because:

• The outer loop runs k/2 times (from x to x + k//2)
• The inner loop runs k times (from y to y + k)
• Therefore, the total number of operations is (k/2) * k = k^2/2, which simplifies to O(k^2)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the loop variables i, i2, and j, regardless of the input size. The swapping operation is performed in-place on the existing grid without allocating any additional data structures.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Row Iteration Range

A common mistake is iterating through all k rows instead of just the first half, which would cause each pair of rows to be swapped twice, resulting in no change to the matrix.

Incorrect approach:

# This swaps each pair twice, undoing the operation
for row_idx in range(x, x + k):  # Wrong! Goes through all k rows
    mirror_row_idx = x + k - 1 - (row_idx - x)
    # Swap logic...

Correct approach:

# Only iterate through the first half of rows
for row_idx in range(x, x + k // 2):  # Correct! Only first half
    mirror_row_idx = x + k - 1 - (row_idx - x)
    # Swap logic...

2. Off-by-One Error in Mirror Row Calculation

Another frequent error is forgetting to subtract 1 when calculating the last row index of the submatrix, leading to accessing rows outside the intended submatrix.

Incorrect formula:

# This accesses row x + k, which is outside the submatrix
mirror_row_idx = x + k - (row_idx - x)  # Wrong! Missing -1

Correct formula:

# Properly calculates the mirror row within bounds
mirror_row_idx = x + k - 1 - (row_idx - x)  # Correct!

3. Modifying Grid While Iterating Without Proper Swapping

Some might attempt to assign values directly without swapping, which would overwrite data before it's moved to its correct position.

Incorrect approach:

# This loses the original value of grid[row_idx][col_idx]
for row_idx in range(x, x + k // 2):
    mirror_row_idx = x + k - 1 - (row_idx - x)
    for col_idx in range(y, y + k):
        grid[row_idx][col_idx] = grid[mirror_row_idx][col_idx]  # Data loss!
        grid[mirror_row_idx][col_idx] = grid[row_idx][col_idx]  # Already overwritten!

Correct approach:

# Proper simultaneous swap preserves both values
grid[row_idx][col_idx], grid[mirror_row_idx][col_idx] = (
    grid[mirror_row_idx][col_idx], 
    grid[row_idx][col_idx]
)

4. Assuming Square Matrix Instead of Submatrix

A conceptual error is treating the entire grid as the target for flipping rather than just the k × k submatrix starting at (x, y).

Prevention: Always ensure your row iteration is range(x, x + k // 2) and column iteration is range(y, y + k), not range(0, m // 2) and range(0, n).