D
DevExCode

LeetCode 838: Push Dominoes Solution

Master LeetCode problem 838 (Push Dominoes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can simulate the process of pushing dominoes by iterating through the input string. We keep track of the state of each domino as it falls based on its surroundings. We can handle three cases: when a domino is falling to the left, to the right, or it is stable.

  1. When a domino is falling to the left, we update its state to 'L' if it was '.' or 'R' before.
  2. When a domino is falling to the right, we update its state to 'R' if it was '.' or 'L' before.
  3. When a domino is stable, we leave it unchanged.

We maintain two pointers to keep track of the dominoes falling to the left and to the right. By iterating through the string, we update the state of each domino based on its surroundings. Finally, we return the updated string representing the final state of the dominoes.

  • Time complexity: O(n) where n is the length of the input string.
  • Space complexity: O(n) for storing the updated state of the dominoes.

:

Solution Code

class Solution {
    public String pushDominoes(String dominoes) {
        char[] doms = dominoes.toCharArray();
        int n = doms.length;
        int[] forces = new int[n];
        
        int force = 0;
        for (int i = 0; i < n; i++) {
            if (doms[i] == 'R') force = n;
            else if (doms[i] == 'L') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] += force;
        }
        
        force = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (doms[i] == 'L') force = n;
            else if (doms[i] == 'R') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] -= force;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int f : forces) {
            sb.append(f > 0 ? 'R' : f < 0 ? 'L' : '.');
        }
        
        return sb.toString();
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 838 (Push Dominoes)?

This page provides optimized solutions for LeetCode problem 838 (Push Dominoes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 838 (Push Dominoes)?

The time complexity for LeetCode 838 (Push Dominoes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 838 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 838 in Java, C++, or Python.

Back to LeetCode Solutions