Skip to main content
Talentd

Flip Square Submatrix Vertically - Solution & Explanation

EasyArrayTwo PointersMatrix7 min readAsked at: Meta, Google
Practice this problem

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100
  • 0 <= x < m
  • 0 <= y < n
  • 1 <= 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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation with Temporary MatrixO(k^2)O(k^2)Good for clarity or when modifying the original matrix directly is not allowed
In-Place Two Pointer Row SwapO(k^2)O(1)Best general solution when you can mutate the matrix and want constant extra space

Video Solution

Flip Square Submatrix Vertically | Clean Simple Code | Leetcode 3643 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 3,973 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Flip Square Submatrix Vertically with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays