Push Dominoes
Medium · Two Pointers · Explanation and code example
Iteration (Greedy)
How it works
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.
Steps
- Track the count of consecutive dots and whether we've seen an unresolved 'R'.
- 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'.
- 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.
- Handle trailing dots at the end based on whether an 'R' is active.
- Return the constructed result.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)for only the output string.
Things to watch for
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.
Python code example
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)
C++ code example
class Solution {
public:
string pushDominoes(string dominoes) {
string res = "";
int dots = 0;
bool R = false;
for (char d : dominoes) {
if (d == '.') {
dots++;
} else if (d == 'R') {
if (R) {
// Previous was 'R', and current is also 'R'.
// Append 'R' for all the dots between them.
res += string(dots + 1, 'R');
} else if (dots > 0) {
// Previous was not 'R'. The previous dots remain unchanged.
res += string(dots, '.');
}
dots = 0;
R = true; // Current is 'R'.
} else {
if (R) {
// Append the previous 'R'.
res += 'R';
if (dots > 0) {
// Half the dots are affected by the previous 'R'.
res += string(dots / 2, 'R');
// Add a '.' if there's an odd number of dots.
if (dots % 2 != 0) {
res += '.';
}
// Append half the dots as 'L'.
res += string(dots / 2, 'L');
}
// Append the current 'L'.
res += 'L';
R = false;
dots = 0;
} else {
// There is no 'R' on the left.
// Append 'L' for all the dots and the current 'L'.
res += string(dots + 1, 'L');
dots = 0;
}
}
}
if (R) {
// Trailing dots are affected by the last 'R'.
res += string(dots + 1, 'R');
} else {
// Trailing dots remain unchanged as there is no previous 'R'.
res += string(dots, '.');
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.