⚡Flashcard Drill➔
NeetCode #125LC-838MediumArrays & Hashing
← Back to All Problems

#125 · #838 · Push Dominoes(推多米诺)

📌 Problem Statement & Constraints

Given a string dominoes where dominoes[i] is 'L', 'R' or '.', return the final state after all falling dominoes settle. A domino pushed left forces its left neighbour to fall left, and so on; when an 'R' and an 'L' meet, the ones between them stay upright. Constraints: 1 <= dominoes.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Model the forces numerically: R contributes a positive force decaying by 1 per step to the right, L a negative force decaying to the left.
  2. Sweep left to right accumulating the rightward force: reset to a large value on R, reset to 0 on L, and decrement by 1 on ..
  3. Sweep right to left accumulating the leftward force symmetrically, and add it to the same array.
  4. The final state is R where the total force is positive, L where negative, and . where it is zero -- which is exactly where the two forces cancel.

💻 Benchmark Python3 Implementation

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        force = [0] * n
        # rightward force from 'R'
        f = 0
        for i in range(n):
            if dominoes[i] == "R":
                f = n                      # strong enough to reach any distance
            elif dominoes[i] == "L":
                f = 0
            else:
                f = max(f - 1, 0)          # decay, but never negative
            force[i] += f
        # leftward force from 'L'
        f = 0
        for i in range(n - 1, -1, -1):
            if dominoes[i] == "L":
                f = n
            elif dominoes[i] == "R":
                f = 0
            else:
                f = max(f - 1, 0)
            force[i] -= f                  # leftward force is negative
        return "".join("R" if v > 0 else ("L" if v < 0 else ".") for v in force)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear sweeps.
💾 Space Complexity
O(n) for the force array.

⚠️ Interview Pitfalls & Follow-ups

  • Using a stack or simulating rounds: correct but O(n^2) in the worst case; the two-pass force accumulation is O(n).
  • Forgetting the decay (f - 1): the force would act across the whole string instead of stopping after a few cells.
  • Using f -= 1 without the max(..., 0): the force would become negative and leak past the boundary.
  • Treating an R and an L meeting with an odd gap: the middle cell stays upright when the gap is odd, which the equal-force cancellation handles automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems