Subramanya's Digital Garden

Recent Notes

3643. Flip Square Submatrix Vertically

6 min read

Problem Statement

We’re given a grid of numbers (an m x n integer matrix). Our mission is to take a specific square portion of this grid, defined by its top-left corner (x, y) and its side length k, and flip it upside down. Essentially, we need to reverse the order of the rows within that square submatrix. We then return the modified grid.

Breaking Down the Problem

At its heart, this problem asks us to manipulate a specific section of a 2D array. The key operation is reversing the order of rows within that designated square. We need to be careful not to affect the parts of the grid outside this submatrix.

The main challenge lies in correctly identifying the rows that belong to the submatrix and then performing the reversal on only those rows, while maintaining the order of elements within each row.

A potential hidden constraint is that the submatrix is always a square. This might simplify some approaches compared to dealing with a rectangular submatrix.

Intuition & Thought Process

Imagine your matrix is a multi-level bookshelf. You are asked to reverse the order of a specific section of books on a few shelves.

  • x and y tell you which shelf and which position on the shelf to start at.
  • k tells you how many shelves deep and how many books across your section is.

Your task is to flip this block of books “vertically.” How would you do it efficiently? You wouldn’t create a whole new bookshelf section. Instead, you’d perform the swaps directly on the existing shelf.

You would take the entire top row of books in your section and swap their position with the entire bottom row of books. Then, you’d take the second shelf from the top and swap it with the second from the bottom. You would continue this process, working from the outside in, until you reach the middle.

This bookshelf analogy is a perfect fit for our problem. Each row in the submatrix is like a shelf of books. Our goal is to swap the entire top “shelf” (row) with the bottom “shelf” (row), then the next pair, and so on, until the whole section is reversed.

A brute-force approach might involve taking all the books in the section off the shelf, arranging them in the flipped order on a temporary cart, and then putting them back. While this works, it requires extra space (the cart) and is less efficient. We can do better by swapping the rows directly on the “bookshelf” (the grid).

Step-by-Step Approach

This problem falls into the category of array manipulation. The efficient approach involves using a two-pointer technique.

  1. Identify the Row Range: Determine the starting and ending row indices of the submatrix we need to flip. These will be start_row = x and end_row = x + k - 1.
  2. Initialize Pointers: Set up two pointers, one at the beginning of the submatrix rows (top = start_row) and one at the end (bottom = end_row).
  3. Iterate and Swap: While top is less than bottom, we need to swap the row at index top with the row at index bottom. Since we are dealing with rows within a 2D array, we need to swap the entire row.
  4. Move Pointers: After swapping, increment top and decrement bottom to move towards the middle of the submatrix rows.
  5. Repeat: Continue this process until top is no longer less than bottom. At this point, the rows within the submatrix will be reversed.

Time & Space Complexity

Brute-Force (with temporary matrix):

  • Time Complexity: O(k²) to copy the submatrix to the temporary matrix and then back.
  • Space Complexity: O(k²) to store the temporary submatrix.

Optimized (two-pointer):

  • Time Complexity: O(k²) because in the worst case, we iterate through all k rows of the submatrix, and for each swap, we potentially iterate through k elements in those rows.
  • Space Complexity: O(1) as we are modifying the grid in place using a constant amount of extra space for the pointers.

Code Implementation

Here are the optimized, in-place solutions in C++, Java, Python, and JavaScript.

C++

#include <vector>
#include <algorithm> // Required for std::swap
 
class Solution {
public:
    // The function modifies the grid in-place and returns it.
    std::vector<std::vector<int>>& flipSubmatrix(std::vector<std::vector<int>>& grid, int x, int y, int k) {
        int top = x;
        int bottom = x + k - 1;
 
        // Loop until the top and bottom pointers meet or cross.
        while (top < bottom) {
            // For the current pair of rows, iterate through the columns of the submatrix.
            for (int j = y; j < y + k; ++j) {
                // Swap the elements at the same column index in the top and bottom rows.
                std::swap(grid[top][j], grid[bottom][j]);
            }
            
            // Move the pointers towards the center.
            top++;
            bottom--;
        }
        
        return grid;
    }
};

Java

class Solution {
    public int[][] flipSubmatrix(int[][] grid, int x, int y, int k) {
        int top = x;
        int bottom = x + k - 1;
 
        // Loop until the top and bottom pointers meet in the middle.
        while (top < bottom) {
            // Iterate through the columns of the submatrix for the current rows.
            for (int j = y; j < y + k; j++) {
                // A classic swap using a temporary variable.
                int temp = grid[top][j];
                grid[top][j] = grid[bottom][j];
                grid[bottom][j] = temp;
            }
            
            // Move pointers inward for the next pair of rows.
            top++;
            bottom--;
        }
        
        return grid;
    }
}

Python

from typing import List
 
class Solution:
    def flipSubmatrix(self, grid: List[List[int]], x: int, y: int, k: int) -> List[List[int]]:
        top = x
        bottom = x + k - 1
 
        # Continue swapping rows until the pointers meet.
        while top < bottom:
            # In Python, we can swap the entire relevant slice of the rows directly.
            # This is more efficient and concise than a manual for-loop swap.
            grid[top][y:y+k], grid[bottom][y:y+k] = grid[bottom][y:y+k], grid[top][y:y+k]
            
            # Move the pointers towards each other.
            top += 1
            bottom -= 1
            
        return grid

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} x
 * @param {number} y
 * @param {number} k
 * @return {number[][]}
 */
var flipSubmatrix = function(grid, x, y, k) {
    let top = x;
    let bottom = x + k - 1;
 
    // Loop from the outside rows of the submatrix inwards.
    while (top < bottom) {
        // Iterate through the columns of the submatrix.
        for (let j = y; j < y + k; j++) {
            // Use array destructuring for a clean, inline swap.
            [grid[top][j], grid[bottom][j]] = [grid[bottom][j], grid[top][j]];
        }
        
        // Move the pointers to the next inner pair of rows.
        top++;
        bottom--;
    }
    
    return grid;
};

How to Recognize Similar Problems

Problems involving in-place reversal or manipulation of a specific segment of an array or matrix often hint at the use of two-pointer techniques. Look out for keywords like “reverse a sublist,” “rotate a section,” or any task that requires modifying a contiguous part of a data structure.

Graph View