Farthest Smaller Element in an Array

Question

In an unsorted positive integer array, how to find out the farthest smaller element on the right side of each element in most efficient way?

Ex:
Input: 6 3 1 8 2 9 7
Output: 2 2 -1 7 -1 7 -1

Explanation:

For 6, the smaller elements on it's right side are [3, 1, 2]. Since the last smallest element is 2, it's the most farthest from 6. Like wise for others. If no such number exists answer is "-1"

Answer 1

One idea is:

• let us call the original array A
• keep an array min[] of size n of which min[i] means the minimum value of the sub-array A[i..n-1]. Obviously, min[i] <= min[i+1].
• now move from right to left on A. At every index i, do a binary search on min[i+1..n-1] to find the farthest smaller value.

Java code:

    int[] A = { 6, 2, 3, 10, 1, 8 };
    int n = A.length;
    // calculate min
    int[] min = new int[n];
    min[n - 1] = A[n - 1];
    for (int i = n - 2; i >= 0; i--)
        min[i] = Math.min(A[i], min[i + 1]);
    // calculate results
    int[] results = new int[n];
    results[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) {
        int left = i; // after the binary search, A[left] would be the answer
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (min[mid] < A[i])
                left = mid;
            else
                right = mid - 1;
            if (min[left] < A[i])
                results[i] = min[left];
            else
                results[i] = -1;
        }
    }

Space complexity O(n)

Time complexity O(nlogn) for all cases.

Compared to the solution from @vivek_23, the above algorithm would be better in the following worst case:

Imagine the case of A of n elements as follows

A = [ n/2 n/2 .. n/2 1 2 .. n/2]

If we use the stack solution suggested by @vivek_23,

• at the step to find the farthest smaller element of any of the first n/2 elements (which are all valued n/2), st1 should be now [1 2 .. n/2]
• for each element valued n/2, all st1 elements except n/2 will be transferred to st2 in order to find the farthest smaller element n/2 - 1. After that all elements in st2 will be transferred back to st1. This results in the worst case performance of O(n). As there are n/2 elements, the total worst time performance is O(n^2).