Push Dominoes Leetcode Problem 838 [Python Solution]

In this article, we’re going to tackle the Push Dominoes Leetcode problem, which falls under the category of Arrays & Hashing.

The problem description can be found here.

Problem Overview

You are given a string representing the initial state of dominoes.

Each domino can be in one of three states: standing straight up (represented by a ‘.’), leaning to the left (represented by ‘L’), or leaning to the right (represented by ‘R’).

After each second, the dominoes that are falling to the left will push adjacent dominoes on their left, and dominoes falling to the right will push their adjacent dominoes on the right.

When a vertical domino has dominoes falling on it from both sides, it remains still due to the balance of forces.

Your task is to find the final state of the dominoes after all the pushing occurs.

Constraints

• The length of the input string dominoes is denoted as ‘n’.
• 1 <= n <= 105
• The characters in the dominoes string can be ‘L’, ‘R’, or ‘.’

Efficient Python Code Solution

Here’s a Python solution to the Push Dominoes problem:

def pushDominoes(dominoes: str) -> str:
    dom = list(dominoes)
    q = collections.deque()

    # Add dominoes that are not standing straight up to the queue
    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)

The time complexity of this solution is O(n), and the space complexity is also O(n) because we use a queue to process the dominoes.

Reasoning Behind Our Approach

The idea behind this solution is to simulate the process of dominoes falling.

We start by converting the input string into a list to make it easier to update the characters.

Then, we use a deque (double-ended queue) to keep track of the dominoes that need to be processed.

We iterate through the list of dominoes, adding any domino that is not standing straight up to the queue.

After that, we simulate the dominoes falling by continuously processing the queue.

If a domino is leaning to the left (‘L’), we check if there is an empty space to its left and update it accordingly.

If a domino is leaning to the right (‘R’), we check if there is an empty space to its right and update it accordingly.

The key insight here is that we can process the dominoes from left to right, and we don’t need to revisit a domino that has already been processed.

This ensures that the final state of the dominoes is accurately determined.

#

Related Interview Questions By Company:

• Maximum Product Subarray LeetCode
• Insert Delete Get Random O(1) LeetCode
• Number Of Subsequences That Satisfy The Given Sum Condition LeetCode

Related Interview Questions By Difficulty:

• Number Of Pairs Of Interchangeable Rectangles LeetCode
• Sort Colors LeetCode
• Next Greater Element I LeetCode

Related Interview Questions By Category:

• Path Sum LeetCode
• Permutations II LeetCode
• Maximum Sum Circular Subarray LeetCode

Conclusion

In this article, we’ve addressed the Push Dominoes problem from LeetCode, providing a Python solution and explaining the reasoning behind our approach.

This solution efficiently simulates the process of dominoes falling, ensuring that the final state of the dominoes is correctly determined.

We hope this guide has been helpful in understanding the problem and how to solve it.

Feel free to comment, ask questions, make suggestions, and share this content with others who might find it useful.

Happy coding!