zahidhasanmozumder's blog

By zahidhasanmozumder, history, 7 weeks ago, In English

Suppose I have an array of 1 to n elements (Basically they are permutation) and I want to store the next bigger element of the i th element. How is it possible in O(N) or O(NlogN) time?

For example, The given array is : [5, 6, 7, 1, 2, 4, 3] of 7 length. Now I want to store all the element's next bigger element (according to indexing order) in O(N) or O(NlogN) time.

The resultant array should look like this : [6, 7, 7, 2, 4, 4, 3].

Here, the next bigger element of 5 is 6, for 6 is 7, for 7 (there is no bigger element than 7 in the next indices) is 7, for 1 is 2, for 2 is 4, for 4 (there is no bigger element than 4 in the next indices) is 4 and for 3 (as last element so it won't have any next bigger element) is 3.

How it can be done? Hope you guys will help me with your ideas :)

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, this can be done in n*log(n) time, and I have a straightforward solution. Please share where you got this problem first so that I know I'm not helping you cheat on an assessment or ongoing contest, and I will respond with the solution idea after.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agree on not helping before they share the source, in one case I've seen someone even ask for solutions during a company's code challenge. Well, I think I know your solution by now anyways :D

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    UPD: I found a problem of which this seems to be a near-dupe, there seems to be an O(n) solution of it. I shall leave finding the solution to the reader. (SecondThread, I can discuss about the solution with you in DM if you wish)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your response. And I truly appreciate your thoughts of not sharing the solution or idea before knowing the source or context. Basically I'm asking the idea for my recent unsuccessful submissions of a problem from past contest. I have already given two days behind the problem and now I'm asking for the idea for a particular part of the problem. Source: Fighting Tournament Hope you will help me by let me know your ideas......

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's easy to do it in O(NlogN).

We traverse the array in reverse order, and put the numbers into a set.

Than query in the set,done!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would be more helpful for me if you can explain the "query in the set" more clearly....

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Basically, you can binary search on STL sets! Other than that you can fill the array from the back and thats it.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ummm I'm a little bit confused. I have tried both of these approach but none of them gave me the desired result :(

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Use a stack, and start traversing from the back of the array.

          Here a small pseudocode

          stack<int> st;
          vector<int> res=arr;  // arr is the given array
          for(int i=n-1;i>=0;i--){
                if(!st.empty() && st.top()<arr[i]){ 
                     st.pop();
                }
                if(!st.empty()){
                      res[i]=st.top();
                }
                st.push(arr[i]);
          }
          
»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

You can do this question in O(n) using stack, let me explain:

You traverse the array in reverse order, i.e., back to front. Then for each element in the original array, while the element at the top of the stack is smaller than the element we are at, pop the top element out of the stack. Do this until the stack is empty or the element on top of the stack is bigger than the element we are at. Then if the stack is empty, then the answer for this element will simply be the element. Otherwise, it will be the element on the top of the stack. Lastly, we just have to add the element we are at to the top of the stack. Let me simulate this for the above input.

Answer array: 0, 0, 0, 0, 0, 0, 0 Stack: Empty

Element we are at: 3

Stack after removing elements from stack: empty

Answer array: 0, 0, 0, 0, 0, 0, 3. (since stack is empty, the last element will just be 3)

Stack after adding 3: 3

Element we are at: 4

Stack after removing elements: empty

Answer array: 0, 0, 0, 0, 0, 4, 3 (since stack is empty, the last element will just be 4)

Stack after adding 4: 4

Element we are at: 2

Stack after removing elements: 4 (2 is not bigger than 4)

Answer array: 0, 0, 0, 0, 4, 4, 3 (answer is the number at the top of the stack

Stack after adding 2: 2, 4.

Element we are at: 1

Stack after removing elements: 2, 4 (1 is not bigger than 2)

Answer array: 0, 0, 0, 2, 4, 4, 3 (answer is the number at the top of the stack)

Stack after adding 1: 1, 2, 4.

Element we are at: 7

Stack after removing element: Empty (we removed all the elements since none of the numbers in the stack were bigger than 7

Answer array: 0, 0, 7, 2, 4, 4, 3. (Since stack is empty, answer is just 7)

Stack after adding 7: 7

Element we are at: 6

Stack after removing elements: 7 (7 bigger than 6)

Answer array: 0, 7, 7, 2, 4, 4, 3

Stack after adding 6: 6, 7

Element we are at 5:

Stack after removing elements: 6, 7 (6 is bigger than 5)

Answer array: 6, 7, 7, 2, 4, 4, 3

Stack after adding 5: 5, 6, 7.

So now you have the answer. It is clear that this is O(n) because you will only add and remove each element from the stack at most once. Also I hope that the simulation will intuitively make you understand why this works.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Btw I did the question in the last contest and implemented this idea. Here is the submission: https://codeforces.com/contest/1719/submission/168584747

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so so much. I was really looking for such kind of explanation. My doubts are clear now. It was really worthy and helpful for me. Thanks a lot for your response and such explanation :)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No problem, but this is a fairly standard and well known algorithm. You should probably try to research a little more bfore asking here. Also, ignore the code that i shared. It doesnt use this algorithm. However it shows that you dont really need this algorithm for this question

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was stuck with this problem for some days and my brain got exhausted that's why I asked here. By the way I will keep it in my mind before asking anything in the blog section. Again thanks a lot for your co-operation :)