SupaHotFire's blog

By SupaHotFire, history, 8 months ago, In English,

let's say we have an array={9,1,7,4,5} and I want to query what is the nearest bigger element to the left and to the right of the index I'm querying for example the nearest bigger element for 5 is 7 (it doesn't have bigger element to the right because it's the last element)and for 1 is 7 to the right and 9 to the left .

I think it needs some data structure(to make it nlog(n) instead of n^2) so if someone can provide some code it would be better and thanks in advance

  • Vote: I like it
  • -11
  • Vote: I do not like it

8 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

For one direction, you can do it with a stack:

At each element a[i], if the top of the stack is bigger than a[i], then the answer of a[i] is this top of stack, else if a[i] is bigger or equal to the top of stack, then the top of stack is no longer an answer for any element from now, so you will pop all the element from the top of the stack untill the stack becomes empty, or the top of the stack becomes bigger than a[i], so you reached the answer of a[i].

And in both cases, you have to push a[i] in the stack. So, each element will be pushed once and poped at most once, so the time complexity is O(n).

The solution with data structure can be as follows:

You can maintain a maximum segment tree on the range [minVal, maxVal]. Initially, all the position of the segTree will be -1, and at each element a[i], you will update the segTree at position a[i] with i, and for the answer of a[i], you will do a maximum query on the range [a[i]+1, maxVal].

And in both solutions, you will do the approach two times, one forward, and one backward, (for both directions, left and right, with some small differences in the segTree solution).

8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

you don't need any data structure, you can precompute suffix array such that suf[i]=min(a[i],suf[i+1]). After that all you need to do is binary search the smallest value in suffix array which is >a[i] on range i+1 to end of array. You can do for left of array similarly by precomputing prefix array. A problem using similar idea:Queue.Code: My solution