LeetCode 838 - Push Dominoes

This problem models a chain reaction of falling dominoes. We are given a string where each character represents the initial state of a domino in a row. A domino can be in one of three states: - 'L' means the domino has been pushed to the left.

leetcodemediumtwo-pointersstringdynamic-programming

LeetCode Problem 838

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Dynamic Programming

Solution

Problem Understanding

This problem models a chain reaction of falling dominoes. We are given a string where each character represents the initial state of a domino in a row.

A domino can be in one of three states:

  • 'L' means the domino has been pushed to the left.
  • 'R' means the domino has been pushed to the right.
  • '.' means the domino is standing upright and has not yet been pushed.

The important detail is that all initially pushed dominoes start moving at the same time. Every second, a falling domino transfers force to its adjacent domino in the direction of motion. A domino falling left pushes the domino immediately to its left, and a domino falling right pushes the domino immediately to its right.

However, if a standing domino receives equal force from both directions at the same time, the forces cancel out and the domino remains upright.

The goal is to compute the final stable arrangement after all motion stops.

For example:

Input: ".L.R...LR..L.."

Some dominoes fall immediately, others get affected later by chain reactions, and some remain standing because opposing forces balance each other. The final output becomes:

"LL.RR.LLRRLL.."

The constraints tell us that the string length can be as large as 10^5. This is important because it rules out inefficient simulation approaches that repeatedly update the dominoes second by second. An algorithm with quadratic complexity would likely time out. We need something close to linear time.

Several edge cases can easily break a naive implementation:

  • Dominoes with no forces at all, such as "...", should remain unchanged.
  • Consecutive pushes in the same direction, such as "R....", should propagate all the way.
  • Opposing pushes like "R...L" require careful handling because dominoes in the middle may balance.
  • Equal distance collisions, such as "R.L", must preserve the center domino if forces meet simultaneously.
  • Leading or trailing dots, such as "...L" or "R...", need special treatment because force only comes from one side.

Approaches

Brute Force Simulation

A straightforward idea is to simulate the dominoes second by second.

At each time step, we scan the row and determine which dominoes will fall next based on their neighbors. Since all changes happen simultaneously, we must compute updates into a temporary structure instead of modifying the row in place.

For example, if a domino receives force from only the left side, it becomes 'R'. If it receives force from only the right side, it becomes 'L'. If it receives force from both sides simultaneously, it stays upright.

We repeat this process until no domino changes state.

This approach is correct because it directly follows the rules of the problem. However, it is inefficient. In the worst case, force may propagate one domino per second across the entire row, and each iteration scans all n dominoes. This leads to quadratic complexity.

Key Insight for an Optimal Solution

Instead of simulating every second, we can think in terms of forces between already determined dominoes.

The key observation is that only the nearest non-dot dominoes matter.

Consider segments between force sources:

R.....R

Both ends push right, so every domino in the middle becomes 'R'.

L.....L

Both ends push left, so everything becomes 'L'.

L.....R

The forces point away from each other, so nothing changes.

R.....L

The forces move toward each other. Dominoes closer to R fall right, dominoes closer to L fall left, and the middle domino remains upright if the gap length is odd.

We can process the string by treating 'L' and 'R' as boundaries and resolving the segment between them in one pass.

A common trick is to add virtual boundaries:

  • Add a virtual 'L' before the string.
  • Add a virtual 'R' after the string.

This eliminates edge-case handling for prefixes and suffixes.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates domino motion second by second
Optimal O(n) O(n) Resolves intervals between force sources directly

Algorithm Walkthrough

We will use a two-pointer approach that processes segments between meaningful dominoes.

  1. Convert the input string into a list of characters so it can be modified efficiently.
  2. Add virtual boundaries conceptually:
  • Treat the left side as if there is an 'L' before index 0.
  • Treat the right side as if there is an 'R' after the last index.

This prevents special logic for prefixes and suffixes. 3. Scan through the dominoes and identify every non-dot character ('L' or 'R'). 4. Keep track of the previous force source using a pointer left. 5. Whenever another force source is found at right, resolve the segment between left and right.

There are four possible cases:

Case 1: Same directions

If both boundaries are 'L' or both are 'R', every domino in the middle falls in the same direction.

Example:

R....R

becomes:

RRRRRR

because the force keeps propagating consistently.

Case 2: Left boundary is 'L' and right boundary is 'R'

Example:

L....R

The forces move outward, so the middle dominoes never receive any force.

No changes are needed.

Case 3: Left boundary is 'R' and right boundary is 'L'

Example:

R.....L

The forces move toward each other.

Fill dominoes symmetrically:

  • Left side becomes 'R'
  • Right side becomes 'L'
  • Stop when pointers meet

If there is an odd number of dominoes between them, the center stays upright. 6. Update the left pointer to the current force source and continue scanning. 7. Convert the modified character list back into a string.

Why it works

The algorithm works because every domino's final state depends only on the nearest force coming from the left and right. By processing intervals between consecutive non-dot dominoes, we completely determine the outcome of every undecided domino exactly once. Since intervals do not overlap and every case is resolved according to the physical rules of force propagation, the resulting configuration is guaranteed to be correct.

Python Solution

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        chars = ['L'] + list(dominoes) + ['R']
        left = 0

        for right in range(1, len(chars)):
            if chars[right] == '.':
                continue

            if right - left > 1:
                if chars[left] == chars[right]:
                    for i in range(left + 1, right):
                        chars[i] = chars[left]

                elif chars[left] == 'R' and chars[right] == 'L':
                    l = left + 1
                    r = right - 1

                    while l < r:
                        chars[l] = 'R'
                        chars[r] = 'L'
                        l += 1
                        r -= 1

            left = right

        return ''.join(chars[1:-1])

