maneeshp626
BAN USERHere is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].
For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.
Just perform BFS considering root as source node. We update the distance as we reach to next level. As we get the specified element return the distance from root node.
- maneeshp626 November 23, 2017
I think there may be a dynamic programming solution having O(N) time complexity.
- maneeshp626 November 25, 2017