Matrix.code's blog

Longest Sub-array with smaller elements

By Matrix.code, 9 years ago, In English 
An array of integer is given.. 
For each element of i th index , I need to find the length of the longest sub-array starting from i+1 index where all the element is smaller than arr[i]

Sample : arr[]={10 , 2 , 7 , 4 , 12 ,2 }

for i = 0 , arr[0] = 10 , the sub-array is = {2,7,4} . All are smaller than 10 and starting from 
i + 1 th index ... 
and for i = 1 , length = 0
This need to be done for all the index of the array 

How to find the length ??
Constrains: 
Size of The array = 10^6

I think RMQ will prove necessary here
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it 
stack< pair<int, int> > st;
for (int i = (int)a.size() - 1; i >= 0; --i)
{
    while (!st.empty() && st.top().first < a[i])
        st.pop();
    if (st.empty())
        ans[i] = a.size();
    else
        ans[i] = st.top().second;
    st.push(pair<int, int>(a[i], i));
}
→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let v be the given array. Initially, you should push to a stack all the elements of v that you have processed. But the main idea is that the stack should have the following invariant: for every element k in the stack, the element k-1 (right below it, if it exists) should necessarily be strictly greater in value than it. Let len_i be the longest sub-array starting from i+1. This way you can be sure that the elements v[i] and v[i+1+len_i] (first element that is not in the sub-array) will never be in the stack at the same time.

So before you push an element v[x] to the stack, you have to pop all the elements from the top of the stack which are lesser or equals in value to the element v[x]. Let v[j], j < x, be an element that was popped from the stack at this step. You can notice that v[x] is the first element which is not in the longest subarray starting from j+1, so you can easily get the longest subarray starting from j+1 by subtracting the positions x and j+1.

// ii is pair<int, int>
// c is the answer array
v.push_back(INFINITE);
stack<ii> s;
for(int x = 0; x < v.size(); x++){
	while(!s.empty() && s.top().first <= v[x]){
		int j = s.top().second; s.pop();
		c[j] = x - (j+1);
	}
	s.push(ii(v[x], x));
}

So we have stack<ii> containing the element value and its position in the original array. You may simplify it by not using pairs, but I think it's ok. You can easily make sure that all the elements were popped from the stack by pushing an INFINITE element to the vector v and looping through all the elements. It's O(n) complexity since the elements are pushed once and popped once.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

This is basically just an application of the All nearest smaller values problem, though in our case the situation is kind of reversed. The stack based solution is easier to understand, but I like the following solution more since the code is shorter and it's more memory efficient...

Input: A[0..len)
Output: B[0..len), B[i] contains the index of the first element to the right larger than A[i] (or len if no such element exists).

for(int i = len-1; i>=0; i--)
{
    int j = i+1;
    while(j<len && A[j]<=A[i]) j = B[j];
    B[i] = j;
}

And yeah the complexity is O(n).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Thanks Klein
This was great & thanks for the link
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @testcoder

      Here is one more simple but lengthy solution that may help you .

      1. You can build a segment tree for the given array and use binary search type technique.
      2. Let me explain the solution ..

      As you can see the max(i+1..i+1) , max(i+1 .. i+2) , max(i+1 .. i+3) and so on max(i+1...n) will be forming a increasing sequence.. agree ??

      now you can do binary search to find the solution ... binary search from (i+1,n) to find the right most index idx such that max(i+1 .. idx)<=arr[i]. you can use this to find the answer dynamically as well...

      Time complexity O(nlog^2(n)) .. Hope this is useful..

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

        @testcoder

        Can you provide me link to this problem ...

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

        With sparse table you're able to do it in O(n·log2n) time.

        Also with segment tree you can find first element that more or equal than a[i] in [i + 1;n]. That's also O(n·log2n).

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

          how ??

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

            sparse table serve the purpose but we can't allocate that much memory and preprocessing time

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

              80 MB is not that much

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

              Author didn't give us limits. TL = 2s and ML = 512mb would me enough :)

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

          I was expecting some Segment Tree solution ..
I got the idea, just could not implement it !!!

Can you help @Wackloner
          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello test coder

      Here is O(N) solution much precise and simplest implementation i can think off .. http://ideone.com/axjpyT

      Here is the link to detailed explanation of the problem .. and sorry for introducing the concept of segment tree here as it was not needed but yeah there exists a O(NlogN) time solution using segment tree ...

      → Reply