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.