Find the nearest smaller numbers on left side in an array - GeeksforGeeks
Stack is used to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed.
O(N^2)
Read full article from Find the nearest smaller numbers on left side in an array - GeeksforGeeks
Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.
Examples:
Input: arr[] = {1, 6, 4, 10, 2, 5}
Output: {_, 1, 1, 4, 1, 2}
First element ('1') has no element on left side. For 6,
there is only one smaller element on left side '1'.
For 10, there are three smaller elements on left side (1,
6 and 4), nearest among the three elements is 4.
Stack is used to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed.
void printPrevSmaller(int arr[], int n){ // Create an empty stack stack<int> S; // Traverse all array elements for (int i=0; i<n; i++) { // Keep removing top element from S while the top // element is greater than or equal to arr[i] while (!S.empty() && S.top() >= arr[i]) S.pop(); // If all elements in S were greater than arr[i] if (S.empty()) cout << "_, "; else //Else print the nearest smaller element cout << S.top() << ", "; // Push this element S.push(arr[i]); }}void printPrevSmaller(int arr[], int n){ // Always print empty or '_' for first element cout << "_, "; // Start from second element for (int i=1; i<n; i++) { // look for smaller element on left of 'i' int j; for (j=i-1; j>=0; j--) { if (arr[j] < arr[i]) { cout << arr[j] << ", "; break; } } // If there is no smaller element on left of 'i' if (j == -1) cout << "_, " ; }}