How do I calculate the length of longest subarray ending at index $$$i$$$ $$$(1 \leq i \leq N)$$$ with elements smaller than or equal to $$$A[i]$$$ in an array A of length N for each $$$i$$$? $$$(1 \leq N \leq 10^6).$$$
I have tried a few different approaches with two pointers, tried using the merge sort algorithm to find the lesser than or equal to elements before each element but every approach I tried have obvious flaws.
Can anyone please help me with this? I would appreciate a solution without the use of data structures like segment trees or BIT and such, as I am yet to learn about these.
binary search over range maximum
can you explain with an example how that would work? Let's say my array is 10 8 9 5 4 6 7 9.
for a index i pick index j <= i now do the binary search over over from 0 to i if max(j..i) <= A[i] then you search for better j in 0..j — 1 else search in j + 1..i. the complexity would O((logn)^2) for single element. But there is a better solution using monotonic stack.
How would you solve using stack? Let's say I have 10 7 9 8. My answer should be 1 1 2 1. Can you explain an algorithm for it? I am really stuck :(
iterate from i = n — 1 to 0; if the stack is empty of top element of stack is >= current element push the index of current element in stack else if current element is greater than you ans for the top index is i — cur. keep keep doing this until stack is empty or top element >= current element.
considering above example 10 7 9 8 stack = s initially empty ans = {-1, -1, -1, -1}
i = 4 : s is empty push 4i = 3 : A[top] = 8 < A[3] pop ans[4] = 4 - 3 = 1 s is empty push 3i = 2 : A[top] = 9 > A[2] push 2i = 1 : A[top] = 7 < A[1] pop ans[2] = 2 - 1 = 1, pop ans[3] = 3-1 = 2at last set ans for top index to index itself and pop untill stack is empty ans[1] = 1 ans = {1, 1, 2, 1}Finally got it! Thanks for your efforts to make me understand this!! Much love <3
you can do linear with a stack, so if max was a[i], you find the previous greater and exclude it from the longest subarray
you can read this https://usaco.guide/gold/stacks
Hi thanks for the idea but I don't see the solution clearly yet.
Suppose the array is: 10 8 9 5 4 6 7 9, then I am supposed to output 1 1 2 1 1 3 4 7 correspondingly.
follow the link, we can find $$$prv[i]$$$ = maximum $$$j$$$ such that $$$p[j] > p[i]$$$, we can note that for all $$$j < k <= i$$$, $$$p[k] <= p[i]$$$, so the answer would be $$$i - j$$$ for each $$$i$$$
In the code below, $$$a$$$ is reversed $$$p$$$, where $$$p$$$ is the original array
Thanks! This approach is so much simpler, I tried using so many unnecessary techniques. As a side note, Im using a stack of pair of ints to easily access "j" as the second element of the pair being the index.