CODEWITHSUNDEEP
algorithmdata-structuresdynamic-programmingrecursive-datastructures
Murali Krishna Bellamkonda
Murali Krishna Bellamkonda

Reputation: 447

How to find previous smallest element of a given index in the array?

For example, I have an 

input array 
[1,3,5,6,4,8,4,3,2,1]

the output should be [-1 , 1, 3, 5, 3 , 6, 3, 1, 1, -1]

Explanation: let's keep the first element as -1, as there is no smaller one previous to that.

In index '1' the previous smaller element to 3 needs to be stored. i.e 1.

In index '2' the previous smaller element to 5 needs to be stored. i.e 3. & so on...

I know I can solve this problem in O(n2) complexity. But I Would like to solve this in O(n) complexity. I have tried, but I am unable to do it.

Please help me to solve this problem. Thanks in Advance.

Upvotes: 1

Views: 1319

Answers (3)

Sagar Chandgadkar
Sagar Chandgadkar

Reputation: 1

 //NEAREST SMALLEST TO LEFT'S INDEX
    //CREATE A NEW STACK
    Stack<Integer> stack = new Stack<>();
    //ARRAY TO STORE OUTPUT VALUES
    int[] ans = new int[n];
    //TRAVERSE FROM LEFT TO RIGHT OF INPUT ARRAY
    for(int i=0; i<n; i++){
        //HERE WE PERFORM 3 OPERATIONS
        /* 1ST) WHILE STACK IS NOT EMPTY
        IF YOU FIND ANYTHING >= TO ARR[I] POP*/
        while(!stack.empty() && arr[stack.peek()] >= arr[i]){
            stack.pop();
        }
        /* 2ND) IF STACK IS EMPTY RETURN -1 
          (WHATEVER AS PER YOUR NEED) */
        if(stack.empty()){
            ans[i] = -1;
        }
        /* 3RD) WE FOUND NEAREST SMALLEST TO LEFT */
        else{
            ans[i] = stack.peek();
        }
        //PUSH INDEX TO STACK
        stack.push(i);
       
    }

Upvotes: 0

Maras
Maras

Reputation: 982

O(n) is probably impossible, but I can give you O(n log n) approach. Create a balanced BST (set/dictionary structure in most of programming languages). You can now easily find the largest number smaller than x by traversing a tree.

Set/dictionary structure often have a built-in function called upper bound, that find you smallest element larger than x (or largest smaller if you decide to change sorting order). You may also use that.

All you need to do is:

For each value v in the array:

  • find the largest number smaller than v in BST,

  • insert v into BST

Upvotes: 3

visleck
visleck

Reputation: 331

I think you want to solve it in O(n) time. You can find your answer here: https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

Upvotes: 2

Related Questions