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 ```python 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.