We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Push Dominoes

Difficulty: Medium

Problem Description

Given a string representing the initial state of dominoes, where 'L' indicates a domino pushed to the left, 'R' indicates a domino pushed to the right, and '.' indicates a vertical domino, return a string representing the final state after all dominoes have fallen.

Key Insights

  • Dominoes falling to the left ('L') and right ('R') will influence adjacent dominoes.
  • An upright domino will fall if influenced by only one side; if influenced by both, it remains upright.
  • The problem can be effectively solved using a two-pointer or simulation approach to track the effect of falling dominoes over time.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a simulation approach where we iterate through the string to determine the final state of each domino:

  1. Traverse the dominoes from left to right to determine how far the influence of 'R' extends.
  2. Traverse the dominoes from right to left to determine how far the influence of 'L' extends.
  3. Combine the results considering the influence from both sides.

This approach ensures that we accurately model the falling behavior of the dominoes.

Code Solutions

def pushDominoes(dominoes: str) -> str:
    n = len(dominoes)
    result = list(dominoes)
    # First pass: handle 'R' influences
    force = 0
    for i in range(n):
        if dominoes[i] == 'R':
            force = n  # Resetting the force to n (maximum influence)
        elif dominoes[i] == 'L':
            force = 0  # Resetting force
        else:
            force = max(force - 1, 0)  # Decrease force as we move
        if force > 0:
            result[i] = 'R'

    # Second pass: handle 'L' influences
    force = 0
    for i in range(n - 1, -1, -1):
        if dominoes[i] == 'L':
            force = n  # Resetting the force to n (maximum influence)
        elif dominoes[i] == 'R':
            force = 0  # Resetting force
        else:
            force = max(force - 1, 0)  # Decrease force as we move
        if force > 0:
            if result[i] == 'R':
                result[i] = '.'  # Both sides push, remains upright
            else:
                result[i] = 'L'

    return ''.join(result)
← Back to All Questions