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

Question

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 ?

Answer 1

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;
    }
}