CLEAN CODE: NEAREST SMALLER ELEMENT | STACK | PATTERN QUESTIONS

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.

Example:

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

Example 2:

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

InterviewBit

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

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
else:
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]
mystack.pop
end

if mystack.empty?
final << -1
else
final << mystack[-1]
end

mystack << i
end

return final

end```