The implementation begins by creating a mutable list of characters and inserting virtual boundaries. We prepend 'L' and append 'R', which simplifies handling dominoes at the edges.

The variable left stores the index of the previous force source. We then iterate using right to locate the next non-dot domino.

Whenever a valid boundary pair is found, we resolve the segment between them. If both directions match, the entire interval gets filled with the same force. If the interval is bounded by 'R' and 'L', we use two inward-moving pointers to assign 'R' and 'L' symmetrically.

Finally, we remove the artificial boundaries and reconstruct the string.

Go Solution

func pushDominoes(dominoes string) string {
	chars := make([]byte, 0, len(dominoes)+2)
	chars = append(chars, 'L')
	chars = append(chars, []byte(dominoes)...)
	chars = append(chars, 'R')

	left := 0

	for right := 1; right < len(chars); right++ {
		if chars[right] == '.' {
			continue
		}

		if right-left > 1 {
			if chars[left] == chars[right] {
				for i := left + 1; i < right; i++ {
					chars[i] = chars[left]
				}
			} else if chars[left] == 'R' && chars[right] == 'L' {
				l, r := left+1, right-1

				for l < r {
					chars[l] = 'R'
					chars[r] = 'L'
					l++
					r--
				}
			}
		}

		left = right
	}

	return string(chars[1 : len(chars)-1])
}

The Go solution follows the exact same logic as the Python implementation. Since Go strings are immutable, we convert the input into a mutable []byte slice. This allows in-place modification of domino states.

Unlike Python lists, Go slices require explicit construction and appending. Otherwise, the algorithm remains identical. Integer overflow is not a concern because indices remain bounded by 10^5.

Worked Examples

Example 1

Input: "RR.L"

After adding virtual boundaries:

L R R . L R
left right Left Char Right Char Action
0 1 L R No gap
1 2 R R No gap
2 4 R L Middle contains . but forces meet immediately
4 5 L R No gap

Result:

RR.L

The second domino is already falling right, so the first domino does not exert extra force on it.

Example 2

Input: ".L.R...LR..L.."

After adding boundaries:

L . L . R . . . L R . . L . . R

Step 1

Boundary pair:

L . L

Same direction (L, L):

L L L

State becomes:

LL.R...LR..L..

Step 2

Boundary pair:

L . R

Forces move outward, no change.

State remains:

LL.R...LR..L..

Step 3

Boundary pair:

R . . . L

Opposing forces:

  • Left side becomes R
  • Right side becomes L
  • Middle remains .

Result:

LL.RR.LLR..L..

Step 4

Boundary pair:

L R

No middle dominoes.

Step 5

Boundary pair:

R . . L

Opposing forces:

R R L L

State becomes:

LL.RR.LLRRLL..

Step 6

Trailing dots remain unchanged.

Final result:

LL.RR.LLRRLL..

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every domino is processed at most once
Space O(n) Character array is used for in-place modification

The algorithm runs in linear time because each index participates in at most one interval resolution. Even in the inward two-pointer case, every domino is assigned once. The extra space comes from converting the string into a mutable character array and adding sentinel boundaries.

Test Cases

solution = Solution()

assert solution.pushDominoes("RR.L") == "RR.L"  # Provided example
assert solution.pushDominoes(".L.R...LR..L..") == "LL.RR.LLRRLL.."  # Provided example

assert solution.pushDominoes(".") == "."  # Single upright domino
assert solution.pushDominoes("L") == "L"  # Single left push
assert solution.pushDominoes("R") == "R"  # Single right push

assert solution.pushDominoes("....") == "...."  # No forces applied
assert solution.pushDominoes("R....") == "RRRRR"  # Right propagation
assert solution.pushDominoes("....L") == "LLLLL"  # Left propagation

assert solution.pushDominoes("R.L") == "R.L"  # Balanced collision
assert solution.pushDominoes("R...L") == "RR.LL"  # Odd gap collision
assert solution.pushDominoes("R....L") == "RRRLLL"  # Even gap collision

assert solution.pushDominoes("L....R") == "L....R"  # Outward forces
assert solution.pushDominoes("R.R.L") == "RRR.L"  # Multiple separated pushes
assert solution.pushDominoes("..R...") == "..RRRR"  # Trailing propagation
assert solution.pushDominoes("...L..") == "LLLL.."  # Leading propagation

Test Summary

Test Why
"RR.L" Validates provided example
".L.R...LR..L.." Validates complex chain reaction
"." Smallest possible input
"L" Single forced domino left
"R" Single forced domino right
"...." No force propagation
"R...." Rightward propagation across suffix
"....L" Leftward propagation across prefix
"R.L" Balanced opposing forces
"R...L" Odd-length collision
"R....L" Even-length collision
"L....R" Outward forces leave dominoes unchanged
"R.R.L" Multiple disconnected force regions
"..R..." Right push affects trailing dominoes
"...L.." Left push affects leading dominoes

Edge Cases

Balanced Collision Between Opposing Forces

An input like:

"R.L"

is easy to mishandle because the middle domino receives force from both sides at the same moment. A naive implementation may accidentally favor one direction. Our implementation handles this correctly because the inward two-pointer loop only executes while l < r. When the pointers meet in the center, that domino remains '.'.

No External Force

Inputs such as:

"...."

contain no 'L' or 'R' at all. Since there are no force sources, the dominoes should never move. The sentinel boundaries ensure the algorithm still works naturally, and no interval resolution changes any characters.

Leading and Trailing Domino Chains

Cases like:

"R...."

or

"....L"

can be problematic because force propagates only from one side. Without careful boundary handling, implementations often miss these sections. The virtual 'L' at the front and 'R' at the back elegantly solve this problem by converting edge segments into ordinary intervals processed by the same logic as the middle of the string.