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

Question

Given an array find the next smaller element in array for each element without changing the original order of the elements.

For example, suppose the given array is 4,2,1,5,3.

The resultant array would be 2,1,-1,3,-1.

I was asked this question in an interview, but i couldn't think of a solution better than the trivial O(n^2) solution. Any approach that I could think of, i.e. making a binary search tree, or sorting the array, will distort the original order of the elements and hence lead to a wrong result.

Any help would be highly appreciated.

Answer 1

O(N) Algorithm

1. Initialize output array to all -1s.
2. 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.
3. 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.

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

Answer 3

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

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

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

Answer 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]

Answer 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]

Answer 6

Time complexity O(N), space complexity O(N).

Clean solution on java keeping order of the array:

public static int[] getNGE(int[] a) {
    var s = new Stack<Pair<Integer, Integer>>();
    int n = a.length;
    var result = new int[n];
    s.push(Pair.of(0, a[0]));

    for (int i = 1; i < n; i++) {
        while (!s.isEmpty() && s.peek().v2 > a[i]) {
            var top = s.pop();
            result[top.v1] = a[i];
        }
        s.push(Pair.of(i, a[i]));
    }

    while (!s.isEmpty()) {
        var top = s.pop();
        result[top.v1] = -1;
    }

    return result;
}

static class Pair<K, V> {
    K v1;
    V v2;

    public static  <K, V> Pair<K, V> of (K v1, V v2) {
        Pair p = new Pair();
        p.v1 = v1;
        p.v2 = v2;
        return p;
    }
}

Answer 7

Here is an observation that I think can be made into an O(n log n) solution. Suppose you have the answer for the last k elements of the array. What would you need in order to figure out the value for the element just before this? You can think of the last k elements as being split into a series of ranges, each of which starts at some element and continues forward until it hits a smaller element. These ranges must be in descending order, so you could think about doing a binary search over them to find the first interval smaller than that element. You could then update the ranges to factor in this new element.

Now, how best to represent this? The best way I've thought of is to use a splay tree whose keys are the elements defining these ranges and whose values are the index at which they start. You can then in time O(log n) amortized do a predecessor search to find the predecessor of the current element. This finds the earliest value smaller than the current. Then, in amortized O(log n) time, insert the current element into the tree. This represents defining a new range from that element forward. To discard all ranges this supercedes, you then cut the right child of the new node, which because this is a splay tree is at the root, from the tree.

Overall, this does O(n) iterations of an O(log n) process for total O(n lg n).

Answer 8

Here is a O(n) algorithm using DP (actually O(2n) ):

int n = array.length();

The array min[] record the minimum number found from index i until the end of the array.

int[] min = new int[n];
min[n-1] = array[n-1];
for(int i=n-2; i>=0; i--)
   min[i] = Math.min(min[i+1],array[i]);

Search and compare through the original array and min[].

int[] result = new int[n];
result[n-1] = -1;
for(int i=0; i<n-1; i++)
   result[i] = min[i+1]<array[i]?min[i+1]:-1;

Here is the new solution to find "next smaller element":

int n = array.length();
int[] answer = new int[n];
answer[n-1] = -1;
for(int i=0; i<n-1; i++)
   answer[i] = array[i+1]<array[i]?array[i+1]:-1;

Answer 9

        All that is actually not required i think

    case 1: a,b
    answer : -a+b

    case 2: a,b,c
    answer : a-2b+c

    case 3: a,b,c,d
    answer : -a+3b-3c+d

    case 4 :a,b,c,d,e
    answer : a-4b+6c-4d+e

    .
    .
    .
    recognize the pattern in it?
    it is the pascal's triangle!
                                   1
                                1     1
                              1    2     1
                           1    3     3     1
                        1    4     6     4     1
    so it can be calculated using Nth row of pascal's triangle!
    with alternate + ans - for odd even levels!
    it is O(1)

Answer 10

You can solve this in O(n) runtime with O(n) space complexity. Start with a Stack and keep pushing elements till you find arr[i] such that arr[i] < stack.top element. Then store this index .

Code Snippet:

vector<int> findNext(vector<int> values) {

    stack<int> st;
    vector<int> nextSmall(values.size(), -1);
    st.push(0);

    for (int i = 1; i < values.size(); i++) {
        while (!st.empty() && values[i] < values[st.top()]) {  
      // change values[i] < values[st.top()] to values[i] > values[st.top()] to find the next greater element.
            nextSmall[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
     return nextSmall;
}

Answer 11

Solution With O(n) Time Complexity and O(1) Space Complexity. This Solution is not complex to understand and implemented without stack.

def min_secMin(a,n):
    min = a[0]
    sec_min = a[1]
    for i in range(1,n):
        if(a[i]<min):
              sec_min = min
              min = a[i]
        if(a[i]>min and a[i]<sec_min):
              sec_min = a[i]

return min,sec_min

Answer 12

Solution with O(1) space complexity and O(n) time complexity.

void replace_next_smallest(int a[], int n)                                                          
    {                                                                                                   
        int ns = a[n - 1];                                                                              
        for (int i = n - 1; i >= 0; i--) {                                                              
            if (i == n - 1) {                                                                           
                a[i] = -1;                                                                              
            }                                                                                           
            else if (a[i] > ns) {                                                                       
                int t = ns;                                                                             
                ns = a[i];                                                                
                a[i] = t;                                                                               
            }                                                                                           
            else if (a[i] == ns) {                                                                      
                a[i] = a[i + 1];                                                                        
            }                                                                                           
            else {                                                                                      
                ns = a[i];                                                                              
                a[i] = -1;                                                                              
            }                                                                                           
        }                                                                                               
    }