Push Dominoes

Problem

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 ith domino has been pushed to the left,
• dominoes[i] = 'R', if the ith domino has been pushed to the right, and
• dominoes[i] = '.', if the ith domino has not been pushed.

Return a string representing the final state.

Examples

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 == dominoes.length
• 1 <= n <= 105
• dominoes[i] is either 'L', 'R', or '.'.

Solution

Method 1 - Using count arrays From left and right

First, we iterate the dominoes twice.

1. During the first pass (left to right), we determine which dominoes may fall to the right. So, whenever we encounter 'R' , we know that the next dominoes may fall rightwards, so we save in the 'right' vector the distance from the previous 'R'. (Until we reach a 'L').
2. In the second pass (right to left), we apply the same logic to dominoes falling leftward and store their distances in the 'left' array.

Example:

Position	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Dominoes	.	L	.	R	.	.	.	L	R	.	.	L	.	.
Right Array	0	0	0	0	1	2	3	0	0	1	2	0	0	0
Left Array	1	0	0	0	3	2	1	0	0	2	1	0	0	0

3. Next step is to compare 'right and 'left'. For each i:
   1. If both forces are 0, the original state of the domino remains unchanged.
   2. If right[i] is 0 but left[i] is not, the domino falls to the left, and vice versa.
   3. if both forces are equal, the domino stays upright due to balanced forces.
   4. For unequal forces, the domino falls towards the closer side, determined by the smaller force value.

Code

Java

class Solution {
	public String pushDominoes(String dominoes) {
		int n = dominoes.length();
		int[] left = new int[n];
		int[] right = new int[n];
		char prev = '.';
		int count = 0;
		for (int i = 0; i < n; i++) {
			char c = dominoes.charAt(i);
			if (c == 'R') {
				count = 1;
				prev = c;
			}else if(c == 'L') {
				count = 0;
				prev = c;
			}else if (c == '.' && prev == 'R'){
				right[i] = count++;
			}
		}
	
		prev = '.';
		for (int i = n - 1; i >= 0; i--) {
			char c = dominoes.charAt(i);
			if (c == 'L') {
				count = 1;
				prev = c;
			}else if(c == 'R') {
				count = 0;
				prev = c;
			}else if (c == '.' && prev == 'L'){
				left[i] = count++;
			}
		}
		char[] ans = new char[n];
		for (int i = 0; i < n; i++) {
			int L = left[i];
			int R = right[i];
			if (L == 0 && R == 0) {
				ans[i] = dominoes.charAt(i);
			} else if (L == 0) {
				ans[i] = 'R';
			} else if (R == 0) {
				ans[i] = 'L';
			} else if (L == R) {
				ans[i] = '.';
			}else if(L < R) {
				ans[i] = 'L';
			}else {
				ans[i] = 'R';
			}
		}
		return new String(ans);
	}
}

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        left: list[int] = [0] * n
        right: list[int] = [0] * n
        
        # Initial variables for tracking forces
        prev: str = '.'
        count: int = 0

        # Fill the 'right' array
        for i in range(n):
            c = dominoes[i]
            if c == 'R':
                count = 1
                prev = c
            elif c == 'L':
                count = 0
                prev = c
            elif c == '.' and prev == 'R':
                right[i] = count
                count += 1

        # Reset variables for tracking forces
        prev = '.'
        count = 0

        # Fill the 'left' array
        for i in range(n - 1, -1, -1):
            c = dominoes[i]
            if c == 'L':
                count = 1
                prev = c
            elif c == 'R':
                count = 0
                prev = c
            elif c == '.' and prev == 'L':
                left[i] = count
                count += 1

        # Determine the final state
        ans: list[str] = [''] * n
        for i in range(n):
            L = left[i]
            R = right[i]
            if L == 0 and R == 0:
                ans[i] = dominoes[i]
            elif L == 0:
                ans[i] = 'R'
            elif R == 0:
                ans[i] = 'L'
            elif L == R:
                ans[i] = '.'
            elif L < R:
                ans[i] = 'L'
            else:
                ans[i] = 'R'

        return ''.join(ans)

Complexity

• ⏰ Time complexity: O(n) due to 3 linear passes
• 🧺 Space complexity: O(n) for using the left and right forces and then using answer array as well

Method 2 - Use the single count array

