I came across an interesting problem today, give a list of numbers n1 to n10, we need to return an array which will have the next greater element for each number

for example, for input N = [...some numbers..] with length L

we need to return

A = [a1....some numbers..] with length same as N

where A[i] can be zero if there are no greater elements after N[i], if there is a greater element we need to get the first instance of greater element and put it in answer array A

The simple solution requires bruteforcing, that is for every element i, we need to iterate through input array in range [i+1, L], this takes O(n ^ 2) time.

### Trying to avoid bruteforcing...

lets say we have an array [7,3,2,8,9]

Why we bruteforce ?

The major reason is we dont know what elements lies after 7, there are various possibilities

1. All the elements after 7 might be less than 7

2. All the elements after 7 might be greater than 7

3. All the elements after 7 might be equal to 7

The problem is not iterating the array, the problem is doing it from the front. In other words we dont know the future when we start with 7, but if we start from the end we know exactly how many elements lies ahead 7 and how many are greater than 7 and which one is closer

we can create a list of elements which we make sure to maintain in descending order. why maintain descending order ? because for each number we want to know if there are any elements greater than that, if we dont have the descending order then we would need to loop through entire array to pick the one number greater than the current element, then we need to pick the one with minimum index ( we are taking the next greatest element, so we would need to pick the one with min index )

### how would that list looks like when we are at 7 ?

[9,8,3,2]

### Lets filter all the elements less than 7

[9,8]

### Lets pick the element with minimum index

### [8]

Do we still need 9?

Think about in which case where removing 9 would do harm, that is having 9 not on the list will yield a inconsistent result

lets say we a additional element 10 between 2, 8

does it make sense to have the values less than 10 in our list ? in other words in case if we encounter a higher value ( 10 ) and traversing backwards ( 9, 8, 10 ..) could we safely delete the values which are less than that ?

Yes we absolutely can, because 7,3,2 will all choose 10 as the greatest value not 8, not 9.

## 0 comments:

## Post a Comment