Given an array $$$A$$$ of $$$N$$$ integers . Find the maximum of value of $$$i\ -\ j$$$ such that : $$$\newline$$$ $$$1)\ j\ \le\ i \newline$$$ $$$2)\ A[j]\ \le\ A[i] \newline$$$
Note : $$$i$$$ and $$$j$$$ are 0-based indices
Constraints :
$$$ N \le 10^6\ ;\ A[i]\ \le\ 10^9\ for\ 0\ \le i\ \le\ N-1\newline $$$
Ex :
- $$$A\ =\ [1,2,3,4,5]$$$
$$$j\ =\ 0\ ,\ i\ =\ 4$$$ gives maximum difference of 4 satisfying the given conditions - $$$A\ =\ [8,4,8,7,6,6,3]$$$
$$$j\ =\ 1\ ,\ i\ =\ 5$$$ gives maximum difference of 4 satisfying the given conditions
Note : This question was asked in an on-campus coding exam & it was completed
Forgive me for the English & formatting.
It comes down to find the index of last number >= A[i] for an index 'i' from 0 to n-1 .
My idea for this problem is to find suffix array for storing max value for each index from back. Now we traverse through our array and binary search the smallest index value >= in the suffix array of max after reversing it.
i.e.
5
5 1 4 2 3
my suffix array of max is [ 5,4,4,3,3]
we need to reverse our suffix array to perform binary search so it becomes [ 3,3,4,4,5]
In reversed suffix array we need to binarysearch smallest index having value >= A[i] , (0 <= i <= n-1 ) and find the difference
In above case:-
* for '5' we get index 4 ( 0 based indexing ), we will return (n-(index+1)) as we have reversed it , and difference with current index is going to '0'
similarly for all other values.
One way to do this problem would be using coordinate compression + a segment tree. First, compress all of the coordinates to the range [1, n]. Then iterate left to right, while maintaining a minimum segment tree over a function f, where f(x) = min index with value x. At each index i, the answer is i — min(f(1), f(2), ..., f(i)) which can be queried from the segment tree. All f(i) should be initialized to infinite and values should be updated as they come in.
For each indice $$$i$$$, you have to find the left-most indice $$$j$$$ so that $$$A[j] ≤ A[i]$$$
The idea here is to use a data structure that supports finding the maximum value in a range and update the value. A Segment Tree is suitable.
Firstly, sort the indices based on their value in $$$A$$$ in ascending order. Then iterate from left to right. Assume we have indice $$$i$$$, if there is an indice $$$j ≤ i$$$ and $$$A[j] ≤ A[i]$$$, the maximum of the range $$$[1, j]$$$ in our segment tree is $$$1$$$, but the maximum of the range $$$[1, j - 1]$$$ is $$$0$$$. You can find the smallest $$$j$$$ by using binary search and the complexity will be $$$O(log^2 n)$$$, or segment tree walk in $$$O(log n)$$$. Total complexity will be $$$O(n log n)$$$ or $$$O(n log^2 n)$$$. Just notice the case $$$A[i] = A[i + 1]$$$ and don't forget to update the indice $$$i$$$ by 1.
Now your answer is the maximum $$$i - j$$$ from all iterations!
p/s: My English is bad, forgive me too! If I have any mistakes, I will be grateful if someone point it out for me ^_^
Thanks everyone ,
https://pastebin.com/czydKevx
tried implementing a slight variation where $$$A[j]\ <\ A[i]$$$
Glad it helped you! Don't forget to look at pkpawan's solution, I find it much more interesting than mine. Easier and faster!
No fancy data structures, just a neat little trick that's similar to the one described here https://cses.fi/book/book.pdf#page=91. We want to use binary search to find the corresponding index i for every index j, iterating from left to right. The idea is to maintain a vector of candidate indices which could possibly be the answer i for some future index j. Notice that if an index i is a possible answer, and a[i] < a[i+1], then i+1 will never be a possible answer, because it'll always be advantageous to pick a[i] instead. So while we iterate on j from left to right, we add j to the vector only if a[j] is less than the element at the last index in the vector. Finally, for each index j, we use binary search to find the first possible answer i where a[i] <= a[j].
Haven't tested this at all, but here's an implementation of what I'm thinking https://pastebin.com/NdYE1Aw7 hopefully that helps clarify my logic :D also I just realized I accidentally flipped i and j, in my explanation I'm using i<j and a[i]<=a[j] as the condition sorry about that
O(n) solution:
Key idea is that if we are considering right boundary of the segment $$$i=p$$$, if $$$j < k < i$$$ and $$$A_j \leq A_k$$$, then $$$A_k$$$ is useless.
Maintain a monotone queue, initially empty. Scan the array from left to right. When encountered an element $$$A_i$$$, if the element is strictly smaller than the last element of the queue, append it to the queue. At the end we will get a strictly decreasing queue, which will be our only candidates for left boundary.
Similiary, maintain another monotone queue, this time scanning from right to left and add elements strictly larger than the first element to the head. We will get another strictly decreasing queue (viewed from left to right) which will be our only candidates for right boundary.
As both candidate arrays are strictly decreasing, we can put a pointer on right bounary candidate, initially pointing to first element. Scan the left boundary candidates, as we move from left to right for the left boundary, the pointer of right boundary candidate (so that the segment [left, right] is valid) is also moving to right only, which gives an O(n) solution overall.