Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A run of upright dominoes is determined by the nearest initially pushed domino on each side. Equal directions sweep the whole run; forces pointing away leave it untouched; inward forces meet in the middle. This allows processing whole runs instead of simulating every second.

Approach

Scan left to right, counting pending dots and remembering the previous non-dot direction.
On L, fill the pending run with L if there was no previous push or it was also L. After R, split the run into a right-falling half and a left-falling half, retaining one central dot for an odd length.
On R, fill pending dots with R only if the previous push was R; after L or before any push they remain upright.
Append the current pushed domino and reset the pending count. At the end, trailing dots fall right only after R; otherwise they stay upright. Concatenate these resolved segments to form the final state.

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        last = ''
        count = 0
        res = ''

        for d in dominoes:
            if d == '.':
                count += 1
            else:
                if d == 'L':
                    if last == '': res += 'L' * count
                    elif last == 'L': res += 'L' * count
                    elif last == 'R':
                        res += 'R' * (count // 2)
                        if count % 2: res += '.'
                        res += 'L' * (count // 2)
                elif d == 'R':
                    if last == '': res += '.' * count
                    elif last == 'R': res += 'R' * count
                    elif last == 'L': res += '.' * count
                
                res += d
                count = 0
                last = d

        if count > 0:
            if last == 'R': res += 'R' * count
            else: res += '.' * count
        
        return res

Complexity analysis

For n = dominoes.length, the control-flow scan visits every symbol/run once, but both implementations repeatedly append to an immutable result string. A safe worst-case bound is O(n^2) time for cumulative copying and O(n) space for the constructed string; the returned output itself is O(n).