When solving this, I imagined the dominoes as experiencing "forces" from left and right. Each domino receives a force from the closest 'R' to its left or 'L' to its right. The closer the source, the stronger the force. I assigned a large positive value when a domino was pushed to the right ('R') and a large negative value when pushed to the left ('L'). Then I scanned the string twice:
- Left to Right: I assigned decreasing positive forces after each 'R' and reset after 'L'.
- Right to Left: I assigned decreasing negative forces after each 'L' and reset after 'R'.
Finally, I added the forces at each position:
- Positive: falls right 'R'
- Negative: falls left 'L'
- Zero: stays '.'
class Solution:
def pushDominoes(self, dominoes: str) -> str:
n = len(dominoes)
forces = [0] * n
force = 0
for i in range(n):
if dominoes[i] == 'R':
force = n
elif dominoes[i] == 'L':
force = 0
else:
force = max(force - 1, 0)
forces[i] += force
force = 0
for i in range(n - 1, -1, -1):
if dominoes[i] == 'L':
force = n
elif dominoes[i] == 'R':
force = 0
else:
force = max(force - 1, 0)
forces[i] -= force
# Build final result
result = []
for f in forces:
if f > 0:
result.append('R')
elif f < 0:
result.append('L')
else:
result.append('.')
return ''.join(result)- Time: O(n)
- Space: O(n)
- Space: O(n)