The problem can be solved using forces to simulate the effect of domino pushes. Here's the approach:

1. Simulating Forces:

   • Each domino experiences a "force" resulting from being pushed to the left (L) or right (R).
   • The force will spread from a domino to its neighbours.
   • A domino subjected to equal and opposite forces stays upright.

2. Two-Pass Algorithm:

   • First pass calculates forces propagating to the right (R).
   • Second pass calculates counteracting forces propagating to the left (L).
   • Combine the forces to compute the final orientation.

This ensures we efficiently calculate the final state without explicitly simulating second-by-second movement.

Code

Java

class Solution {

    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        int[] forces = new int[n];
        int force = 0;

        // Calculate forces to the right caused by 'R'
        for (int i = 0; i < n; i++) {
            if (dominoes.charAt(i) == 'R') {
                force = n; // Apply large positive force
            } else if (dominoes.charAt(i) == 'L') {
                force = 0; // Reset force to zero for 'L'
            } else {
                force = Math.max(force - 1, 0); // Gradually decrease force
            }
            forces[i] += force;
        }

        // Calculate forces to the left caused by 'L'
        force = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (dominoes.charAt(i) == 'L') {
                force = n; // Apply large negative force
            } else if (dominoes.charAt(i) == 'R') {
                force = 0; // Reset force to zero for 'R'
            } else {
                force = Math.max(force - 1, 0); // Gradually decrease force
            }
            forces[i] -= force;
        }

        // Build the final state based on the forces
        StringBuilder ans = new StringBuilder();
        for (int f : forces) {
            if (f > 0) {
                ans.append('R');
            } else if (f < 0) {
                ans.append('L');
            } else {
                ans.append('.');
            }
        }

        return ans.toString();
    }
}

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        forces: list[int] = [0] * n
        
        # Calculate forces to the right caused by 'R'
        force = 0
        for i in range(n):
            if dominoes[i] == 'R':
                force = n  # Apply large positive force
            elif dominoes[i] == 'L':
                force = 0  # Reset force to zero for 'L'
            else:
                force = max(force - 1, 0)  # Gradually decrease force
            forces[i] += force
        
        # Calculate forces to the left caused by 'L'
        force = 0
        for i in range(n - 1, -1, -1):
            if dominoes[i] == 'L':
                force = n  # Apply large negative force
            elif dominoes[i] == 'R':
                force = 0  # Reset force to zero for 'R'
            else:
                force = max(force - 1, 0)  # Gradually decrease force
            forces[i] -= force
        
        # Build the final state based on the forces
        ans: list[str] = []
        for f in forces:
            if f > 0:
                ans.append('R')
            elif f < 0:
                ans.append('L')
            else:
                ans.append('.')
        
        return ''.join(ans)

Complexity

• ⏰ Time complexity: O(n). The algorithm performs linear passes, so the time complexity is O(n), where n is the length of the string dominoes.
• 🧺 Space complexity: O(n). The space complexity is O(n) due to the array used to store force values.

Method 3 - Just Track the Count of L and R

Keep track of the indices of the last seen 'L' and 'R' using variables L and R.

1. If we see 'R' and R > L, this indicates a sequence of R....R, so all affected dominoes should be set to 'R'.
2. If we see 'R' and R < L, the sequence L...R appears, which requires no changes.
3. If we see 'L' and L > R, the sequence L....L is formed, and all relevant dominoes are set to 'L'.
4. If we see 'L' and L < R, representing R....L, use two pointers (lo for the left and hi for the right). Assign 'R' to a[lo] and 'L' to a[hi], increment lo, decrement hi, and stop when lo == hi.
5. Handle edge cases carefully, such as i <= dominoes.length() to process trailing 'L'. Also, initialise L and R to -1 instead of 0 for correct logic.

Code

Java

