Problem Informations

• Problem Index: 838
• Problem Link: Push Dominoes
• Topics: Two Pointers, String, Dynamic Programming

Problem Description

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

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

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

• dominoes[i] = 'L', if the $i^{th}$ domino has been pushed to the left,
• dominoes[i] = 'R', if the $i^{th}$ domino has been pushed to the right, and
• dominoes[i] = '.', if the $i^{th}$ domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: dominoes = “RR.L”
Output: “RR.L”
Explanation: The first domino expends no additional force on the second domino.

Example 2:

Input: dominoes = “.L.R…LR..L..”
Output: “LL.RR.LLRRLL..”

Constraints:

• $n == \text{dominoes.length}$
• $1 \leq n \leq 10^5$
• dominoes[i] is either 'L', 'R', or '.'.

Intuition

The problem is essentially simulating the behavior of dominoes falling over time based on initial pushes, either to the left (‘L’) or right (‘R’). Every domino either maintains its position when it receives equal force from both sides or continues falling in the direction of the stronger side’s force. By understanding and simulating these pushes and allowing for subsequent chain reactions, we can predict the final state of the dominoes. Given the constraints, an efficient solution needs to traverse the domino sequence systematically, capturing the interactions between ‘L’ and ‘R’ dominoes from left to right while avoiding unnecessary repeats of the same conditions.

Approach

1. Initialization: We prepend an ‘L’ at the start and append an ‘R’ at the end of the dominoes string to simplify boundary conditions, ensuring that each domino has a defined influencing force from both ends. This allows our simulation to consider transitions cleanly without special case handling for the beginning and end of the sequence.

2. State Tracking: Use two pointers, lastIdx to record the position of the most recent ‘L’ or ‘R’ seen as we traverse the domino string from left to right with index i.

3. Simulation Process:

   • As we iterate through each character in the string:
     • If we encounter an ‘L’ at position i:
       • Check if the last impacting domino was ‘R’. If so, fill the gap from lastIdx + 1 to i - 1 with ‘R’ and ‘L’ converging inward until they meet.
       • If the last impacting domino was also ‘L’ (or has no affecting ‘R’), simply fill from lastIdx + 1 to i with ‘L’, as there’s no opposing force.
     • If we encounter an ‘R’, and the last impacting domino was ‘R’, fill from lastIdx + 1 to i entirely with ‘R’ since there’s no opposing leftward force interfering.

4. Completion: Continue this process until reaching the artificially appended ‘R’. The sequence now should have all forces applied according to the domino effect rules and appended extremity guards stripped away.

5. Result Construction: Construct and return the final domino arrangement excluding the extra ‘L’ and ‘R’ that were added to simplify boundary conditions.

This approach ensures all interactions are processed in a single pass with complexity $O(n)$, which is efficient given the constraints.

Code

C++

class Solution {
public:
    string pushDominoes(string dominoes) {
        // Add 'L' at the beginning and 'R' at the end to handle edge cases
        dominoes = 'L' + dominoes + 'R';

        int lastIdx = 0;  // Last position of 'L' or 'R'
        int len = dominoes.size();

        for (int i = 1; i < len; ++i) {
            char current = dominoes[i];
            
            if (current == 'L') {
                if (dominoes[lastIdx] == 'R') {
                    // There were 'R's before and now an 'L', so push inward
                    int low = lastIdx + 1, high = i - 1;
                    while (low < high) {
                        dominoes[low++] = 'R';
                        dominoes[high--] = 'L';
                    }
                } else {
                    // Fill all dominoes between last 'L' or start and current 'L' with 'L'
                    fill(dominoes.begin() + lastIdx + 1, dominoes.begin() + i, 'L');
                }
                lastIdx = i;
            } else if (current == 'R') {
                if (dominoes[lastIdx] == 'R') {
                    // Fill all dominoes between last 'R' and current 'R' with 'R'
                    fill(dominoes.begin() + lastIdx + 1, dominoes.begin() + i, 'R');
                }
                lastIdx = i;
            }
        }

        // Return the result excluding the added 'L' and 'R'
        return dominoes.substr(1, len - 2);
    }
};

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        # Add 'L' at the beginning and 'R' at the end to handle edge cases
        dominoes = 'L' + dominoes + 'R'

        lastIdx = 0  # Last position of 'L' or 'R'
        len_dominoes = len(dominoes)

        for i in range(1, len_dominoes):
            current = dominoes[i]
            
            if current == 'L':
                if dominoes[lastIdx] == 'R':
                    # There were 'R's before and now an 'L', so push inward
                    low = lastIdx + 1
                    high = i - 1
                    while low < high:
                        dominoes = dominoes[:low] + 'R' + dominoes[low + 1:]
                        dominoes = dominoes[:high] + 'L' + dominoes[high + 1:]
                        low += 1
                        high -= 1
                else:
                    # Fill all dominoes between last 'L' or start and current 'L' with 'L'
                    dominoes = dominoes[:lastIdx + 1] + 'L' * (i - lastIdx - 1) + dominoes[i:]
                lastIdx = i
            elif current == 'R':
                if dominoes[lastIdx] == 'R':
                    # Fill all dominoes between last 'R' and current 'R' with 'R'
                    dominoes = dominoes[:lastIdx + 1] + 'R' * (i - lastIdx - 1) + dominoes[i:]
                lastIdx = i

        # Return the result excluding the added 'L' and 'R'
        return dominoes[1:len_dominoes - 1]

Complexity

• Time complexity: $O(n)$

  The algorithm processes the string containing the dominoes in a single pass, examining each character exactly once. This is achieved through a loop that iterates from the beginning to the end of the string, leading to a linear time complexity relative to the length of the string $n$. Within the loop, operations such as setting characters within the string or filling a range with specific characters are constant time operations, summing to an overall complexity of $O(n)$.

• Space complexity: $O(n)$

  The space complexity is driven by the storage requirements needed to hold the modified string of dominoes. The algorithm extends the original string by two characters (‘L’ at the beginning and ‘R’ at the end) to account for edge cases. Therefore, the space needed is proportional to $n + 2$, which simplifies to $O(n)$ when considering asymptotic complexity. This additional space usage is minimal and scales linearly with the input size.