Droplets: Simulate Water Droplet Merging on a 1D Surface. LeakCode

Question Details

Problem

You have a 1D array representing a surface. Water droplets fall at positions given in a list. When two droplets are adjacent (no gap between them), they merge into one larger droplet. After all droplets have fallen,

return the number of distinct water bodies and the size of the largest one.

python
def simulate_droplets(surface_len: int, drops: list[int]) -> tuple[int, int]:

**returns** (num_distinct_bodies, largest_body_size)
    pass

Example:


**Input**:  surface_len = 10, drops = [3, 4, 7, 8, 9]

After all drops:
  Positions filled: {3,4,7,8,9}
  Body 1: [3,4]   -> size 2
  Body 2: [7,8,9] -> size 3

**Output**: (2, 3)

Follow-ups

How would you track which droplets merged and when (event log)?
If drops are applied one at a time and you must answer queries after each drop, what data structure handles this efficiently?
Extend to 2D: droplets fall on a grid and merge if they touch horizontally or vertically.
What is the time complexity of your approach using a Union-Find structure?

Full Details

Problem

You have a 1D array representing a surface. Water droplets fall at positions given in a list. When two droplets are adjacent (no gap between them), they merge into one larger droplet. After all droplets have fallen,

return the number of distinct water bodies and the size of the largest one.

python
def simulate_droplets(surface_len: int, drops: list[int]) -> tuple[int, int]:

**returns** (num_distinct_bodies, largest_body_size)
    pass

Example:


**Input**:  surface_len = 10, drops = [3, 4, 7, 8, 9]

After all drops:
  Positions filled: {3,4,7,8,9}
  Body 1: [3,4]   -> size 2
  Body 2: [7,8,9] -> size 3

**Output**: (2, 3)

Follow-ups

How would you track which droplets merged and when (event log)?
If drops are applied one at a time and you must answer queries after each drop, what data structure handles this efficiently?
Extend to 2D: droplets fall on a grid and merge if they touch horizontally or vertically.
What is the time complexity of your approach using a Union-Find structure?

Free preview. Unlock all questions →

Topics

Coding Onsite

More from Airbnb

Reddit Airbnb engineering apprenticeship 2026 assessment. What questions to expect? 1p3a Airbnb and DoorDash Senior Software Engineer Interview Experience 1p3a Airbnb Senior Software Engineer TPS Interview Question 1p3a Airbnb Fullstack SDE Tech Phone Screen Experience in August LeetCode Airbnb onsite