Aspergillus's blog

Need Help with a particular problem.
By Aspergillus, history, 10 months ago, In English

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.

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it
hint
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain with an example how that would work? Let's say my array is 10 8 9 5 4 6 7 9.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :(

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 4 i = 3 : A[top] = 8 < A[3] pop ans[4] = 4 - 3 = 1 s is empty push 3 i = 2 : A[top] = 9 > A[2] push 2 i = 1 : A[top] = 7 < A[1] pop ans[2] = 2 - 1 = 1, pop ans[3] = 3-1 = 2 at last set ans for top index to index itself and pop untill stack is empty ans[1] = 1 ans = {1, 1, 2, 1}

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Finally got it! Thanks for your efforts to make me understand this!! Much love <3

            → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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

      Спойлер
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply