Get started

Push Dominoes — Medium Problem & Solution

A row of dominoes is described by a string: 'L' was pushed left, 'R' was pushed right, and '.' is still standing.

Problem statement

A row of dominoes is described by a string: 'L' was pushed left, 'R' was pushed right, and '.' is still standing.

Each second, a falling domino pushes the adjacent standing one in the same direction. A standing domino with a falling domino on both sides stays upright, because the forces cancel.

Return the final state once nothing moves any more.

Example 1

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The third domino is pushed left by the fourth; the second one was already down.

Example 2

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Explanation: In the run `R...L` the outer two meet in the middle and the exact centre stays standing.

Example 3

Input: dominoes = "..."
Output: "..."
Explanation: Nothing was ever pushed.

Constraints

  • 1 <= dominoes.length <= 100000
  • dominoes[i] is 'L', 'R' or '.'

How to solve Push Dominoes

The outcome of each maximal run of dots depends only on the two non-dot characters bounding it. Padding the row with a leftward push on the far left and a rightward push on the far right makes every run bounded, and then each of the four cases has a closed form.

Approach

  1. Form s = "L" + dominoes + "R"; the sentinels push away from the row, so they never disturb it.
  2. Walk i over the non-dot positions, keeping prev as the previous one.
  3. Emit s[prev] (unless it is the left sentinel) followed by the gap = i - prev - 1 dots resolved by case: same characters fill with that character, L…R stays all dots, R…L fills half R, half L, with a single . in the middle when the gap is odd.

Why it works

Forces only travel along a run of standing dominoes, so a run's fate is decided by its two ends. With R…L the two waves advance at the same rate and meet after gap/2 steps: an odd gap leaves a domino pushed equally from both sides, which the rules say stays up. The sentinels encode the true boundary behaviour — a leading …L really does drag everything before it down, and a trailing R… really does push everything after it.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Simulating second by second is O(n²) on a long row of dots.
  • Forgetting the sentinels loses the leading and trailing runs.
  • With an odd gap in R…L, the centre domino stays '.' — it is not pushed either way.

Reference solution

Python

def pushDominoes(dominoes: str) -> str:
    s = "L" + dominoes + "R"
    out = []
    prev = 0
    for i in range(1, len(s)):
        if s[i] == ".":
            continue
        gap = i - prev - 1
        if prev > 0:
            out.append(s[prev])
        if s[prev] == s[i]:
            out.append(s[i] * gap)
        elif s[prev] == "L" and s[i] == "R":
            out.append("." * gap)
        else:
            out.append("R" * (gap // 2))
            if gap % 2 == 1:
                out.append(".")
            out.append("L" * (gap // 2))
        prev = i
    return "".join(out)

JavaScript

var pushDominoes = function(dominoes) {
    var s = "L" + dominoes + "R";
    var out = [];
    var prev = 0;
    for (var i = 1; i < s.length; i++) {
        if (s.charAt(i) === ".") continue;
        var gap = i - prev - 1;
        if (prev > 0) out.push(s.charAt(prev));
        var t;
        if (s.charAt(prev) === s.charAt(i)) {
            for (t = 0; t < gap; t++) out.push(s.charAt(i));
        } else if (s.charAt(prev) === "L" && s.charAt(i) === "R") {
            for (t = 0; t < gap; t++) out.push(".");
        } else {
            var half = Math.floor(gap / 2);
            for (t = 0; t < half; t++) out.push("R");
            if (gap % 2 === 1) out.push(".");
            for (t = 0; t < half; t++) out.push("L");
        }
        prev = i;
    }
    return out.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue