Push Dominoes

Simulate each round of falling: apply forces from all currently-falling dominoes to their neighbors. Repeat until no changes occur. In the worst case this takes O(n) rounds of O(n) work each.

1. 1Convert the string to a list for in-place updates.
2. 2In each round, scan all positions and apply forces: R pushes right, L pushes left.
3. 3Repeat until the state stops changing.

Why it's not optimal: Up to O(n) rounds × O(n) per round = O(n²). The two-pointer approach processes each pair of adjacent force points directly in O(n).

def pushDominoes(dominoes):
    state = list(dominoes)
    while True:
        new_state = state[:]
        for i in range(len(state)):
            if state[i] == '.':
                if i > 0 and state[i-1] == 'R':
                    new_state[i] = 'R'
                elif i < len(state)-1 and state[i+1] == 'L':
                    new_state[i] = 'L'
        if new_state == state: break
        state = new_state
    return ''.join(state)

Pad the string with sentinel 'L' on the left and 'R' on the right. Then scan for adjacent force points (dom[l], dom[r]) and deterministically fill the gap between them based on the four possible combinations.

1. 1Pad: dom = 'L' + dominoes + 'R'.
2. 2Scan with pointer r. Skip dots. When dom[r] is L or R, process the gap (l, r).
3. 3L...L or R...R: fill all dots with that direction.
4. 4R...L: fill from both ends inward (R from left, L from right). Middle dot stays if gap is odd.
5. 5L...R: all dots stay (forces point away from each other).