3

Description of Algorithm

For each element in the input array, the corresponding output is the first number that follows the input element, that is greater than the input element.

In other words, for a given input[i], the output[i] is some element input[j] where j is the minimum index such that j > i and input[j] > input[i]

Example

Input  12 15 22  9  7  2 18 23 27 
Output 15 22 23 18 18 18 23 27 -1

For example, the output that corresponds to 9 is 18 since 18 is the first number in the array that meets these requirements

  1. follows 9 in the input array
  2. is greater than 9

Question

Can anyone suggest me an algorithm better than O(n^2)?

user3386109
  • 34,287
  • 7
  • 49
  • 68
instance
  • 1,366
  • 15
  • 23
  • 2
    what are your thoughts on the matter? What do you think might work? – drew moore Jun 08 '14 at 04:42
  • I must be missing something. Why is 18 repeated three times, and why is there a -1 at the end? – IllusiveBrian Jun 08 '14 at 04:48
  • 18 is repeated because for 9 , 7 , 2 - 18 is the next greater number and -1 because there is no greater number after 27. – instance Jun 08 '14 at 04:49
  • @instance Your question is ambiguous - do you want to replace x with the first value after x in the original sequence that is larger than it, or by the smallest value greater than x out of all the elements that come after x? – templatetypedef Jun 08 '14 at 04:50
  • @templatetypedef i want to replace every a[i] with the new element which is the next immediate greater element than a[i]. – instance Jun 08 '14 at 04:52
  • @instance: That's not consistent with your example. If you're looking for that, the 4th element in the result would be 12, because 12 is the next greater element than 9. – Reto Koradi Jun 08 '14 at 05:00
  • @RetoKoradi - next immediate greater should be in the given order of array like arr[x] > arr[y] such that x>y. – instance Jun 08 '14 at 05:03
  • Shouldn't the second number output (the output value for 15 in the input array) be 18, not 22? – Michael Burr Jun 08 '14 at 07:41

2 Answers2

2

This can be done in O(N) time and O(N) extra memory space with the help of two stacks (one for indices and other for values).

I'll explain the algorithm with the help of your example.

Input  12 15 22  9  7  2 18 23 27 

Initialize Output Array O[] as all -1.

1. Start from the first element. Set CurrentElement = A[0] (12). index = 0   
2. Push A[index] in a Stack S_values. Push index in a Stack S_indices.  
3. Increment index.  
4. while ( S_values is not empty && A[index] is > than S_values.top() )  
   - Set output_index = S_indices.top()
   - set O[output_index] = A[index].  
   - S_values.pop()
   - S_indices.pop().      
5. If index < length(Input)-1 Goto Step 2.
6. Set O[index] = -1. // Last element.

This works because the top of the stack S_values shall always have the lowest value and the elements shall be popped out from it in ascending order. Similarly the stack S_indices shall always have the largest value on top and indices shall be popped out in descending order.

EDIT: Code in C++

#include <vector>
#include <stack>
#include <iostream>

using std::cout;
using std::endl;
using std::vector;
using std::stack;

int main()
{
    vector<int> Input = { 12, 15, 22,  9,  7,  2, 18, 23, 27};
    vector<int> Output( Input.size(), -1 );

    stack<int> S_values, S_indices;
    S_values.push( Input[0] );
    S_indices.push( 0 );
    for ( size_t index = 1; index < Input.size(); ++index )
    {
        while ( !S_values.empty() && Input[index] > S_values.top() )
        {
            size_t output_index = S_indices.top();
            Output[ output_index ] = Input[ index ];
            S_values.pop();
            S_indices.pop();

        }
        S_values.push( Input[index] );
        S_indices.push( index );
    }

    for ( auto &x : Output )
        cout << x << " ";
    cout << endl;

    return 0;
}

Output:

15 22 23 18 18 18 23 27 -1
Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
1

One approach is to use a stack, where each entry in the stack is a value:index pair. Iterate through the input array, popping items from the stack whose value is less than the value of the current item in the input array. Once all of the smaller values have been popped from the stack, push the current value:index pair onto the stack. When the end of the input array is reached, any remaining entries in the stack get an output value of -1 to indicate that no larger number was found.

Using the example in the question, here's how the algorithm would work

input item 12
    stack = 12:0

input item 15
    pop 12:0 and set output[0] = 15
    stack = 15:1

input item 22
    pop 15:1 and set output[1] = 22
    stack = 22:2

input item 9
    stack = 9:3, 22:2

input item 7
    stack = 7:4, 9:3, 22:2

input item 2
    stack = 2:5, 7:4, 9:3, 22:2

input item 18
    pop 2:5 and set output[5] = 18
    pop 7:4 and set output[4] = 18
    pop 9:3 and set output[3] = 18
    stack = 18:6, 22:2

input item 23
    pop 18:6 and set output[6] = 23
    pop 22:2 and set output[2] = 23
    stack = 23:7

input item 27
    pop 23:7 set output[7]= 27
    stack = 27:8

end of array
    pop 27:8 and set output[8] = -1
    done
user3386109
  • 34,287
  • 7
  • 49
  • 68