By: Saurav

2018-02-11 11:01:00 UTC

Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

G[i] for an element A[i] = an element A[j] such that
j is maximum possible AND
j < i AND
A[j] < A[i]
Elements for which no smaller element exist, consider next smaller element as -1.


Input : A : [4, 5, 2, 10, 8]
Return : [-1, 4, -1, 2, 2]

Example 2:

Input : A : [3, 2, 1]
Return : [-1, -1, -1]


This problem is very simple if you use an O(n^2) approach:
Iterate through the array on index
For each array iterate again through all the lesser elements starting from the index-1 positon till 0.
When you find an element where a[i] < a[j]: Add to the final array
else, add -1

One thing to notice is that for each element at position index, we are using the last element in the sequence 0..index-1, where the element is smaller. Otherwise, we are continuing the search.

This pattern is similar to the use of Stack data structure. The only difference is we are not popping if we find such an element. In summary, the algorithm is:

Let input sequence be 'arr[]' and size of array be 'n'

New empty stack S

For every element 'arr[i]' in the input sequence 'arr[]',
where 'i' goes from 0 to n-1.
while S is nonempty and the top element of
S is greater than or equal to 'arr[i]':
pop S

if S is empty:
'arr[i]' has no preceding smaller value
the nearest smaller value to 'arr[i]' is
the top element of S

push 'arr[i]' onto S

Lets write some tests and see it in action:

p prevSmaller([ 34, 35, 27, 42, 5, 28, 39, 20, 28 ]) == [-1, 34, -1, 27, -1, 5, 28, 5]
p prevSmaller([4, 5, 2, 10, 8]) == [-1, 4, -1, 2, 2]
p prevSmaller([3, 2, 1]) == [-1, -1, -1]

   def prevSmaller(a)
            return [] if a.size < 1
            return [-1] if a.size == 1
            mystack = []
            final = []
            a.each do |i|
                while !mystack.empty? and i <= mystack[-1]
                if mystack.empty?
                    final << -1
                    final << mystack[-1]
                mystack << i
            return final

Let me know what you think!
twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)