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
- Model the forces numerically:
Rcontributes a positive force decaying by 1 per step to the right,La negative force decaying to the left. - Sweep left to right accumulating the rightward force: reset to a large value on
R, reset to 0 onL, and decrement by 1 on.. - Sweep right to left accumulating the leftward force symmetrically, and add it to the same array.
- The final state is
Rwhere the total force is positive,Lwhere 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 -= 1without themax(..., 0): the force would become negative and leak past the boundary. - Treating an
Rand anLmeeting 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.