CODEWITHSUNDEEP
arraysalgorithmdata-structures
user12073121
user12073121

Reputation: 81

Farthest Smaller Element in an Array

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"

Upvotes: 4

Views: 3541

Answers (3)

AMIT SINGH
AMIT SINGH

Reputation: 1

    int arr[]={6,3,1,8,2,9,7};
    for(int i=0;i<arr.length;i++){
        int min=-1;
        for(int j=i+1;j<arr.length;j++){
            if(arr[j]<arr[i]){
                min=arr[j];
            }
        }
        arr[i]=min;
    }

Upvotes: 0

Quynh Tran
Quynh Tran

Reputation: 86

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).

Upvotes: 7

nice_dev
nice_dev

Reputation: 17825

  • The basic idea behind the getting the answer quickly is to use a stack when moving from right to left in the array.

  • We insert an element in the stack only in one of the below 2 conditions,

    • If the stack is empty.
    • If the current top element in the stack is greater than the current element in iteration.

  • This would ensure us the correct results since a number greater than the current element in iteration will always be anyway greater than the current element at the top of the stack and current top at stack also wins over the farthest criteria.

  • So, insert in stack only if less than the current top.

  • However, it's quite possible that current element in iteration has many elements in stack smaller than itself. So, we need to go deep in stack till we find an element in stack greater than the current one.

Implementation(in java):

    int[] arr = {6,3,1,8,2,9,7};
    Stack<Integer> st1 = new Stack<Integer>();
    Stack<Integer> st2 = new Stack<Integer>();
    List<Integer> result = new ArrayList<>();

    for(int i=arr.length-1;i>=0;--i){
        while(!st1.isEmpty() && arr[(int)st1.peek()] < arr[i]){
            st2.push(st1.pop());
        }

        if(st2.isEmpty()) result.add(-1);
        else result.add(arr[(int)st2.peek()]);

        while(!st2.isEmpty()) st1.push(st2.pop());

        if(st1.isEmpty() || arr[(int)st1.peek()] > arr[i]){
            st1.push(i);
        }
    }
  • The above implementation follows the explanation provided.
  • We use 2 stacks to not lose the popped data as it would be useful for future elements.
  • So, we revert all back to the main stack once the answer is found for the current element.

Demo: https://ideone.com/0oAasu

Note: You can directly store elements in the stack instead of indexes to make it more simpler.

Update: This solution's complexity is indeed O(n^2) for case where array could have elements in [ n/2, n/2 ,.. n/2, 1, 2, .. n/2] fashion for an array of size 10^5 or more. See Quynh Tran's answer for a better solution.

Upvotes: 2

Related Questions