CODEWITHSUNDEEP
algorithmmathoptimization
user18068163
user18068163

Reputation:

Given unsorted array, for each element, find index of the earliest next element that is larger than it

I have an unsorted array with distinct numbers.

[4, 2, 1, 3, 5]

I would like an output of all the possible pairs (i, j) meaning the next earliest number larger than array[i] is at array[j]. *** Special case: if you notice the reverse of the sample input, [5, 3, 1, 2, 4], there is no element greater than 5. As a result, there is no pair.

For the original input, answer would be [[0, 4], [1, 3], [2, 3], [3, 4]]

An O(n^2) solution would just be start at index i and then loop to the end and stop when reaching an element that is greater than array[i]. Is there a way to bring this down to O(n log n) or O(n)?

Upvotes: 1

Views: 125

Answers (1)

maraca
maraca

Reputation: 8743

You can get the result in O(n) using a stack. Either going forward or backwards. But going forward the output will not be sorted. Unshift puts an element in front. The idea is that we can always use the top of the stack and discard what doesn't matter any more, so we push and pop everything on the stack just once.

function pairs(arr) {
    let stack = [], solution = []
    for (let i = arr.length - 1; i >= 0; i--) {
        while (stack.length > 0 && stack[stack.length - 1][0] < arr[i])
            stack.pop() //         ^^^^^^^^^^peek^^^^^^^^^
        if (stack.length > 0)
            solution.unshift([i, stack[stack.length - 1][1]])
        stack.push([arr[i], i])
    }
    return solution
}
console.log(pairs([4, 2, 1, 3, 5]))

Upvotes: 1

Related Questions