Push Dominoes - Leetcode Solution

Problem Statement:

You are given a string of characters representing a row of dominoes. Each character represents the initial position of a domino. The character 'L' represents a domino that is falling to the left, the character 'R' represents a domino that is falling to the right, and the character '.' represents a domino that is standing upright.

You are to simulate the falling of the dominoes by applying the following rules:

1. A domino that falls to the right remains upright if it is not pushed.
2. A domino that falls to the right is knocked over if it is pushed by a falling domino.
3. A domino that falls to the left remains upright if it is not pushed.
4. A domino that falls to the left is knocked over if it is pushed by a falling domino.
5. A domino that is standing upright remains upright.

Write a function to return the final state of the dominoes after all the dominos have fallen. The input is a string of length n (1 ≤ n ≤ 10^5) representing the initial state of the row of dominoes.

Solution:

To solve the problem, we can simulate the falling of the dominoes using a loop. We can start by initializing two variables to keep track of the current state of the row of dominoes: left and right. We can initialize left to '.', and right to the first character of the input string.

We can then iterate through the input string and apply the rules of the problem to determine the final state of each domino.

If the current character is 'R', we can update the value of right. If right is 'L', then the previous domino is pushed and we need to determine the final state of both dominos. We can update the final state of the previous domino to 'L' and the current domino to 'R'.

If the current character is 'L', we can update the value of left. If left is 'R', then the previous domino is pushed and we need to determine the final state of both dominos. We can update the final state of the previous domino to 'R' and the current domino to 'L'.

If the current character is '.', then we need to check if either left or right is 'R' or 'L'. If either left or right is 'R', then the current domino is knocked over and we update it to 'R'. If either left or right is 'L', then the current domino is knocked over and we update it to 'L'.

We can then return the final state of the row of dominoes after iterating through the input string.

Here is the Python code for the solution:

def pushDominoes(dominoes: str) -> str: n = len(dominoes) states = ['.' for _ in range(n)] left, right = '.', dominoes[0] for i in range(1,n): if dominoes[i] == 'R': right = 'R' if left == 'R': states[i-1] = 'R' right = '.' elif dominoes[i] == 'L': left = 'L' if right == 'L': for j in range((i-1+1)>>1): states[i-1-j] = 'L' states[j] = 'R' left = '.' right = '.' else: if right == 'L': states[i] = 'L' elif left == 'R': states[i] = 'R' if right == 'R': states[i] = 'R' elif left == 'L': states[i] = 'L' if right == 'L': states[n-1] = 'L' return ''.join(states)

Complexity Analysis:

Time Complexity: O(n)

The time complexity of the solution is O(n) as we iterate through the input string of length n only once.

Space Complexity: O(n)

The space complexity of the solution is O(n) as we use an extra array of length n to store the final state of the row of dominoes.

1