NINJA’S GRID

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