class Solution {
	public String pushDominoes(String dominoes) {
		char[] a = dominoes.toCharArray();
		for (int i = 0, L = -1, R = -1; i <= dominoes.length(); i++)
			if (i == a.length || a[i] == 'R') {
				if (R > L)//R..R, turn all to R
					while (R < i)
						a[R++] = 'R';
				R = i;
			} else if (a[i] == 'L')
				if (L > R || R == -1)//L..L, turn all to L
					while (++L < i)
						a[L] = 'L';
				else { //R...L
					L = i;
					for (int lo = R + 1, hi = L - 1; lo < hi; ) {//one in the middle stays '.'
						a[lo++] = 'R';
						a[hi--] = 'L';
					}
				}
		return new String(a);
	}
}

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        a = list(dominoes)  # Convert string to a list for in-place modifications
        n = len(a)  # Length of the domino array
        L, R = -1, -1  # Initialise indices for last seen 'L' and 'R'

        # Iterate through the dominoes array (+1 to handle edge cases, i == n)
        for i in range(n + 1):
            if i == n or a[i] == 'R':  # Case where 'R' is encountered or iteration reaches beyond the last index
                if R > L:  # Handle 'R...R', set all affected to 'R'
                    while R < i:  # Propagate 'R' forward
                        a[R] = 'R'
                        R += 1
                R = i  # Update last seen 'R' index
            elif a[i] == 'L':
                if L > R or R == -1:  # Handle 'L...L', set all affected to 'L'
                    while L + 1 < i:  # Propagate 'L' backward
                        L += 1
                        a[L] = 'L'
                else:  # Handle 'R...L'
                    L = i  # Update last seen 'L' index
                    lo, hi = R + 1, L - 1
                    while lo < hi:  # Handle the two pointers to propagate 'R' and 'L'
                        a[lo] = 'R'
                        a[hi] = 'L'
                        lo += 1
                        hi -= 1

        return ''.join(a)  # Convert the list back to a string to return the result

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1) if we see aux space complexity, but O(n) if we consider answer string

Method 4 - Using BFS

BFS can simulate the propagation effect of falling dominoes iteratively:

Approach

1. Initial Setup:
   • For dominoes pushed (L or R), add their indices to a queue.
   • Indices in the queue will be processed level by level (like BFS), simulating the dominoes falling in one-second increments.
2. Processing the Queue:
   • Pop indices from the queue and determine the effect they cause (L pushes left and R pushes right).
   • Update the state of the dominoes and add newly affected dominoes to the queue.
3. Final State:
   • Once the queue is empty, return the updated dominoes string.

Code

Java

class Solution {

    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        char[] a = dominoes.toCharArray(); // Convert the string to a character array for easier updates
        Queue<int[]> queue = new LinkedList<>(); // Queue to hold indices and their current force ('L', 'R')

        // Add initial 'L' and 'R' dominoes to the queue
        for (int i = 0; i < n; i++) {
            if (a[i] == 'L' || a[i] == 'R') {
                queue.offer(new int[] { i, a[i] });
            }
        }

        // Process the BFS queue
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int i = current[0];
            char force = (char) current[1];

            if (force == 'R') { // Dominoes falling to the right
                if (i + 1 < n && a[i + 1] == '.') { // If the next domino is upright
                    a[i + 1] = 'R';
                    queue.offer(new int[] { i + 1, 'R' }); // Add the next position to the queue
                }
            } else if (force == 'L') { // Dominoes falling to the left
                if (i - 1 >= 0 && a[i - 1] == '.') { // If the previous domino is upright
                    a[i - 1] = 'L';
                    queue.offer(new int[] { i - 1, 'L' }); // Add the previous position to the queue
                }
            }
        }

        return new String(a); // Convert the array back to a string and return the result
    }
}

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        a = list(dominoes)  # Convert string to a list for easier updates
        queue = deque()  # Queue for BFS

        # Add all pushed dominoes (L or R) to the queue
        for i in range(n):
            if a[i] in ('L', 'R'):
                queue.append((i, a[i]))

        # Process the queue
        while queue:
            i, force = queue.popleft()
            
            if force == 'R':  # Domino falls/pushes right
                if i + 1 < n and a[i + 1] == '.':  # If next domino is upright
                    a[i + 1] = 'R'
                    queue.append((i + 1, 'R'))  # Add next position to the queue
            elif force == 'L':  # Domino falls/pushes left
                if i - 1 >= 0 and a[i - 1] == '.':  # If previous domino is upright
                    a[i - 1] = 'L'
                    queue.append((i - 1, 'L'))  # Add previous position to the queue

        return ''.join(a)  # Convert list back to string and return the result

Complexity

• ⏰ Time complexity: O(n). Each domino is processed once, as its state changes and cannot be affected again.
• 🧺 Space complexity: O(n). Queue size can be up to n in the worst case.