Count the Leaves Left on a Grid After a Sequence of Wind Gusts
Company: Cresta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A rectangular field is divided into a grid of cells, and each cell holds some number of leaves. A sequence of wind gusts then blows across the field. Each gust pushes the leaves one cell in its direction, and leaves pushed past the edge of the field blow away. Apply the gusts in order and return how many leaves are still on the field at the end.
### Function Signature
```python
def leaves_remaining(grid: list[list[int]], winds: list[str]) -> int:
```
`grid[r][c]` is the number of leaves in row `r`, column `c`. Row 0 is the top row and column 0 is the leftmost column. `winds[i]` is the direction of the `i`-th gust: `"U"` (up), `"D"` (down), `"L"` (left) or `"R"` (right).
### Rules
- Gusts are applied one at a time, in the order given.
- During a gust, all leaves move at the same time, each exactly one cell in the gust's direction: `"U"` moves a leaf from row `r` to row `r - 1`, `"D"` to row `r + 1`, `"L"` moves it from column `c` to column `c - 1`, and `"R"` to column `c + 1`. All the leaves in a cell move together.
- A leaf whose new position is outside the grid is gone for good: no later gust brings it back.
- Return the total number of leaves on the grid after the last gust. If `winds` is empty, return the total of the initial grid.
### Constraints
- `1 <= len(grid) <= 50`, `1 <= len(grid[r]) <= 50`, and all rows have the same length
- `0 <= grid[r][c] <= 10^5`, so every total fits in a 32-bit signed integer
- `0 <= len(winds) <= 200`
- each `winds[i]` is one of `"U"`, `"D"`, `"L"`, `"R"`
### Examples
**Example 1**
```text
Input: grid = [[1, 2, 0], [0, 3, 4], [5, 0, 6]], winds = ["R", "D"]
Output: 6
```
The gust to the right blows the rightmost column (0 + 4 + 6 = 10 leaves) off the field and leaves `[[0, 1, 2], [0, 0, 3], [0, 5, 0]]`. The gust down blows the bottom row (5 leaves) off and leaves `[[0, 0, 0], [0, 1, 2], [0, 0, 3]]`, which holds 6 leaves.
**Example 2**
```text
Input: grid = [[1, 1], [1, 1]], winds = ["L", "R"]
Output: 2
```
The gust to the left blows the left column off and leaves `[[1, 0], [1, 0]]`. The gust to the right moves those leaves to the right column, `[[0, 1], [0, 1]]`; the leaves already blown away do not come back.
**Example 3**
```text
Input: grid = [[0, 5, 0]], winds = []
Output: 5
```
No gust blows, so all 5 leaves stay.
Overview: Simulate wind gusts over a grid in which every cell holds a number of leaves: each gust shifts all leaves one cell in its direction, and leaves pushed off the edge are lost for good. Return how many leaves remain, testing careful two-dimensional state updates and boundary handling under time pressure.
Read the full Cresta Software Engineer interview experience this question came from
A rectangular field is divided into a grid of cells, and each cell holds some number of leaves. A sequence of wind gusts then blows across the field. Each gust pushes the leaves one cell in its direction, and leaves pushed past the edge of the field blow away. Apply the gusts in order and return how many leaves are still on the field at the end.
Implement `leaves_remaining(grid, winds)`:
- `grid[r][c]` is the number of leaves in row `r`, column `c`. Row 0 is the top row and column 0 is the leftmost column.
- `winds[i]` is the direction of the `i`-th gust: `"U"` (up), `"D"` (down), `"L"` (left) or `"R"` (right).
### Rules
- Gusts are applied one at a time, in the order given.
- During a gust, all leaves move at the same time, each exactly one cell in the gust's direction: `"U"` moves a leaf from row `r` to row `r - 1`, `"D"` to row `r + 1`, `"L"` moves it from column `c` to column `c - 1`, and `"R"` to column `c + 1`. All the leaves in a cell move together.
- A leaf whose new position is outside the grid is gone for good: no later gust brings it back.
- Return the total number of leaves on the grid after the last gust, as an integer. If `winds` is empty, return the total of the initial grid.
### Constraints
- `1 <= len(grid) <= 50`, `1 <= len(grid[r]) <= 50`, and all rows have the same length
- `0 <= grid[r][c] <= 10^5`, so every total fits in a 32-bit signed integer: it is at most 50 * 50 * 10^5 = 250,000,000 and never exceeds 2^31 - 1
- `0 <= len(winds) <= 200`
- each `winds[i]` is one of `"U"`, `"D"`, `"L"`, `"R"`
### Example 1
```text
Input: grid = [[1, 2, 0], [0, 3, 4], [5, 0, 6]], winds = ["R", "D"]
Output: 6
```
The gust to the right blows the rightmost column (0 + 4 + 6 = 10 leaves) off the field and leaves `[[0, 1, 2], [0, 0, 3], [0, 5, 0]]`. The gust down blows the bottom row (5 leaves) off and leaves `[[0, 0, 0], [0, 1, 2], [0, 0, 3]]`, which holds 6 leaves.
### Example 2
```text
Input: grid = [[1, 1], [1, 1]], winds = ["L", "R"]
Output: 2
```
The gust to the left blows the left column off and leaves `[[1, 0], [1, 0]]`. The gust to the right moves those leaves to the right column, `[[0, 1], [0, 1]]`; the leaves already blown away do not come back.
Constraints
- 1 <= len(grid) <= 50, 1 <= len(grid[r]) <= 50, and all rows have the same length
- 0 <= grid[r][c] <= 10^5, so every total fits in a 32-bit signed integer (at most 250,000,000)
- 0 <= len(winds) <= 200
- each winds[i] is one of "U", "D", "L", "R"
Examples
Input: ([[1, 2, 0], [0, 3, 4], [5, 0, 6]], ['R', 'D'])
Expected Output: 6
Explanation: Source example 1: R blows off the right column (10 leaves), D blows off the bottom row (5 leaves), 6 remain.
Input: ([[1, 1], [1, 1]], ['L', 'R'])
Expected Output: 2
Explanation: Source example 2 and opposite-gust regression: the left column blown off by L does not come back on R, so 2 of 4 leaves remain.
Hints
- Row 0 is the top row: "U" lowers the row index, "D" raises it, and "L" and "R" change only the column index.
- A leaf that leaves the grid never returns, so a left gust followed by a right gust still loses the leaves that started in the leftmost column.
- With at most 50 x 50 cells and 200 gusts, you can either apply each gust in turn or reason about where the leaves from each starting cell travel; both are fast enough.