Quick Overview

A grid simulation question about an orchard of rotten trees, healthy trees and empty ground, where each day rot spreads at once from every rotten tree to the healthy trees directly beside it. It asks for the orchard after a given number of days and tests simultaneous updates, blocked cells and very large day counts.

Simulate Rot Spreading Through an Orchard Grid Over a Number of Days

Company: Capital One

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

An orchard is a grid of characters: `'R'` is a rotten tree, `'H'` is a healthy tree, and `'-'` is empty ground. Every day, each rotten tree turns every healthy tree directly above, below, left or right of it rotten, and all of these changes happen at the same time. Given the orchard and a number of days, return the orchard after that many days. ### Function Signature ```python def orchard_after_days(orchard: list[str], days: int) -> list[str]: ``` ### Rules - Day 0 is the given orchard. The orchard after day `d + 1` is computed from the orchard after day `d`: every `'H'` cell with at least one `'R'` cell directly above, below, left or right of it becomes `'R'`, and every other cell keeps its character. - A tree that turns rotten during a day starts spreading rot only on the following day. - Diagonal cells are not neighbors, and rot does not wrap around the edges of the grid. - Empty ground never changes and does not pass rot along. - With `days = 0`, return the orchard unchanged. - Return a list of strings with the same number of rows, in the same order, each of the same length as in the input. ### Constraints - `1 <= len(orchard) <= 200` - `1 <= len(orchard[r]) <= 200`, and all rows have the same length - every character is `'R'`, `'H'` or `'-'` - `0 <= days <= 10^9` ### Examples **Example 1** ```text Input: orchard = ["RH-", "HHH", "-HH"], days = 1 Output: ["RR-", "RHH", "-HH"] ``` The rotten tree in the top-left corner rots its right neighbor and the tree below it. **Example 2** ```text Input: orchard = ["RH-", "HHH", "-HH"], days = 3 Output: ["RR-", "RRR", "-RH"] ``` Day 2 rots the center tree. Day 3 rots the right tree of the middle row and the middle tree of the bottom row. The bottom-right tree would rot on day 4. **Example 3** ```text Input: orchard = ["H-R"], days = 5 Output: ["H-R"] ``` The empty ground separates the healthy tree from the rotten one, so it never rots.

Overview: A grid simulation question about an orchard of rotten trees, healthy trees and empty ground, where each day rot spreads at once from every rotten tree to the healthy trees directly beside it. It asks for the orchard after a given number of days and tests simultaneous updates, blocked cells and very large day counts.

Read the full Capital One Software Engineer interview experience this question came from

An orchard is given as a grid of characters, one string per row: `'R'` is a rotten tree, `'H'` is a healthy tree, and `'-'` is empty ground. Every day, each rotten tree turns every healthy tree directly above, below, left or right of it rotten, and all of these changes happen at the same time. Given the orchard and a number of days, return the orchard after that many days. Implement `orchard_after_days(orchard, days)`. ### Rules - Day 0 is the given orchard. The orchard after day `d + 1` is computed from the orchard after day `d`: every `'H'` cell with at least one `'R'` cell directly above, below, left or right of it becomes `'R'`, and every other cell keeps its character. - A tree that turns rotten during a day starts spreading rot only on the following day. - Diagonal cells are not neighbors, and rot does not wrap around the edges of the grid. - Empty ground never changes and does not pass rot along. - With `days = 0`, return the orchard unchanged. - Return a list of strings with the same number of rows, in the same order, each of the same length as in the input. ### Constraints - `1 <= len(orchard) <= 200` - `1 <= len(orchard[r]) <= 200`, and all rows have the same length - every character is `'R'`, `'H'` or `'-'` - `0 <= days <= 10^9` No value in this problem exceeds 2^31 - 1: `days` fits in a signed 32-bit integer (`int` in Java and C++). ### Example 1 ```text Input: orchard = ["RH-", "HHH", "-HH"], days = 1 Output: ["RR-", "RHH", "-HH"] ``` The rotten tree in the top-left corner rots its right neighbor and the tree below it. ### Example 2 ```text Input: orchard = ["RH-", "HHH", "-HH"], days = 3 Output: ["RR-", "RRR", "-RH"] ``` Day 2 rots the center tree. Day 3 rots the right tree of the middle row and the middle tree of the bottom row. The bottom-right tree would rot on day 4.

Constraints

  • 1 <= len(orchard) <= 200
  • 1 <= len(orchard[r]) <= 200, and all rows have the same length
  • every character is 'R', 'H' or '-'
  • 0 <= days <= 10^9

Examples

Input: (['R'], 0)

Expected Output: ['R']

Explanation: Minimum valid: a 1x1 rotten tree with days = 0 is returned unchanged.

Input: (['H'], 1)

Expected Output: ['H']

Explanation: Minimum valid: a 1x1 healthy tree with no rotten tree anywhere stays healthy after one day.

Hints

  1. All changes in a day happen at the same time: a tree that rots today must not rot its neighbours until tomorrow, so be careful if you update the grid in place.
  2. days can be as large as 10^9, far more than the number of cells. When does the orchard stop changing, and how much work does each day really need?
  3. A healthy tree cut off from every rotten tree by empty ground or the grid edge never rots, no matter how many days pass.

Loading coding console...

Show the approach

Approach

Run a level-by-level multi-source breadth-first search over the grid. The day-0 frontier is every 'R' cell. For each day, while fewer than days days have been processed and the frontier is non-empty, examine the four orthogonal neighbours of every frontier cell; each in-bounds 'H' neighbour is changed to 'R' and appended to the next frontier, which replaces the current one when the day ends.

Invariant: after d processed days the grid equals the orchard after day d, and the frontier holds exactly the cells that turned rotten on day d. Only those cells can rot anything on day d + 1, because every older rotten cell already rotted all of its healthy neighbours on the day after it turned. Cells rotted during a day go into the next frontier, not the current one, so they first spread on the following day, which is exactly the simultaneous update. Equivalently, a healthy tree ends up rotten iff its shortest 4-directional path through healthy trees from some rotten tree has length at most days.

Empty ground is never entered, bounds checks stop wrapping, and diagonals are never examined. Each cell joins a frontier at most once, so the loop runs at most min(days, R * C) times and the total work is O(R * C) no matter how large days is (up to 10^9); the loop stops as soon as the frontier empties.

Edge cases: days = 0 returns the input unchanged; a grid with no 'R' or no 'H' never changes; healthy regions sealed off by '-' or the grid edge stay healthy forever.

Time complexity:
O(R * C), where R is the number of rows and C the number of columns, independent of days
Space complexity:
O(R * C)