Given an array, find out the next smaller element for each element

Solution 1:

O(N) Algorithm

Initialize output array to all -1s.
Create an empty stack of indexes of items we have visited in the input array but don't yet know the answer for in the output array.
Iterate over each element in the input array:
1. Is it smaller than the item indexed by the top of the stack?
  1. Yes. It is the first such element to be so. Fill in the corresponding element in our output array, remove the item from the stack, and try again until the stack is empty or the answer is no.
  2. No. Continue to 3.2.
2. Add this index to the stack. Continue iteration from 3.

Python implementation

def find_next_smaller_elements(xs):
    ys=[-1 for x in xs]
    stack=[]
    for i,x in enumerate(xs):
        while len(stack)>0 and x<xs[stack[-1]]:
           ys[stack.pop()]=x
        stack.append(i)
    return ys

>>> find_next_smaller_elements([4,2,1,5,3])
[2, 1, -1, 3, -1]
>>> find_next_smaller_elements([1,2,3,4,5])
[-1, -1, -1, -1, -1]
>>> find_next_smaller_elements([5,4,3,2,1])
[4, 3, 2, 1, -1]
>>> find_next_smaller_elements([1,3,5,4,2])
[-1, 2, 4, 2, -1]
>>> find_next_smaller_elements([6,4,2])
[4, 2, -1]

Explanation

How it works

This works because whenever we add an item to the stack, we know its value is greater or equal to every element in the stack already. When we visit an element in the array, we know that if it's lower than any item in the stack, it must be lower than the last item in the stack, because the last item must be the largest. So we don't need to do any kind of search on the stack, we can just consider the last item.

Note: You can skip the initialization step so long as you add a final step to empty the stack and use each remaining index to set the corresponding output array element to -1. It's just easier in Python to initialize it to -1s when creating it.

Time complexity

This is O(N). The main loop clearly visits each index once. Each index is added to the stack exactly once and removed at most once.

Solving as an interview question

This kind of question can be pretty intimidating in an interview, but I'd like to point out that (hopefully) an interviewer isn't going to expect the solution to spring from your mind fully-formed. Talk them through your thought process. Mine went something like this:

Is there some relationship between the positions of numbers and their next smaller number in the array? Does knowing some of them constrain what the others might possibly be?
If I were in front of a whiteboard I would probably sketch out the example array and draw lines between the elements. I might also draw them as a 2D bar graph - horizontal axis being position in input array and vertical axis being value.
I had a hunch this would show a pattern, but no paper to hand. I think the diagram would make it obvious. Thinking about it carefully, I could see that the lines would not overlap arbitrarily, but would only nest.
Around this point, it occurred to me that this is incredibly similar to the algorithm Python uses internally to transform indentation into INDENT and DEDENT virtual tokens, which I'd read about before. See "How does the compiler parse the indentation?" on this page: http://www.secnetix.de/olli/Python/block_indentation.hawk However, it wasn't until I actually worked out an algorithm that I followed up on this thought and determined that it was in fact the same, so I don't think it helped too much. Still, if you can see a similarity to some other problem you know, it's probably a good idea to mention it, and say how it's similar and how it's different.
From here the general shape of the stack-based algorithm became apparent, but I still needed to think about it a bit more to be sure it would work okay for those elements that have no subsequent smaller element.

Even if you don't come up with a working algorithm, try to let your interviewer see what you're thinking about. Often it is the thought process more than the answer that they're interested in. For a tough problem, failing to find the best solution but showing insight into the problem can be better than knowing a canned answer but not being able to give it much analysis.

Solution 2:

Start making a BST, starting from the array end. For each value 'v' answer would be the last node "Right" that you took on your way to inserting 'v', of which you can easily keep track of in recursive or iterative version.

UPDATE:

Going by your requirements, you can approach this in a linear fashion:

If every next element is smaller than the current element(e.g. 6 5 4 3 2 1) you can process this linearly without requiring any extra memory. Interesting case arises when you start getting jumbled elements(e.g. 4 2 1 5 3), in which case you need to remember their order as long as you dont' get their 'smaller counterparts'. A simple stack based approach goes like this:

Push the first element (a[0]) in a stack.

For each next element a[i], you peek into the stack and if value ( peek() ) is greater than the one in hand a[i], you got your next smaller number for that stack element (peek()) { and keep on popping the elements as long as peek() > a[i] }. Pop them out and print/store the corresponding value. else, simply push back your a[i] into the stack.

In the end stack 'll contain those elements which never had a value smaller than them(to their right). You can fill in -1 for them in your outpput.

e.g. A=[4, 2, 1, 5, 3];

stack: 4
a[i] = 2, Pop 4, Push 2 (you got result for 4)
stack: 2
a[i] = 1, Pop 2, Push 1 (you got result for 2)
stack: 1
a[i] = 5
stack: 1 5
a[i] = 3, Pop 5, Push 3 (you got result for 5)
stack: 1 3
1,3 don't have any counterparts for them. so store -1 for them.

Solution 3:

Assuming you meant first next element which is lower than the current element, here are 2 solutions -

Use sqrt(N) segmentation. Divide the array in sqrt(N) segments with each segment's length being sqrt(N). For each segment calculate its' minimum element using a loop. In this way, you have pre-calculated each segments' minimum element in O(N). Now, for each element, the next lower element can be in the same segment as that one or in any of the subsequent segments. So, first check all the next elements in the current segment. If all are larger, then loop through all the subsequent segments to find out which has an element lower than current element. If you couldn't find any, result would be -1. Otherwise, check every element of that segment to find out what is the first element lower than current element. Overall, algorithm complexity is O(N*sqrt(N)) or O(N^1.5).

You can achieve O(NlgN) using a segment tree with a similar approach.

Sort the array ascending first (keeping original position of the elements as satellite data). Now, assuming each element of the array is distinct, for each element, we will need to find the lowest original position on the left side of that element. It is a classic RMQ (Range Min Query) problem and can be solved in many ways including a O(N) one. As we need to sort first, overall complexity is O(NlogN). You can learn more about RMQ in a TopCoder tutorial.

Solution 4:

For some reasons, I find it easier to reason about "previous smaller element", aka "all nearest smaller elements". Thus applied backward gives the "next smaller".

For the record, a Python implementation in O(n) time, O(1) space (i.e. without stack), supporting negative values in the array :

def next_smaller(l):
    """ Return positions of next smaller items """
    res = [None] * len(l)
    for i in range(len(l)-2,-1,-1):
        j=i+1
        while j is not None and (l[j] > l[i]):
            j = res[j]
        res[i] = j
    return res

def next_smaller_elements(l):
    """ Return next smaller items themselves """
    res = next_smaller(l)
    return [l[i] if i is not None else None for i in res]

Solution 5:

Here is the javascript code . This video explains the Algo better

function findNextSmallerElem(source){
    let length = source.length;
    let outPut = [...Array(length)].map(() => -1);
    let stack = [];
    for(let i = 0 ; i < length ; i++){
        let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val;
        // If stack is empty or current elem is greater than stack top
        if(!stack.length || source[i] > stackTopVal ){
            stack.push({ val: source[i], ind: i} );
        } else {
            // While stacktop is greater than current elem , keep popping
            while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){
                outPut[stack.pop().ind] = source[i];
            }
            stack.push({ val: source[i], ind: i} );
        }
    }
    return outPut;
}

Output -

findNextSmallerElem([98,23,54,12,20,7,27])

[23, 12, 12, 7, 7, -1, -1]