You are given an m x n integer matrix grid, and three integers x, y, and k.
The integers x and y represent the row and column indices of the top-left corner of a square submatrix and the integer k represents the size (side length) of the square submatrix.
Your task is to flip the submatrix by reversing the order of its rows vertically.
Return the updated matrix.
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
Output: [[1,2,3,4],[13,14,15,8],[9,10,11,12],[5,6,7,16]]
Explanation:
The diagram above shows the grid before and after the transformation.
Example 2:
Input: grid = [[3,4,2,3],[2,3,4,2]], x = 0, y = 2, k = 2
Output: [[3,4,4,2],[2,3,2,3]]
Explanation:
The diagram above shows the grid before and after the transformation.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 1000 <= x < m0 <= y < n1 <= k <= min(m - x, n - y)Problem Overview: You are given a matrix and a square submatrix inside it. Flipping the submatrix vertically means reversing the order of its rows while keeping the columns unchanged. Only the elements inside the square region are affected; everything outside remains the same.
Approach 1: Simulation with Temporary Copy (O(k^2) time, O(k^2) space)
Create a temporary k × k buffer representing the square region. Iterate through the submatrix and copy elements so that the top row maps to the bottom row, the second row maps to the second-last row, and so on. After constructing the flipped version, write the values back into the original matrix. This approach is straightforward and mirrors the definition of a vertical flip. The tradeoff is the extra memory used for the temporary matrix.
Approach 2: In-Place Row Swapping with Two Pointers (O(k^2) time, O(1) space)
Treat the square submatrix as a small matrix and reverse its rows using a two pointers technique. Place one pointer at the top row of the square and another at the bottom row. For each pair of rows, iterate through all k columns and swap the corresponding elements. Move the pointers toward the center until they meet. This works because a vertical flip is equivalent to reversing the row order of the submatrix.
The algorithm only touches cells inside the square region, so the work is proportional to k × k elements. No additional storage is required because swaps happen directly inside the original matrix.
This technique relies on simple operations on a matrix and indexed access in an array-like structure, which keeps the implementation short and cache-friendly.
Recommended for interviews: The in-place two-pointer swap is the expected solution. It shows you understand how a vertical flip works at the row level and how to manipulate a submatrix without extra memory. The temporary-copy simulation is still useful as a first step when explaining your thinking, but interviewers usually prefer the O(1) space version.
We start from row x and flip a total of \lfloor \frac{k}{2} \rfloor rows.
For each row i, we need to swap it with the corresponding row i_2, where i_2 = x + k - 1 - (i - x).
During the swap, we need to traverse j \in [y, y + k) and swap grid[i][j] with grid[i_2][j].
Finally, return the updated matrix.
The time complexity is O(k^2), where k is the side length of the submatrix. The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with Temporary Matrix | O(k^2) | O(k^2) | Good for clarity or when modifying the original matrix directly is not allowed |
| In-Place Two Pointer Row Swap | O(k^2) | O(1) | Best general solution when you can mutate the matrix and want constant extra space |
Flip Square Submatrix Vertically | Clean Simple Code | Leetcode 3643 | codestorywithMIK • codestorywithMIK • 3,792 views views
Watch 9 more video solutions →Practice Flip Square Submatrix Vertically with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor