Katkat
Back

Count the Leaves Left on a Grid After a Sequence of Wind Gusts

CrestaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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

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

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

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

Input: grid = [[0, 5, 0]], winds = []
Output: 5

No gust blows, so all 5 leaves stay.