Find the first element that is n times larger than current element in a list

I agree with OP that, the simple predicate of the O(N) algo might not work on the stack-based solution when looking for the first element > 2x in the remaining array.

I found a O(NlogN) solution for this btw.

It uses a Min-heap to maintain the frontier elements we are interested in.

Pseudo-code:

def get_2x_elements(input_list, multipler = 2):
  H = [] #min-heap with node-values as tuples (index, value)
  R = [-1 for _ in range(len(input_list))] # results-list

  for index, value in enumerate(input_list):
    while multiplier*H[0][1] < value:
      minval = extractMinFromHeap(H)
      R[minval[0]] = value

  insertToMinHeap(H, (index, value))

  return R

Complexity-analysis:

1. Insertion/Extraction from min-heap = O(logN)
2. Number of such operations = N

Total-complexity = O(NlogN)

PS: This assumes we need the first >2x element from the remaining part of the list.

Re: I made a Java verion implementation of your idea. Thanks @Serial Lazer

    private static class ValueAndIndexPair implements Comparable<ValueAndIndexPair>{
        public final double value;
        public final int index;

        public ValueAndIndexPair(double value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(ValueAndIndexPair other) {
            return Double.compare(value, other.value);
        }
    }

    public static double[] returnNextNTimeLargerElementIndex(final List<Double> valueList, double multiplier) {
        double[] result = new double[valueList.size()];
        PriorityQueue<ValueAndIndexPair> minHeap = new PriorityQueue<>();

        // Initialize O(n)
        for (int i = 0; i < valueList.size(); i++) {
            result[i] = -1.0;
        }
        if (valueList.size() <= 1) return result;

        minHeap.add(new ValueAndIndexPair(valueList.get(0) * multiplier, 0));

        for (int i = 1; i <valueList.size(); i++) {
            double currentElement = valueList.get(i);
            while (!minHeap.isEmpty() && minHeap.peek().value < currentElement) {
                result[minHeap.poll().index] = currentElement;
            }
            minHeap.add(new ValueAndIndexPair(currentElement * multiplier, i));
        }
        return result;
    }

Sure, easily.

We just need a sorted version of the array (sorted elements plus their original index) and then we can do an efficient search (a modified binary search) that points us to the start of the elements that are larger than the current number (or a multiple of it, it doesn't matter). Those elements we can then search sequentially for the one with the smallest index (that is greater than the one of the current number, if so required).

Edit: It was pointed out that the algorithm may not be better than O(n²) because of the sequential search of the elements that satisfy the condition of being greater. This may be so, I'm not sure. But note that we may build a more complex search structure that involves the index already, somehow. This is left as homework. :)

The stack-based solution offered at geeksforgeeks does not seem to maintain the order of the elements in the result even in its output:

input: int arr[] = { 11, 13, 21, 3 };
output: 
 11 -- 13
 13 -- 21
 3 -- -1
 21 -- -1

After minor modification to find the first element which is greater N times than a current, this algorithm fails to detect 9 for the element 4 from the given example.

Online demo

input: int arr[] = { 2, 5, 4, 7, 3, 8, 9, 6 }; // as in this question
output: 
2 * 2 --> 5
2 * 3 --> 8
6 -- -1
9 -- -1
8 -- -1
7 -- -1
4 -- -1
5 -- -1

Thus, initial assumption about existing solution with complexity O(N) is not quite applicable to the expected result.