Vansh Aggarwal

Posted on May 6

LeetCode Solution: 3643. Flip Square Submatrix Vertically

#leetcode #dsa #programming #tutorial

Master the Matrix: Flipping Submatrices Vertically Like a Pro! 🚀

Hey LeetCoders and aspiring competitive programmers! 👋 Vansh2710 here, ready to tackle another exciting problem that will sharpen your array manipulation skills. Today, we're diving into LeetCode Problem 3643: Flip Square Submatrix Vertically.

This problem is a fantastic way to practice working with 2D arrays (matrices) and understanding how to manipulate specific regions within them. Don't worry if matrices feel intimidating – we'll break it down step-by-step!

What's the Challenge? 🤔

Imagine you have a giant grid of numbers, like a spreadsheet or a chessboard. Your mission, should you choose to accept it, is to find a specific square within this grid and flip it upside down.

Here's the breakdown:

You get an m x n integer grid (our big matrix).
You're given x and y, which are the row and column indices of the top-left corner of the submatrix we want to flip.
You're also given k, which is the side length of this square submatrix. So, it's a k x k square!

Your goal is to "flip the submatrix by reversing the order of its rows vertically." This means the top row of the submatrix becomes the bottom, the second-from-top becomes the second-from-bottom, and so on.

Finally, you need to return the updated grid.

Let's look at Example 1 to make it crystal clear:

Input:
grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], x = 1, y = 0, k = 3

Here, x=1, y=0 points to the 5. A k=3 square submatrix starting there means we're looking at:

[5,  6,  7]
[9, 10, 11]
[13, 14, 15]

After flipping vertically, the row [5,6,7] should go to the bottom, and [13,14,15] should go to the top. The middle row [9,10,11] stays in the middle.

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

Notice how only the designated submatrix cells are affected! The numbers outside this 3x3 square (1,2,3,4, 8, 12, 16) remain untouched.

The "Aha!" Moment 💡

When you hear "flip vertically" or "reverse order," what's the first thing that comes to mind? If you've ever reversed an array or a linked list, you know the classic trick: swap elements from the beginning with elements from the end, and work your way inwards!

This problem is no different! Instead of swapping individual numbers in a 1D array, we'll be swapping entire rows within our chosen submatrix.

Think about it:

The very top row of the submatrix needs to swap places with the very bottom row of the submatrix.
The second row from the top needs to swap with the second row from the bottom.
...and so on, until you reach the middle.

This symmetrical swapping is the core intuition.

Our Step-by-Step Approach 🚶‍♂️

Let's translate that intuition into concrete steps:

Identify the Submatrix Boundaries:
- The startingRow of our submatrix is simply x.
- The endingRow of our submatrix will be x + k - 1 (since k is the size, a k x k matrix from x will go up to x + k - 1).
- The startingColumn of our submatrix is y.
- The endingColumn of our submatrix will be y + k - 1.
Two Pointers for Rows:
- We'll use two pointers, topRowIdx (initialized to startingRow) and bottomRowIdx (initialized to endingRow).
- We want to continue swapping as long as topRowIdx is less than bottomRowIdx. Once they meet or cross, we've flipped the whole section.
Swap Corresponding Rows (Elements by Element):
- Inside our loop (while (topRowIdx < bottomRowIdx)), for each pair of topRowIdx and bottomRowIdx rows, we need to swap only the elements that belong to the submatrix.
- This means we'll iterate through the columns from startingColumn (y) up to endingColumn (y + k - 1).
- For each column j in this range, we'll swap grid[topRowIdx][j] with grid[bottomRowIdx][j].
Move Pointers Inwards:
- After swapping all the relevant elements for the current topRowIdx and bottomRowIdx, we need to move our pointers closer to the center.
- Increment topRowIdx (topRowIdx++).
- Decrement bottomRowIdx (bottomRowIdx--).
Return the Modified Grid:
- Once the while loop finishes, the submatrix will be flipped, and the grid will be updated. Simply return grid.

Show Me the Code! 💻

class Solution {
public:
    vector<vector<int>> reverseSubmatrix(vector<vector<int>>& grid, int x, int y, int k) {
        // Step 1: Identify the boundaries of the submatrix for row indices
        int topRowIdx = x;
        int bottomRowIdx = x + k - 1;

        // Step 2 & 3: Use two pointers to swap rows symmetrically
        // We continue swapping as long as the top pointer is above the bottom pointer
        while (topRowIdx < bottomRowIdx) {
            // For each pair of rows (topRowIdx and bottomRowIdx),
            // we need to swap only the elements within the column range of the submatrix.
            // The columns relevant to our submatrix start at 'y' and extend 'k' elements.
            for (int col = y; col < y + k; ++col) {
                // Perform the swap: element in current top row and column
                // swaps with element in current bottom row and column.
                swap(grid[topRowIdx][col], grid[bottomRowIdx][col]);
            }

            // Step 4: Move the pointers inwards to process the next pair of rows
            topRowIdx++;
            bottomRowIdx--;
        }

        // Step 5: Return the modified grid
        return grid;
    }
};

Time and Space Complexity Analysis ⏱️

Let's break down how efficient our solution is:

Time Complexity: O(k^2)
- Our while loop runs approximately k / 2 times (because topRowIdx goes from x to x + k/2 and bottomRowIdx goes from x + k - 1 to x + k/2).
- Inside this while loop, our for loop iterates k times (from y to y + k - 1).
- So, the total number of swaps is proportional to (k/2) * k, which simplifies to O(k^2).
- Since k is the size of the submatrix, this makes perfect sense – we're essentially touching every element within the k x k submatrix once.
Space Complexity: O(1)
- We are modifying the grid in-place. We don't use any additional data structures that grow with the input size.
- The few integer variables (topRowIdx, bottomRowIdx, col) consume constant extra space.

Key Takeaways ✨

Two-Pointer Technique: A powerful pattern for reversing or processing symmetrical parts of data structures (arrays, linked lists, and even rows/columns in matrices!).
In-Place Modification: When possible, modifying the input directly is great for optimizing space complexity.
Boundary Awareness: Carefully calculating startingRow, endingRow, startingColumn, and endingColumn is crucial to ensure you're only affecting the intended submatrix. Remember k represents size, so an index range is often start to start + k - 1.

And there you have it! A neat and efficient way to flip a submatrix vertically. This problem teaches you fundamental matrix manipulation and reinforces the versatility of the two-pointer approach. Keep practicing, and you'll be a matrix master in no time!

Happy Coding! 🎉

Authored by Vansh2710 | Published: 2026-05-06 16:54:20

DEV Community