What is the time complexity of the In-place Row Swapping approach?

The time complexity is O(k²), where k is the size of the square submatrix.

What is the space complexity of the In-place Row Swapping approach?

The space complexity is O(1) as we perform the operation in-place without allocating extra space proportional to the input size.

What is the space complexity of the Temporary Matrix approach?

The space complexity is O(k²) because we create a temporary matrix to store the submatrix.

Flip Square Submatrix Vertically

Difficulty: Easy | Acceptance: 79.40% | Paid: No Topics: Array, Two Pointers, Matrix

You are given a 2D integer matrix grid and three integers r, c, and k. The task is to flip the k x k square submatrix of grid whose top-left corner is at (r, c) vertically.

Flipping a submatrix vertically means that the first row of the submatrix becomes the last, the second row becomes the second last, and so on. The columns within the submatrix remain in their original positions.

Return the resulting matrix after performing the flip.

Examples
Constraints
Approach 1: In-place Row Swapping
Approach 2: Temporary Matrix

Examples

Example 1

Input:

grid = [[1,0,1],
        [1,1,1],
        [0,1,0]]
r = 0, c = 0, k = 2

Output:

[[1,1,1],
 [1,0,1],
 [0,1,0]]

Explanation: The top-left 2x2 submatrix is:

1 0
1 1

After flipping vertically, it becomes:

1 1
1 0

The rest of the matrix remains unchanged.

Example 2

Input:

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

Output:

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

Explanation: The 2x2 submatrix starting at (1,1) is:

6 7
10 11

After flipping vertically, it becomes:

10 11
6 7

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 100
0 <= r < m
0 <= c < n
1 <= k <= min(m - r, n - c)
0 <= grid[i][j] <= 10⁹

Approach 1: In-place Row Swapping

Intuition We can flip the submatrix vertically by reversing the order of the rows within the specified range. This is efficiently done using two pointers: one starting at the top row of the submatrix and one at the bottom row. We swap the elements between these two rows until the pointers meet in the middle.

Steps

Initialize top pointer to r and bottom pointer to r + k - 1.
Iterate while top < bottom.
In each iteration, iterate through the columns from c to c + k - 1 and swap grid[top][j] with grid[bottom][j].
Increment top and decrement bottom.
Return the modified grid.

python

Complexity

Time: O(k²) — We iterate through roughly half the rows of the submatrix (k/2) and for each row, we iterate through k columns.
Space: O(1) — We perform the swap in-place without using extra space proportional to the input size.
Notes: This is the most optimal approach for this problem.

Approach 2: Temporary Matrix

Intuition We can extract the target submatrix into a temporary 2D array, reverse the order of the rows in this temporary array, and then copy the data back into the original grid. This approach is conceptually simpler as it separates the “extraction”, “processing”, and “insertion” steps.

Steps

Create a temporary 2D array temp of size k x k.
Copy elements from grid starting at (r, c) into temp.
Iterate i from 0 to k - 1. Copy the row temp[k - 1 - i] back to grid[r + i] starting at column c.
Return the modified grid.

python

Complexity

Time: O(k²) — We iterate through the submatrix twice (once to copy to temp, once to copy back).
Space: O(k²) — We use a temporary matrix of size k x k to store the submatrix.
Notes: While easier to implement, this uses extra memory which is unnecessary for this specific operation.