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

Question

It is easy to come up with an O(n) algorithm to solve this very famous question:

For every element in the list, find the first element that is larger than it. This can be done using a stack. But, what if I want to find the first element that is larger than n*current element?

More specifically:

Given an array [2, 5, 4, 7, 3, 8, 9, 6] and n = 2.

I want [5, -1, 9, -1, 8, -1, -1, -1] For 2, 5 is the next element larger than n * 2, for 4, 9 is the next element larger than n * 4. For 5, there is no element larger than n * 5 so return -1 at that position.

Can we do better than O(n^2)?

Answer 1

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