Push Dominoes

Medium
767.

Push Dominoes

Push Dominoes is a medium coding problem on strings, dynamic programming and two pointers, asked in Amazon, Google and Flipkart interviews.

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 '.'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} dominoes
 * @return {string}
 */
var pushDominoes = function(dominoes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Push Dominoes — Solution in Python, Java & C++

Push Dominoes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Push Dominoes is a medium coding problem on strings, dynamic programming and two pointers, asked in Amazon, Google and Flipkart interviews.

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 '.'

Hints for Push Dominoes

  1. Hint 1

    Every standing run is bounded by two pushed dominoes (or by the ends of the row).

  2. Hint 2

    Pad the string with a virtual 'L' on the left and 'R' on the right so every run has two bounds.

  3. Hint 3

    The four bound pairs behave differently: L…L all fall left, R…R all fall right, L…R nothing moves, R…L meets in the middle.

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)

Java

public static String pushDominoes(String dominoes) {
    String s = "L" + dominoes + "R";
    StringBuilder out = new StringBuilder();
    int prev = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == '.') continue;
        int gap = i - prev - 1;
        if (prev > 0) out.append(s.charAt(prev));
        int t;
        if (s.charAt(prev) == s.charAt(i)) {
            for (t = 0; t < gap; t++) out.append(s.charAt(i));
        } else if (s.charAt(prev) == 'L' && s.charAt(i) == 'R') {
            for (t = 0; t < gap; t++) out.append('.');
        } else {
            for (t = 0; t < gap / 2; t++) out.append('R');
            if (gap % 2 == 1) out.append('.');
            for (t = 0; t < gap / 2; t++) out.append('L');
        }
        prev = i;
    }
    return out.toString();
}

C++

string pushDominoes(string dominoes) {
    string s = "L" + dominoes + "R";
    string out;
    int prev = 0;
    for (int i = 1; i < (int) s.size(); i++) {
        if (s[i] == '.') continue;
        int gap = i - prev - 1;
        if (prev > 0) out += s[prev];
        if (s[prev] == s[i]) {
            out.append((size_t) gap, s[i]);
        } else if (s[prev] == 'L' && s[i] == 'R') {
            out.append((size_t) gap, '.');
        } else {
            out.append((size_t) (gap / 2), 'R');
            if (gap % 2 == 1) out += '.';
            out.append((size_t) (gap / 2), 'L');
        }
        prev = i;
    }
    return 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming