NINJA’S GRID

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in company
Adobe

Problem statement

Ninja is thinking of developing a game where a user will be provided with a 'GRID' of size ‘N * N’. The user has to return the minimum number of steps required to make the given grid as ‘Ninja Grid’. If it is not possible the user has to return ‘-1’.

A grid is called a ‘Ninja Grid’ if all the cells of the grid that are present above the main diagonal have become equal to ‘0’ by doing below operation zero or more times:

1. Choose two adjacent rows and swap them.

As Ninja is busy developing the game, he asks you for help. Your task is to find out the minimum number of operations required to make a 'Ninja grid' from a given 'GRID' of size ‘N * N’.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains an integer ‘N’  denoting the size of the 'GRID' as size ‘N * N’.

Then each next ‘N’ line contains ‘N’ space-separated integers denoting the given grid values.

Output Format:

For each test case, return the minimum number of steps required to make the given grid as ‘Ninja Grid’. In case it is not possible then return ‘-1’.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 100
0 <= GRID[i][j] <= 1

Time Limit: 1 sec

Sample Input 1:

2
3 
1 1 1
1 0 0
1 1 0
3 
1 0 0
1 1 1
1 1 1

Sample Output 1:

2
-1

Explanation for sample input 1:

Test Case 1:

Example

As you can see in the input grid first we have to swap row 1 with 0 and then row 1 with 2 to get the ninja grid so it takes two steps so we return ‘2’.

Test Case 2:

Example

As you can see in the input grid there is no possibility of swapping as the last two rows are the same so we return ‘-1’.

Sample Input 2:

1
3 
0 0 0
1 1 1
1 0 0

Sample Output 2:

1

Explanation of sample input 2:

Test Case 1:

Example

As you can see in the input grid we just have to swap row 1 with 2 to make the grid a ninjas grid.
Hint

Can you think of counting ‘0s’ for each row?

Approaches (1)
Using bubble sort

The idea here is to count the number of zeros in every row starting from the end and fill in the 1-D array and also create a 1-D array for filling count of ‘0’ in the desired form which we want to make. Now from this 1-D array, we can compare in how many minimum steps we can create the desired array, and only swapping between adjacent rows is allowed.

So according to this example, our 'ORIGINAL_ARR' = [ 0, 2, 1 ] as in the first row there are no’ ‘0’ and in the next two rows the count of ‘0’ is ‘2’ and ‘1’ respectively.

 

Now we start iterating and check that the first index has no zero and less than ‘N - 1 - i’ so we use bubble sort like we pass 'ORIGINAL_ARR', current index i.e  ‘0’ and size i.e.’3’ now we run a loop starting from 'CURRENT_INDEX' to 'SIZE' and check if ‘ORIGINAL_ARR[i]’ is greater than or equal to ‘N - 1 - i’ so, in this case, this condition failed so the value of ‘i’ increases now this condition pass and we run another loop starting from ‘j’ = ‘i’ and less than 'START' and swap ‘ORIGINAL_ARR[j]’ and ‘ORIGINAL_ARR[j - 1]’ so for our case our ‘ORIGINAL_ARR’ modify as [ 2, 0, 1 ] in the same way for ‘1’ index we swap it with the last index and we count the total steps so we return ‘2’ as the final answer.

 

Now we simply apply bubble sort on our 'ORIGINAL_ARR' as we know in bubble sort each element would go to its correct position so whenever we see that in 'ORIGINAL_ARR' no of ‘0’ are less than the required array in any row we use bubble sort starting from the end so that it gets correct element at its index.

If we use the greedy approach, there can be a case where at some index suppose ‘i’ that can't have a number >= N - i - 1 because all those numbers were taken by previous indices (< i). Maybe if we had chosen some other order, the index ‘i’ could have satisfied the condition.

 

Although the individual number of swaps in 'ORIGINAL_ARR' is minimum, there can be a different arrangement where the individual number of swaps in 'ORIGINAL_ARR' is not minimum, but the total is less than the greedy approach.

 

Algorithm:

 

  • First, we create a 1-D array 'ORIGINAL_ARR' and start iterating our given array.
  • Now we fill our 1-D array with a count of ‘0’ in every row starting from the ‘N - 1’ column up to the ‘N - 2’ column.
  • Also now we make a 1-D array ‘requiredArr’ and store the correct form of ‘0’ we need according to ‘N’.
    • For ex - if the ‘N’ size is ‘3’ we need ‘0’ in the form
      • [ 2, 1, 0 ] count of ‘0’ can be more than that in 'ORIGINAL_ARR' but not less than that required array.
  • Now we try to make the ‘requiredArr’ from 'ORIGINAL_ARR' and in one count consecutive swaps are allowed so we use a bubble function for this and store the count in the 'COUNT' variable.
  • Now we check
    • If an index value of  'ORIGINAL_ARR' is less than the ‘requiredArr’ index value we return -1
    • Else we return ‘COUNT’.

 

Description of ‘BUBBLE’ function

 

The function is created to count the number of swaps by using bubble sort as if at any index of the value of ‘ORIGINAL_ARR'  is not correct we call this function to get the correct value at that index as bubble sort gives the correct value at index.

 

The function will take ‘3’ perimeter :

  1. 'ORIGINAL_ARR': An array which contains the count of ‘0’ in each row
  2. ‘START’: An integer which stores the index which has the wrong value or we can say current index.
  3. ‘END’:  An integer which stores the last index.

 

Run a loop starting from ‘i’ =  'START' to ‘end’ and declare a variable 'COUNT'

  • If ORIGINAL_ARR[i] < END - START - i.
  • Set ‘COUNT’ = ‘i’ - ‘START’
  • And run another loop starting  from ‘j’ = i and ‘j’ less than equal to 'START' and swap the element ‘j’ and ‘j-1’
  • Return the ‘COUNT’.
Time Complexity

O(N ^ 2), where ‘N’ is the total number of rows in the given array.

 

As we are iterating the grid to fill the ‘originalArr’ that will take O(N ^ 2) time in the worst case when all the elements of grid are ‘0’ then we are using bubble sort in which two nested loops are running which also takes the time O(N ^ 2) as if all elements are at the different position we need to run both the loop up to ‘N’.

Space Complexity

O(N), where ‘N’ is the total number of rows in the given array.

 

As we are using the array for storing ‘originalARR’ and ‘requiredArr’ and each array is of size equal to no rows in the grid that is O(N).

Code Solution
(100% EXP penalty)
NINJA’S GRID
Full screen
Console