algoadvance

Leetcode 838. Push Dominoes

Problem Statement

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

Return a string representing the final state after all dominoes have been pushed.

Clarifying Questions

  1. Input Constraints:
    • The string length ( n ) can be up to ( 10^5 ).
    • The string contains only the characters '.', 'L', and 'R'.
  2. Is there a guaranteed solution?
    • Yes, there will be a deterministic outcome for the domino setup provided.
  3. Can I make any assumptions about the interactions?
    • Yes, the dominoes will fall until they either hit another domino or reach the end of the string.

Strategy

  1. We’ll process the string dominoes by simulating the effect of domino pushes over time but do it in a single pass for efficiency.
  2. Initialize an array forces to keep track of net forces applied on each position in dominoes.
  3. Traverse the string from left to right and compute forces exerted by dominoes pushed to the right ('R').
  4. Traverse the string from right to left and compute forces exerted by dominoes pushed to the left ('L').
  5. Combine the forces to determine the final state of each domino:
    • Positive force means the net force is towards the right ('R').
    • Negative force means the net force is towards the left ('L').
    • Zero force means no net push (domino stays '.').

Code

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

        // Traversing from left to right
        int force = 0;
        for (int i = 0; i < n; i++) {
            if (dominoes.charAt(i) == 'R') {
                force = n;  // Reset the force to a high positive number
            } else if (dominoes.charAt(i) == 'L') {
                force = 0;  // Reset the force to zero if 'L'
            } else if (force > 0) {
                force--;  // Decrease the force for continuing 'R'
            }
            forces[i] += force;
        }

        // Traversing from right to left
        force = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (dominoes.charAt(i) == 'L') {
                force = n;  // Reset the force to a high negative number
            } else if (dominoes.charAt(i) == 'R') {
                force = 0;  // Reset the force to zero if 'R'
            } else if (force > 0) {
                force--;  // Decrease the force for continuing 'L'
            }
            forces[i] -= force;
        }

        // Construct final string based on net forces
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (forces[i] > 0) {
                result.append('R');
            } else if (forces[i] < 0) {
                result.append('L');
            } else {
                result.append('.');
            }
        }

        return result.toString();
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI