1056MediumTwo PointersStringDynamic Programming

Where the Pushed Tiles Settle

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A row of tiles stands on edge and reads tiles. Each character is 'L' for a tile pushed leftwards at the same instant, 'R' for one pushed rightwards, and '.' for one left standing.

A falling tile pushes the standing tile beside it in the same direction, which then falls too, and so on. A standing tile pushed from both sides at the same instant stays standing. A tile already fallen is unaffected by anything that reaches it later.

Return the row once everything has settled.

Examples

Example 1

Input: tiles = "..R.."
Output: "..RRR"

The pushed tile topples everything to its right, one after another. The two standing tiles to its left have nothing pushing them at all.

Example 2

Input: tiles = "R.L"
Output: "R.L"

The middle tile is reached from both sides at the same instant, so it stays standing.

Example 3

Input: tiles = "L..R.."
Output: "L..RRR"

The leftward push at the front has nothing behind it to topple. The two standing tiles between the pushes are pushed apart rather than together, so neither falls. The rightward push topples everything after it.

Constraints

1 <= tiles.length <= 10^5
Every character of tiles is 'L', 'R' or '.'.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def push_dominoes(tiles: str) -> str:

Java

public String pushDominoes(String tiles)

The intended approach

Time O(n) over the row's length.Space O(n) for the settled row.

Only the pushed tiles matter, and each stretch of standing tiles is decided entirely by the pushes at its two ends. So walk the pushed tiles in order and settle the stretch between each pair of neighbours. Four cases cover it. A stretch between a rightward push and a leftward one is squeezed from both sides: the tiles fall inward from each end at the same rate, and with an odd number of tiles the middle one is reached from both sides at once and stays standing. A stretch between two pushes in the same direction falls entirely that way, since the far push cannot reach past the near one. The stretch before the first push falls only if that push is leftward, and the stretch after the last push only if that push is rightward. Treating the position just past the end as a rightward push, and the position before the start as a leftward one, folds those last two cases into the first two, so one walk with a pair of markers settles the whole row.

Pythonentry point: push_dominoes

def push_dominoes(tiles):
    n = len(tiles)
    out = list(tiles)
    prev_at = -1
    prev_push = 'L'
    for at in range(n + 1):
        push = tiles[at] if at < n else 'R'
        if push == '.':
            continue
        if prev_push == 'R' and push == 'L':
            lo = prev_at + 1
            hi = at - 1
            while lo < hi:
                out[lo] = 'R'
                out[hi] = 'L'
                lo += 1
                hi -= 1
        elif prev_push == 'R' and push == 'R':
            for k in range(prev_at + 1, at):
                out[k] = 'R'
        elif prev_push == 'L' and push == 'L':
            for k in range(prev_at + 1, at):
                out[k] = 'L'
        prev_at = at
        prev_push = push
    return "".join(out)

The obvious version

Run time forward instead. At each instant, look at every standing tile and topple it when exactly one of its neighbours is a fallen tile pushing towards it, taking care to work out every tile's next state from the current one so simultaneous pushes are handled together. Repeat until an instant changes nothing. Costs an instant per stretch of tiles rather than one walk.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_push_dominoes(tiles):
    n = len(tiles)
    row = list(tiles)
    while True:
        nxt = list(row)
        changed = False
        for at in range(n):
            if row[at] != '.':
                continue
            from_left = at > 0 and row[at - 1] == 'R'
            from_right = at < n - 1 and row[at + 1] == 'L'
            if from_left and not from_right:
                nxt[at] = 'R'
                changed = True
            elif from_right and not from_left:
                nxt[at] = 'L'
                changed = True
        if not changed:
            return "".join(row)
        row = nxt

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in