Find the index of the closest number that is greater than the current number

user_11102816 0
Viewed 794

For each integer in an array of positive integers, find the index of the closest integer that is greater than the current integer. Also, we need to search for the answer only to the left of the current integer.

For example -

Input array - [ 5, 4, 3, 6, 2, 3]
Output array - [ -1, 0, 1, -1, 3, 3]

Assign -1 to those numbers which don't have an answer.

There is a simple O(n^2) method, for each number run a for loop from the previous number to the beginning of the array.

for(int i=0; i<n; ++i)
{
    output[i] = -1;
    for(int j=i-1; j>=0; --j)
    {
        if(input[j] > input[i])
        {
            output[i] = j;
            break;
        }
    }
}

This method is inefficient when 'n' is large. Is there a more efficient way?

algorithm c++
2 Answers

The proposed answer is an adaption of : https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

The main idea is to use a stack to remember processed value. In the link, they care about the value but it can easily be adapted to output indices.

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

std::vector<int> function(std::vector<int> input) {
    std::vector<int> output;
    output.reserve(input.size());

    // Create an empty stack 
    // first element of the pair is the index. second is the value
    std::stack<std::pair<int,int>> S; 
  
    // Traverse all array elements 
    for (int i=0; i<input.size(); i++) 
    { 
        // Keep removing top element from S while the top 
        // element is less than or equal to arr[i] 
        while (!S.empty() && S.top().second <= input[i]) 
            S.pop(); 
  
        // If all elements in S were greater than arr[i] 
        if (S.empty()) 
            output.push_back(-1);
        else  //Else print the nearest smaller element
            output.push_back(S.top().first);

  
        // Push this element 
        S.push({i, input[i]}); 
    } 
    
    return output;
}

int main() {
    std::vector<int> input{5, 4, 3, 6, 2, 3};
    std::vector<int> output = function(input);

    for(int index : output) {
        std::cout << index << ' ';
    }

    return 0;
}

Output:

-1 0 1 -1 3 3

Compiler explorer : https://godbolt.org/z/8W3ecv

user_139107440

I believe one popular O(n) solution is to use a stack, maintaining a descending sequence (hopefully the algorithm is clear enough from the commented code):

function f(A){
  let stack = []
  let output = []

  for (let i=0; i<A.length; i++){
    // While there are lower or
    // equal elements on top of
    // the stack
    while (stack.length && A[ stack[stack.length-1] ] <= A[i])
      stack.pop();
    
    // The next greater element
    // to the left
    if (stack.length)
      output.push(stack[stack.length-1]);
    // There was none
    else
      output.push(-1);

    stack.push(i);
  }

  return output;
}

var As = [
  [5, 4, 3, 6, 2, 3],
  [1, 2, 3, 4, 5],
  [5, 4, 3, 2, 1],
  [0, 3, -1, 5, 4]
];

for (let A of As){
  console.log(`${ A }`);
  console.log(`${ f(A) }`);
  console.log('');
}

user_20347870
Related