In-Place Rectangle Copy Within a 2D Array Using O(1) Extra Memory

You are given a 2D array grid and a rectangular block inside it: the block has height rows and width columns and its top-left cell is (src_row, src_col). Copy the block so that its top-left cell lands at (dst_row, dst_col), and return the grid after the copy.

The interviewer required the copy to use O(1) extra memory: modify grid in place without allocating a temporary copy of the block, the rows, or the grid. The source block and the destination block are in the same grid and may overlap.

Function Signature

def copy_rectangle(grid: list[list[int]], src_row: int, src_col: int, dst_row: int, dst_col: int, height: int, width: int) -> list[list[int]]:

Rules

• After the copy, for every 0 <= i < height and 0 <= j < width, cell (dst_row + i, dst_col + j) holds the value that cell (src_row + i, src_col + j) held before the copy started, even when the two blocks overlap.
• Every cell outside the destination block keeps its original value, including cells of the source block that the destination does not cover.
• Return the modified grid (the same list you were given, updated in place).

Constraints

• 1 <= len(grid) <= 500 and 1 <= len(grid[r]) <= 500; all rows have the same length.
• -10^9 <= grid[r][c] <= 10^9
• 1 <= height and 1 <= width.
• Both blocks lie entirely inside the grid: 0 <= src_row, 0 <= dst_row, src_row + height <= len(grid), dst_row + height <= len(grid), and the same for the columns with width and len(grid[0]).
• Extra memory must be O(1) beyond the input grid.

Examples

Example 1

• Input: grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], src_row = 0, src_col = 0, dst_row = 0, dst_col = 1, height = 2, width = 3
• Output: [[1, 1, 2, 3], [5, 5, 6, 7], [9, 10, 11, 12]]
• Explanation: The block [[1, 2, 3], [5, 6, 7]] moves one column to the right, overlapping itself. Column 0 keeps its original values.

Example 2

• Input: grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], src_row = 1, src_col = 1, dst_row = 0, dst_col = 0, height = 2, width = 2
• Output: [[6, 7, 3, 4], [10, 11, 7, 8], [9, 10, 11, 12]]
• Explanation: The block [[6, 7], [10, 11]] moves up and to the left. The source cells outside the destination, (1, 2), (2, 1) and (2, 2), keep their values.

Example 3

• Input: grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], src_row = 0, src_col = 0, dst_row = 1, dst_col = 2, height = 2, width = 2
• Output: [[1, 2, 3, 4], [5, 6, 1, 2], [9, 10, 5, 6]]
• Explanation: The blocks do not overlap, so the source block is simply duplicated.

In-Place Overlapping Block Copy

Hints

1. Think about the one-dimensional version first: when you shift part of an array to the right over itself, which end do you have to start copying from so that you never read a cell you already overwrote?
2. In two dimensions, a cell of the destination can only clobber a source cell that you still need if it lies in the direction the block is moving. Can you choose the row order and the column order independently?
3. Rows and columns each need their own direction, decided by comparing dst_row with src_row and dst_col with src_col.

Approach

The danger with an overlapping copy is reading a source cell after it has already been overwritten by the destination. Destination cell (dst_row + i, dst_col + j) takes its value from source cell (src_row + i, src_col + j). That source cell is also a destination cell (dst_row + i', dst_col + j') exactly when i' = i - (dst_row - src_row) and j' = j - (dst_col - src_col). If the block moves down (dst_row > src_row), then i' < i, so the rows must be processed from the bottom of the block upward: every row that could overwrite a needed source cell is written after that cell has been read. If the block moves up or stays on the same rows, the rows are processed top to bottom for the symmetric reason. When the block moves to a different row the row order alone keeps every read safe, because a row is always read before any other row writes into it. When the block stays on the same rows (dst_row == src_row), each row is a one-dimensional overlapping shift, so the columns are processed right-to-left if dst_col > src_col and left-to-right otherwise. The reference picks both directions up front and then does a plain nested loop, using only a handful of index variables: O(1) extra memory, and each of the height * width cells is written exactly once. A snapshot of the block would also produce the right grid, but it uses O(height * width) extra memory, which the interviewer ruled out.

• Time complexity: O(height * width)
• Space complexity: O(1) extra