Flip Square Submatrix Vertically - Video Solutions
Flip Square Submatrix Vertically | Clean Simple Code | Leetcode 3643 | codestorywithMIK
Flip Square Submatrix Vertically - Video Solution
Watch 10 video solutions for Flip Square Submatrix Vertically, a easy level problem involving Array, Two Pointers, Matrix. This walkthrough by codestorywithMIK has 3,973 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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)
Approach Overview
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.
Complexity Analysis
| 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 |