How do you solve Push Dominoes on LeetCode?

Push Dominoes (LeetCode #838) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Dominoes pushed from both sides will remain upright.

What is the brute force solution for Push Dominoes?

The brute force approach for Push Dominoes is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate each second of the dominoes falling. We check each domino and see if it can fall based on its neighbors, repeating this until no more dominoes can fall. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Push Dominoes?

Push Dominoes uses the following concepts: Two Pointers, String, Dynamic Programming. The recommended patterns to study are: Two Pointers, Dynamic Programming.

What are the interview tips for Push Dominoes?

Think about edge cases, such as no dominoes falling. Explain your thought process clearly while coding. Use comments to clarify your logic, especially in complex loops.

What are common mistakes when solving Push Dominoes?

Not considering the case where a domino is pushed from both sides. Failing to update the state correctly in each iteration.

#838

Push Dominoes

Medium

Two PointersStringDynamic ProgrammingTwo PointersDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a single pass through the dominoes to determine the final state. We track the influence of 'R' and 'L' using a counter, allowing us to efficiently determine the final state of each domino.

⚙️

Algorithm

3 steps

1Step 1: Initialize an array to hold the final state of the dominoes.
2Step 2: Traverse the string and use a counter to track the influence of 'R' and 'L'.
3Step 3: Update the final state based on the counter values, determining if a domino falls left, right, or stays upright.

solution.py19 lines

1def pushDominoes(dominoes):
2    n = len(dominoes)
3    forces = [0] * n
4    for i in range(n):
5        if dominoes[i] == 'R':
6            forces[i] = 1
7        elif dominoes[i] == 'L':
8            forces[i] = -1
9    for i in range(1, n):
10        forces[i] += forces[i - 1]
11    result = []
12    for force in forces:
13        if force > 0:
14            result.append('R')
15        elif force < 0:
16            result.append('L')
17        else:
18            result.append('.')
19    return ''.join(result)

ℹ

Complexity note: This complexity is linear because we only make a constant number of passes over the dominoes, and the space complexity is linear due to the additional array used to track forces.

1Dominoes pushed from both sides will remain upright.
2The influence of 'R' and 'L' can be tracked using a counter.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.