In-Place Rectangle Copy Within a 2D Array Using O(1) Extra Memory
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Overview: Copy a rectangular block of a 2D array to another position in the same array, in place with O(1) extra memory, where the source and destination blocks may overlap. Tests choosing a safe copy direction so that no value is overwritten before it is read.
You are given a rectangular 2D integer grid `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 source block and the destination block are in the same grid and **may overlap**. Your interviewer required the copy to use **O(1) extra memory**: modify `grid` in place, without allocating a temporary copy of the block, of any row, or of the grid.
Implement `copy_rectangle(grid, src_row, src_col, dst_row, dst_col, height, width)`.
### 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 grid you were given, updated in place). The grader compares the returned grid cell by cell, row by row.
- If the source and destination are the same block, the grid is unchanged.
### 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]]
```
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]]
```
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]]
```
The blocks do not overlap, so the source block is simply duplicated.
### Constraints
- `1 <= len(grid) <= 500` and `1 <= len(grid[r]) <= 500`; all rows have the same length.
- `-10^9 <= grid[r][c] <= 10^9` (every value fits in a signed 32-bit integer).
- `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 likewise `0 <= src_col`, `0 <= dst_col`, `src_col + width <= len(grid[0])`, `dst_col + width <= len(grid[0])`.
- Extra memory must be O(1) beyond the input grid.
Constraints
- 1 <= len(grid) <= 500 and 1 <= len(grid[r]) <= 500; all rows have the same length.
- -10^9 <= grid[r][c] <= 10^9 (every value fits in a signed 32-bit integer).
- 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 likewise 0 <= src_col, 0 <= dst_col, src_col + width <= len(grid[0]), dst_col + width <= len(grid[0]).
- The source and destination blocks may overlap or coincide.
- Extra memory must be O(1) beyond the input grid (modify grid in place; no temporary copy of the block, a row, or the grid).
Examples
Input: ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], 0, 0, 0, 1, 2, 3)
Expected Output: [[1, 1, 2, 3], [5, 5, 6, 7], [9, 10, 11, 12]]
Explanation: Example 1: the block moves one column right and overlaps itself; column 0 keeps its values.
Input: ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], 1, 1, 0, 0, 2, 2)
Expected Output: [[6, 7, 3, 4], [10, 11, 7, 8], [9, 10, 11, 12]]
Explanation: Example 2: the block moves up and left; uncovered source cells keep their values.
Hints
- 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?
- 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?
- Rows and columns each need their own direction, decided by comparing dst_row with src_row and dst_col with src_col.