Dominoes Game

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Flipkart limited

Problem statement

You are playing a dominoes game with your friends in which you have ‘N’ dominoes placed vertically upright. At the start of the game, you simultaneously pushed some of the dominoes either to the left or to the right. After each second, each domino falling to the right pushes the adjacent domino on the right. Similarly, the dominoes falling to the left pushes the adjacent domino on the left. When a vertical domino has dominoes falling to it from both sides, it stays as it is due to the balance of the forces. You are given a string ‘S’ of length ‘N’, representing the states of the dominoes where ‘L’ represents a domino falling in the left direction, ‘R’ represents domino falling right direction, and ‘.’ represents domino has not been pushed initially. Print the final state of the dominoes.

Note: 
A falling domino exerts no additional force to a falling domino or an already fallen domino.
For example: 
Let ‘S' be: “R.L”
The second domino is pushed from both directions, therefore remains still. 
So the final state becomes “R.L”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a string ‘S’, representing the initial state of the dominoes.
Output Format : 
For each test case, print a single string representing the final state of the dominoes.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= |S| <= 10^6

S only contains {‘L’, ‘R’, ‘.’}

Time Limit: 1 sec
Sample Input 1 :
2
R.L
R..
Sample Output 1 :
R.L
RRR
Explanation For Sample Input 1 :
For test case 1: 
The second domino is pushed from both directions, therefore remains still. 
So the final state becomes “R.L”.

For test case 2: 
The first domino exerts a force on the second domino, which exerts a force on the third domino.
So the final state becomes “RRR”.
Sample Input 2 :
2
R.LLL....RR
.L.R...LR..L..
Sample Output 2 :
R.LLL....RR
LL.RR.LLRRLL..
Hint

Try to find the direction of the dominoes adjacent to the non-falling dominoes.

Approaches (2)
Greedy Approach

For each group of non-falling dominoes, we will have two falling dominoes at the end of each group. There are four cases we need to consider:

  1. If we have a group “A...B”, and  A == B, we should write “AAAAA”. For example: “R...R” will become “RRRRR”.
  2. If we have a group “L...R”, we don’t need to do anything as they are falling in opposite directions and no one exerts a force on non-falling dominoes.
  3. If we have a group “R...L”, we need to find the number of non-falling dominoes (‘.’) in the group. If we have an even number of ‘.’ non-falling dominoes will be divided equally. For an odd count, we need to check our distance from non-falling dominoes from the falling dominoes.

 

Here is the algorithm :

 

  1. Create two arrays (say, ‘IDX’ and ‘VAL’) to store the index and position of falling dominoes and initialize the first and last index as -1 and ‘N’ for array ‘IDX’ and ‘L’ and ‘R’ for array ‘VAL’ respectively.
  2. Create a variable (say, ‘LENGTH’) to find the number of falling dominoes.
  3. Run a loop from 0 to ‘N’ (say, iterator ‘i’) and store the index and position of the falling dominoes.
  4. Run a loop from 0 to ‘LENGTH’ - 1 (say, iterator ‘i’).
    • Create two variables (say, ‘INDEX’ and ‘nextINDEX’) to store the current indexes.
    • Create two variables (say, ‘X’ and ‘Y’) to store the current values.
    • Check if ‘X’ is equal to ‘Y’.
      • Update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘X’.
    • Else, check if ‘X’ is greater than ‘Y’.
      • Run a loop from ‘INDEX’ + 1 to ‘nextINDEX’ (say, iterator ‘k’)
        • Check if ‘k’ - ‘INDEX’ is equal to ‘nextINDEX’ - ‘k’, update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘.’.
        • Else, check if ‘k’ - ‘INDEX’ is smaller than ‘nextINDEX’ - ‘k’ and update all the ‘S’ values in range ‘INDEX’ to ‘nextINDEX’ to ‘R’.
        • Else, update all the values of ‘S’ in range ‘INDEX’ to ‘nextINDEX’ to ‘L’.
  5. Finally, return ‘S’.
Time Complexity

O(N), where ‘N’ is the size of the string.

 

We iterate the string once to find the falling dominoes’ index and position, which takes O(N) time. We then run a loop again to update the direction of the dominoes, which can take up to O(N) time. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the size of the string.

 

We use two extra arrays, ‘IDX’ and ‘POS’ to store the indexes and the position of the falling dominoes. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Dominoes Game
Full screen
Console