838. Push Dominoes

 Push Dominoes

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 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.

 

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 '.'.

Description

This problem is to calculate the final stable state given the state of the domino at a certain

moment, to represent the domino pushed to the right, to L to represent the domino pushed to the

left, and to. represents the upright domino.

The domino can only affect the cards on its adjacent two sides per second, so R.. after one second, it will become RR. because the first card falls to the right and the second card is also pushed down, and the third card has not been affected by the first card at this time. The effect will not become until after the second second RRR.

When Rand Lmeet there will be a net balance, eg R..L will be RRLL balanced by and R...L will be RR.LL balanced by, the third card remains upright because both dominoes are passed to it at the same time, thus achieving a net balance.

Since cards that have been knocked down to become R or L do not change state, we know that we only need to deal . with cards.

Also, observe .Ror L.can find that these two are also in net force balance, so we can know that we only need to deal with Rthe right or Lthe left .

Idea:

Now that I'm talking about force balance, I'd like to calculate the net force at each point, which is the sum of the left and right thrusts. The two forces are in opposite directions, with a minus sign, and I need a system to calculate the magnitude of the thrust so that the farther the thrust is transmitted, the lower the magnitude.

Let's code it!

/**
 * @param {string} dominoes
 * @return {string}
 */
var pushDominoes = function (dominoes) {
  const arr = new Array(dominoes.length)
  let c = 0
  for (let i = 0; i < dominoes.length; i++) {
    if (c > 0 && dominoes[i] === '.') {
      c--
    } else if (dominoes[i] === 'R') {
      c = dominoes.length
    } else {
      c = 0
    }
    arr[i] = c
  }
  c = 0
  for (let j = dominoes.length - 1; j >= 0; j--) {
    if (c > 0 && dominoes[j] === '.') {
      c--
    } else if (dominoes[j] === 'L') {
      c = dominoes.length
    } else {
      c = 0
    }
    arr[j] -= c
  }
  return arr.map(n => n > 0 ? 'R' : n < 0 ? 'L' : '.').join('')
}

I use the variable to crepresent the magnitude of the thrust, and whenever the thrust source ( Ror L) is encountered, I cinitialize to the number of dominoes, and after the thrust source, whenever the thrust is met ., the thrust will be propagated, and the thrust will decay, so cdecrement by 1; whenever the opposite is encountered If the thrust source is used, the thrust will be reset to zero.

As for why the thrust source is initialized to the number of dominoes, this design is so that the force is still positive after all the dominoes are transmitted, but the value decreases every time a grid is passed.

In lines 8 to 17, I start by calculating the right thrust from left to right.

Every encounter .(line 9) and the current right thrust is greater than 0, the right thrust is decreased; every encounter R(line 11) is given a thrust source with a size equal to the size of the array, and the rest (that is L) will be the right thrust reset to zero.

Vice versa, lines 19 to 28 calculate the left thrust in reverse, the only difference is that Lit is given to the thrust source when it encounters R, and it is reset to zero when it encounters . Incorporate into arr to calculate the net force.

Take sample capital measurement LL.Ras an example :

Right thrust =   0 0 0 4 
Left thrust = -4 -4 0 0 
------------------ 
Net thrust = -4 -4 0 4 
         LL . R

Right is positive, left is negative, and 0 remains upright (line 29). Therefore, an equilibrium state can be obtained LL.R.

Another test fund .L.R...LR..L..:

Right Thrust =    0 0 0 14 13 12 11 0 14 13 12 0 0 0 
Left Thrust = -13 -14 0 0 -11 -12 -13 -14 0 -12 -13 -14 0 0 
------- ------------------------------------------------- 
net Thrust = -13 -14 0 14 2 0 -2 -14 14 1 -1 -14 0 0 
          LL . RR . LLRRLL . .

be in balance LL.RR.LLRRLL...
method proven.

OR

var pushDominoes = function(dominoes) {
    let start=0; 
    let end=1;
    const arr = ("L"+ dominoes +"R").split("");
    while(start < arr.length-1){
        while(arr[end]=='.') 
            end++;
        if(arr[start] == arr[end]) 
            for(let i= start+1; i<end; i++) {
                arr[i]=arr[start];   
            }
        if(arr[start]>arr[end]) 
            for(let i=1; i<=(end-start-1)/2; i++){
                arr[start+i] = 'R';
                arr[end-i] = 'L';
            }   
        start=end++;
    }
    return arr.slice(1,arr.length-1).join("");
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #838. Push Dominoes

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!