Flip Square Submatrix Vertically solution and explanation
Google
9 more videos on this problem
Flip Square Submatrix Vertically | Clean Simple Code | Leetcode 3643 | codestorywithMIKcodestorywithMIK · 7:09 · 3K views
3643. Flip Square Submatrix Vertically (Leetcode Easy)Programming Live with Larry · 6:15 · 444 views
3643. Flip Square Submatrix Vertically | Leetcode Daily - PythonLeetcode Daily · 5:17 · 415 views
Daily Leetcode #2181: Mar 21, 2026 - 3643. Flip Square Submatrix VerticallyProgramming Live with Larry · 6:02 · 302 views
Flip Square Submatrix Vertically | Leetcode 3643 | Java - HindiKernel Queen 👑 · 3:53 · 278 views
3643. Flip Square Submatrix Vertically | Leetcode Weekly Contest 462Break and Build · 9:22 · 215 views
Flip Square Submatrix Vertically | LeetCode 3643 - Pythonimpoldev · 6:42 · 136 views
LeetCode 3643 | Flip Square Submatrix Vertically | Two Pointer | EASY | JavaCode Kage · 4:49 · 100 views
LeetCode 3643 | Flip Submatrix Vertically (Easy) | Simple Matrix Trick 🔥AlgoDiary · 11:52 · 93 views
LeetCode 3643 | Flip Square Submatrix Vertically |Golang DSA with Golang · 16:16 · 88 views
The problem
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.
Solution
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).
class Solution:
def reverseSubmatrix(
self, grid: List[List[int]], x: int, y: int, k: int
) -> List[List[int]]:
for i in range(x, x + k // 2):
i2 = x + k - 1 - (i - x)
for j in range(y, y + k):
grid[i][j], grid[i2][j] = grid[i2][j], grid[i][j]
return gridclass Solution {
public int[][] reverseSubmatrix(int[][] grid, int x, int y, int k) {
for (int i = x; i < x + k / 2; i++) {
int i2 = x + k - 1 - (i - x);
for (int j = y; j < y + k; j++) {
int t = grid[i][j];
grid[i][j] = grid[i2][j];
grid[i2][j] = t;
}
}
return grid;
}
}class Solution {
public:
vector<vector<int>> reverseSubmatrix(vector<vector<int>>& grid, int x, int y, int k) {
for (int i = x; i < x + k / 2; i++) {
int i2 = x + k - 1 - (i - x);
for (int j = y; j < y + k; j++) {
swap(grid[i][j], grid[i2][j]);
}
}
return grid;
}
};function reverseSubmatrix(grid: number[][], x: number, y: number, k: number): number[][] {
for (let i = x; i < x + Math.floor(k / 2); i++) {
const i2 = x + k - 1 - (i - x);
for (let j = y; j < y + k; j++) {
[grid[i][j], grid[i2][j]] = [grid[i2][j], grid[i][j]];
}
}
return grid;
}func reverseSubmatrix(grid [][]int, x int, y int, k int) [][]int {
for i := x; i < x+k/2; i++ {
i2 := x + k - 1 - (i - x)
for j := y; j < y+k; j++ {
grid[i][j], grid[i2][j] = grid[i2][j], grid[i][j]
}
}
return grid
}impl Solution {
pub fn reverse_submatrix(
mut grid: Vec<Vec<i32>>,
x: i32,
y: i32,
k: i32,
) -> Vec<Vec<i32>> {
let x = x as usize;
let y = y as usize;
let k = k as usize;
for i in x..(x + k / 2) {
let i2 = x + k - 1 - (i - x);
for j in y..(y + k) {
let t = grid[i][j];
grid[i][j] = grid[i2][j];
grid[i2][j] = t;
}
}
grid
}
}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 |
Frequently asked questions
Is Flip Square Submatrix Vertically easy or hard?
Flip Square Submatrix Vertically is considered an easy problem. The main challenge is correctly identifying the boundaries of the square region and performing row swaps without affecting elements outside the submatrix.
Flip Square Submatrix Vertically Python/Java solution
The solution iterates over half of the rows of the square region and swaps elements column by column with the mirrored row. The same logic works across Python, Java, C++, Go, TypeScript, and Rust because it relies only on indexed matrix access and element swapping.
How to solve Flip Square Submatrix Vertically in O(n)?
The operation cannot generally be reduced to O(n) for the full matrix because only the square region must be flipped. The optimal method processes each element in the k × k submatrix exactly once using row swaps, giving O(k^2) time and O(1) space.
What is the best approach for Flip Square Submatrix Vertically?
The best approach is an in-place two pointer technique that swaps rows inside the square submatrix. One pointer starts at the top row and the other at the bottom row of the square. For each pair, swap all k column elements. This runs in O(k^2) time and uses O(1) extra space.
Is Flip Square Submatrix Vertically asked at Google/Amazon/Meta?
Matrix manipulation and submatrix transformation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving matrix flips, rotations, and submatrix operations are common because they test indexing accuracy and spatial reasoning.
What data structure is used in Flip Square Submatrix Vertically?
The problem operates on a 2D matrix stored as an array of arrays. The optimal solution also uses the two pointers technique to swap rows from the top and bottom of the square region.
What is the time complexity of Flip Square Submatrix Vertically?
The time complexity is O(k^2), where k is the side length of the square submatrix. Every element inside the k × k region is touched at most once during row swaps. The rest of the matrix is not processed.