838. Push Dominoes - Explanation

Problem Link



1. Brute Force

Intuition

For each standing domino (represented by '.'), we need to determine which force, if any, will knock it over. We look for the nearest 'R' to the left and the nearest 'L' to the right. If only one force reaches this domino, it falls in that direction. If both forces reach it, the closer one wins. If they are equidistant, the forces cancel out and the domino stays upright.

Algorithm

  1. Iterate through each position in the string.
  2. For each '.', search left to find the nearest non-'.' character and search right to find the nearest non-'.' character.
  3. Determine the final state based on which forces apply:
    • If 'R' is on the left and 'L' is on the right, compare distances. The closer force wins, or they cancel if equidistant.
    • If only 'R' is on the left, the domino falls right.
    • If only 'L' is on the right, the domino falls left.
  4. Return the resulting string.
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        res = list(dominoes)

        for i in range(n):
            if dominoes[i] != '.':
                continue

            l, r = i - 1, i + 1

            while l >= 0 and dominoes[l] == '.':
                l -= 1

            while r < n and dominoes[r] == '.':
                r += 1

            left_force = dominoes[l] if l >= 0 else None
            right_force = dominoes[r] if r < n else None

            if left_force == 'R' and right_force == 'L':
                if (i - l) < (r - i):
                    res[i] = 'R'
                elif (r - i) < (i - l):
                    res[i] = 'L'
            elif left_force == 'R':
                res[i] = 'R'
            elif right_force == 'L':
                res[i] = 'L'

        return "".join(res)

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n) for only the output string.

2. Force From Left & Right

Intuition

Instead of checking neighbors for each domino individually, we can precompute how far each position is from the nearest pushing force. We make two passes: one from left to right tracking distance from the last 'R', and one from right to left tracking distance from the last 'L'. At each position, we compare these distances to determine which force dominates.

Algorithm

  1. Create two arrays left and right initialized to infinity.
  2. Left-to-right pass: track the distance from the most recent 'R'. Reset when hitting 'L'.
  3. Right-to-left pass: track the distance from the most recent 'L'. Reset when hitting 'R'.
  4. For each position, compare left[i] and right[i]:
    • If left[i] < right[i], the domino falls left.
    • If right[i] < left[i], the domino falls right.
    • If equal, forces cancel and it stays upright.
  5. Return the result string.
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        left = [float('inf')] * n
        right = [float('inf')] * n
        res = list(dominoes)

        force = float('inf')
        for i in range(n):
            if dominoes[i] == 'R':
                force = 0
            elif dominoes[i] == 'L':
                force = float('inf')
            else:
                force += 1
            right[i] = force

        force = float('inf')
        for i in range(n - 1, -1, -1):
            if dominoes[i] == 'L':
                force = 0
            elif dominoes[i] == 'R':
                force = float('inf')
            else:
                force += 1
            left[i] = force

        for i in range(n):
            if left[i] < right[i]:
                res[i] = 'L'
            elif right[i] < left[i]:
                res[i] = 'R'

        return "".join(res)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Simulation (Queue)

Intuition

We can simulate the dominoes falling in real time using a queue. Initially, all dominoes that are already pushed ('L' or 'R') are added to the queue. We process them one by one, pushing adjacent dominoes as they fall. The key insight is handling collisions: when 'R' meets 'L' with one standing domino between them, that domino stays upright.

Algorithm

  1. Initialize a queue with all positions that have 'R' or 'L'.
  2. Process each element from the queue:
    • For 'L': if the position to the left is '.', mark it as 'L' and add to queue.
    • For 'R': if the position to the right is '.', check if a collision with 'L' is about to happen. If so, skip both. Otherwise, mark it as 'R' and add to queue.
  3. The collision check looks two positions ahead to see if an 'L' is coming.
  4. Return the modified string.
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        dom = list(dominoes)
        q = deque()

        for i, d in enumerate(dom):
            if d != ".":
                q.append((i, d))

        while q:
            i, d = q.popleft()

            if d == "L" and i > 0 and dom[i - 1] == ".":
                q.append((i - 1, "L"))
                dom[i - 1] = "L"
            elif d == "R":
                if i + 1 < len(dom) and dom[i + 1] == ".":
                    if i + 2 < len(dom) and dom[i + 2] == "L":
                        q.popleft()
                    else:
                        q.append((i + 1, "R"))
                        dom[i + 1] = "R"

        return "".join(dom)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Iteration (Greedy)

Intuition

We can process the string in one pass by tracking whether we've seen an 'R' that might affect upcoming dominoes. As we iterate, we count consecutive dots and decide their fate when we hit an 'L' or 'R'. The key cases are: dots between 'R' and 'L' split in half, dots after 'R' all fall right, and dots before 'L' (with no prior 'R') all fall left.

Algorithm

  1. Track the count of consecutive dots and whether we've seen an unresolved 'R'.
  2. When encountering 'R':
    • If a previous 'R' exists, all dots since then fall right.
    • Otherwise, keep the dots as is.
    • Mark that we now have an active 'R'.
  3. When encountering 'L':
    • If a previous 'R' exists, split the dots: half fall right, half fall left, with a possible middle dot staying upright if the count is odd.
    • Otherwise, all dots and the current 'L' fall left.
  4. Handle trailing dots at the end based on whether an 'R' is active.
  5. Return the constructed result.
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        res = []
        dots = 0
        R = False

        for d in dominoes:
            if d == '.':
                dots += 1
            elif d == 'R':
                if R:
                    # Previous was 'R', and current is also 'R'.
                    # Append 'R' for all the dots between them.
                    res.append('R' * (dots + 1))
                elif dots > 0:
                    # Previous was not 'R'. The previous dots remain unchanged.
                    res.append('.' * dots)
                dots = 0
                R = True  # Current is 'R'
            else:
                if R:
                    # Append the previous 'R'.
                    res.append('R')
                    if dots > 0:
                        # Half the dots are affected by the previous 'R'.
                        res.append('R' * (dots // 2))

                        # Add a '.' if there's an odd number of dots.
                        if (dots % 2) != 0:
                            res.append('.')

                        # Append half the dots as 'L'.
                        res.append('L' * (dots // 2))

                    # Append the current 'L'.
                    res.append('L')
                    R, dots = False, 0
                else:
                    # There is no 'R' on the left.
                    # Append 'L' for all the dots and the current 'L'.
                    res.append('L' * (dots + 1))
                    dots = 0

        if R:
            # Trailing dots are affected by the last 'R'.
            res.append('R' * (dots + 1))
        else:
            # Trailing dots remain unchanged as there is no previous 'R'.
            res.append('.' * dots)

        return ''.join(res)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for only the output string.

Common Pitfalls

Ignoring Force Cancellation

When an 'R' force from the left and an 'L' force from the right reach the same domino at equal distances, they cancel out and the domino remains upright. Failing to handle this case by always picking one direction produces incorrect results for inputs like "R...L" where the middle dot should stay as '.'.

Not Handling Boundary Cases

Dominoes at the edges may only have force from one direction. A domino with 'R' to its left but no 'L' to its right should fall right indefinitely. Similarly, 'L' without a preceding 'R' affects all dots to its left. Forgetting to check boundary conditions leads to index errors or missed updates.

Incorrect Distance Comparison

When comparing distances from 'R' and 'L' forces, using the wrong comparison operator or miscalculating distances leads to dominoes falling in the wrong direction. The closer force wins, so if distanceFromR < distanceFromL, the domino falls right, not left.