find every pair of smallest integer for each subarray of given array in O(n)?

Question

I have a problem. Given an array, find the smallest integer and the second smallest integer for all possible subarrays, where a subarray is a contiguous subset of the original array.

Consider for example an array A = [5, 6, 1, 2, 9, 3]. Obviously the subarray size would be atleast 2, so we have a total of (n) * (n+1) /2 - n subarrays. ( subtracting n subarrays of size 1 from total). That is a straighforward O(n^2) solution, checking each subarray and recording the required integers. But i think it can be done in O(n) using stacks. But i am unable to use it intuitively to arrive at an optimal solution. Any help, advice, direction would be appreciated.

marvel308 marvel308 · Accepted Answer · 2017-09-26T11:55:29

Yes it can be done in O(n), The idea is used to solve this question.

For each int i in the array A
    while stack is nonempty
        // current min is stack.top() and A[i]
        if i is less than the top of the stack, pop the stack
        otherwise break the while loop
    If stack is non empty
        // current min is stack.top() and A[i]
    push i onto stack

Basic idea is that if you have a value b in your stack, and you encounter a value c which is smaller, then b cannot form a minimum pair with anything to the right of c. So once you yield the pair (b,c) you can safely dispose of b (you already handled possible pairs to the left).

check it out in the online compiler

find every pair of smallest integer for each subarray of given array in O(n)?

1 Answers