Next greater element over a certain percentage of each element in array-CodePudding

I have seen some posts about next greater element. I am looking for a more performant solution for one of its variant.

The problem : I have an array of numbers. I want to know for each number, the next index where the value become bigger than a percentage of X.

Example : Let's suppose I have this array [1000, 900, 1005, 1022, 1006] and I set a target of 1%. Meanwhile, I want to know when the value become 1% bigger than it was.

1000 -> We want to know when value become bigger of equal to 1010    -> Index = 3
 900 -> We want to know when value become bigger of equal to  909    -> Index = 2
1005 -> We want to know when value become bigger of equal to 1015.05 -> Index = 3
1022 -> We want to know when value become bigger of equal to 1030.2  -> Index = -1
1006 -> We want to know when value become bigger of equal to 1016.06 -> Index = -1

Naïve solution : An O(n^2) algorithm can solve the problem. But it's too slow for my needs.

Does anyone know a faster algorithm to solve this problem or one of its close variant ?

CodePudding user response：

You can create a list of tuples of index and value in array. Sort the list by value. Then you can iterate over the list using two pointers finding values that are greater by the given percentage and capture the corresponding indices. Complexity would be O(nlogn)

Sample implementation in java 17 given below:

final double percentage = 1.01;

int[] arr = new int[]{1000, 900, 1005, 1022, 1006};

record KeyValuePair(int value, int index) {}

List<KeyValuePair> keyValuePairs = new ArrayList<>();
for (int i = 0; i < arr.length;   i) {
    keyValuePairs.add(new KeyValuePair(arr[i], i));
}

keyValuePairs.sort(Comparator.comparingInt(KeyValuePair::value));

int i = 0, j = 1;
while (i != keyValuePairs.size() && j != keyValuePairs.size()) {
    if (keyValuePairs.get(i).value() * percentage < keyValuePairs.get(j).value()) {
        if (keyValuePairs.get(i).index() < keyValuePairs.get(j).index()) {
            System.out.println("For index "   keyValuePairs.get(i).index()   " -> "   keyValuePairs.get(j).index());
        } else if (keyValuePairs.get(i).index()   1 != keyValuePairs.size()) {
            System.out.println("For index "   keyValuePairs.get(i).index()   " -> "   (keyValuePairs.get(i).index()   1));
        }
          i;
    } else {
          j;
    }
}

CodePudding user response：

I'd use a min heap. Each element in the min heap is a tuple (value, index) where value is the target value, and index is the index in the input array where that target value originated.

Then the algorithm is:

create an output array with all elements set to -1
for each element in the input array
   for each target value on the min heap less than the element's value
      pop the (targetValue, targetIndex) tuple
      record the index of the current input element at the target index
   add the current element (value, index) tuple to the min heap

For example, given the array in the question, the algorithm performs the following steps:

Create an output array with all elements set to -1
Read 1000, put (1010, 0) in the min heap.
Read 900, put (909, 1) in the min heap.
Read 1005. That's larger than 909, so pop the (909, 1), and record index 2 as the answer for element 909. Put (1015.05, 2) in the min heap.
Read 1022. Pop (1010, 0) and then (1015.05, 2) from the min heap, recording index 3 as the answer for elements 1000 and 1005. Put (1030.2, 3) in the min heap.
Read 1006, put (1016.06, 4) in the min heap.
Since the end of the input array has been reached, (1030.2, 3) and (1016.06, 4) will never be popped, and the corresponding elements in the output array remain as -1

Running time is O(nlogn).

Sample python implementation:

from heapq import heappush, heappop

def nextGreater(inputArray):
    targetHeap = []
    outputArray = [-1] * len(inputArray)
    for inputIndex, inputValue in enumerate(inputArray):
        while targetHeap and targetHeap[0][0] < inputValue:
            targetValue, targetIndex = heappop(targetHeap)
            outputArray[targetIndex] = inputIndex
        heappush(targetHeap, (inputValue * 1.01, inputIndex))
    return outputArray

inputArray = [1000, 900, 1005, 1022, 1006]
outputArray = nextGreater(inputArray)
print outputArray  # [3, 2, 3, -1, -1]