Find the previous smaller element for each array element
Given an integer array, find the previous smaller element for every array element. The previous smaller element of a number x is the first smaller number to the left of x in the array.
In other words, for each element A[i] in the array A, find an element A[j] such that j < i and A[j] < A[i] and value of j should be as maximum as possible. If the previous smaller element doesn't in the array for any element, consider it -1.
For example,
Output: [-1, 2, 2, 3, 7, -1, 1]
Input: [5, 7, 4, 9, 8, 10]
Output: [-1, 5, -1, 4, 4, 8]
Note that the first element always has a previous smaller element as -1.
1. Brute-Force Approach
The idea is to use two nested loops. The outer loop takes each array element from left to right. The inner loop runs from right to left and considers all elements to the "left" of the element picked by the outer loop. Terminate the inner loop as soon as the smaller element is found, which would be the previous smaller element for the element picked by the outer loop.
The time complexity of this approach is O(n2), where n is the size of the input. Following is the implementation in C, Java, and Python based on the above idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <stdio.h> // Find the previous smaller element for every element in an array void findPrevSmaller(int arr[], int n) { // do for each element for (int i = 0; i < n; i++) { // keep track of the previous smaller element for element `arr[i]` int prev = -1; // process elements on the left of the element `arr[i]` for (int j = i - 1; j >= 0; j--) { // break the inner loop at the first smaller element on the // left of the element `arr[i]` if (arr[j] < arr[i]) { prev = arr[j]; break; } } printf("%d ", prev); } } int main(void) { int arr[] = { 2, 5, 3, 7, 8, 1, 9 }; int n = sizeof(arr) / sizeof(arr[0]); findPrevSmaller(arr, n); return 0; } |
Output:
-1 2 2 3 7 -1 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Main { // Find the previous smaller element for every array element public static void findPrevSmaller(int[] arr) { // base case if (arr == null || arr.length == 0) { return; } // do for each element for (int i = 0; i < arr.length; i++) { // keep track of the previous smaller element for element `arr[i]` int prev = -1; // process elements on the left of the element `arr[i]` for (int j = i - 1; j >= 0; j--) { // break the inner loop at the first smaller element on the // left of the element `arr[i]` if (arr[j] < arr[i]) { prev = arr[j]; break; } } System.out.print(prev + " "); } } public static void main(String[] args) { int[] arr = { 2, 5, 3, 7, 8, 1, 9 }; findPrevSmaller(arr); } } |
Output:
-1 2 2 3 7 -1 1
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# Find the previous smaller element for every array element def findPrevSmaller(arr): # base case if not arr: return # do for each element for i in range(len(arr)): # keep track of the previous smaller element for element `arr[i]` prev = -1 # process elements on the left of the element `arr[i]` for j in reversed(range(0, i)): # break the inner loop at the first smaller element on the # left of the element `arr[i]` if arr[j] < arr[i]: prev = arr[j] break print(prev, end=' ') if __name__ == '__main__': arr = [2, 5, 3, 7, 8, 1, 9] findPrevSmaller(arr) |
Output:
-1 2 2 3 7 -1 1
2. Using Stack
We can reduce the time complexity to linear by using extra space. The idea is to use a stack, which is a LIFO (Last–In, First–Out) data structure suitable for this problem. Following is the C++, Java, and Python program that demonstrates the algorithm:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <stack> using namespace std; // Find the previous smaller element for every element in an array void findPrevSmaller(int arr[], int n) { // create an empty stack stack<int> s; // do for each element for (int i = 0; i < n; i++) { // loop till stack is empty while (!s.empty()) { // If the stack's top element is less than the current element, // it is the previous smaller element if (s.top() < arr[i]) { cout << s.top() << ' '; break; } // remove the stack's top element is less if it is greater or equal // to the current element else { s.pop(); } } // If the stack becomes empty, all elements to the left // of the current element are greater if (s.empty()) { cout << -1 << ' '; } // push current element into the stack s.push(arr[i]); } } int main() { int arr[] = { 2, 5, 3, 7, 8, 1, 9 }; int n = sizeof(arr) / sizeof(arr[0]); findPrevSmaller(arr, n); return 0; } |
Output:
-1 2 2 3 7 -1 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import java.util.Stack; class Main { // Find the previous smaller element for every array element public static void findPrevSmaller(int[] arr) { // base case if (arr == null || arr.length == 0) { return; } // create an empty stack Stack<Integer> s = new Stack<>(); // do for each element for (int i = 0; i < arr.length; i++) { // loop till stack is empty while (!s.empty()) { // If the stack's top element is less than the current element, // it is the previous smaller element if (s.peek() < arr[i]) { System.out.print(s.peek() + " "); break; } // remove the stack's top element is less if it is greater or equal // to the current element else { s.pop(); } } // If the stack becomes empty, all elements to the left // of the current element are greater if (s.empty()) { System.out.print(-1 + " "); } // push current element into the stack s.push(arr[i]); } } public static void main(String[] args) { int[] arr = { 2, 5, 3, 7, 8, 1, 9 }; findPrevSmaller(arr); } } |
Output:
-1 2 2 3 7 -1 1
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
from collections import deque # Find the previous smaller element for every element in a list def findPrevSmaller(arr): # base case if not arr: return # create an empty stack s = deque() # do for each element for i in range(len(arr)): # loop till stack is empty while s: # If the stack's top element is less than the current element, # it is the previous smaller element if s[-1] < arr[i]: print(s[-1], end=' ') break # remove the stack's top element is less if it is greater or equal # to the current element else: s.pop() # If the stack becomes empty, all elements to the left # of the current element are greater if not s: print(-1, end=' ') # push current element into the stack s.append(arr[i]) if __name__ == '__main__': arr = [2, 5, 3, 7, 8, 1, 9] findPrevSmaller(arr) |
Output:
-1 2 2 3 7 -1 1
The time complexity of the above solution is O(n) since every element is pushed and popped at most once to the stack. The additional space used by the program is O(n) for the stack.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)