blank_manash's blog

[Casual] A Cute Task
By blank_manash, 4 years ago, In English

I had a dream about a problem last night that I still haven't been able to solve. Maybe The community can give some insight.

Problem Statement.

You're given an array $$$a$$$ of size $$$n$$$, You perform the following steps in a single operation :

0) Take $$$i = 0$$$,

1) Let $$$j$$$ be the minimum index $$$(j > i)$$$ such that $$$a[j] > a[i]$$$

2) Delete the element $$$i$$$ from the array.

3) If $$$j$$$ doesn't exists, terminate the operation, else set $$$i = j$$$ and repeat from 1.

You are required to find the number of operations you can perform before the array is empty.

An $$$\mathcal{O}(n^2)$$$ algorithm is quite visible, but can you solve it in approximate linear time ?

Model Solution I thought of
  • Vote: I like it
  • +21
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve this in $$$O(n)$$$ using monotonic stack to store, for each index $$$i$$$, the next index $$$j$$$ s.t. $$$a_i < a_j$$$.

Some code

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    I thought of that, but I couldn't prove why it produces the right answer ( I am a little convinced that it does though)

    Because say, the array is $$$a = [3,2,5]$$$, then for $$$0,1$$$ will have $$$next[i] = 2$$$ but after the first operation, the array changes to $$$[2]$$$.

    I think the answer is still the same but I couldn't find a formal proof.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Step 1) https://www.geeksforgeeks.org/next-greater-element/

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yes, but the array is changing after every operation, so I think we cannot afford to pre — calculate that in every operation.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you look at all the selected i in order you will notice that it's increasing. Thus after selecting an i what matters is only the subarray starting from i (the values before i will never get selected so we can safely ignore them). What follows is to calculate the values in step 1, which can be done with a monotonic deque.

→ Reply