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:

1. 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.

2. 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.

3. 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].

4. 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--).

5. 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