CODEWITHSUNDEEP
c++arraysalgorithm
ashkan_d13
ashkan_d13

Reputation: 53

Find nearest bigger value for all elements of array

I'm looking for a fast algorithm (or any hints) to do this;

Here is a sample and O(n^2) implementation

    std::vector<double> v = { 3, 1.5, 4, 2, 5 };
    
    std::vector<int> out(v.size());
    
    for (int i = 0; i < v.size(); i++)
    {
        out[i] = -1;
        for (int j = i + 1; j < v.size(); j++)
        {
            if (v[j] > v[i])
            {
                out[i] = j;
                break;
            }
        }
    }
            
    for (int i : out) std::cout << i << ' '; // => 2 2 4 4 -1

Upvotes: 0

Views: 437

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

It could be done easily using stack in O(n) time complexity by following the steps mentioned below:

Step-1: Maintain a stack that could store indices.

Step-2: Iterate through the array and check the following condition: Condition: If the element of the array at the index at top of the array is less than the element at the current index then the nearest bigger element for the index at the top is the current one.

Step-3: Push the current index to the stack.

Example: [8,4,2,5,9]

dp = [-1,-1,-1,-1,-1] # Array to store the indexes

Iteration-1:

Element = 8

Stack = [] # Empty

Push 0 to stack (index of 8)

Iteration-2:

Element = 4

Stack = [0]

Push 1 to stack (index of 4)

Iteration-3:

Element = 2

Stack = [0,1]

Push 2 to stack (index of 2)

Iteration-4:

Element = 5

Stack = [0,1,2]

Pop from stack -> 2 element = 2

dp[2] = 3

Pop from the stack -> 1 element = 4

dp[1] = 3

Push 3 to stack (index of 5)

Iteration-5:

Element = 9

Stack = [0,3]

Pop from stack -> 3 element = 5

dp[3] = 4

Pop from the stack -> 0 element = 8

dp[0] = 4

Push 4 to stack (index of 9)

Now your answer for array = [8 4 2 5 9] is stored in array dp:

[4,3,3,4,-1]

Upvotes: 2

Related Questions