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, 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.
Input: arr[] = {1, 3, 0, 2, 5}
Output: {-1,1,-1, 0, 2}
Expected time complexity is O(n).
As we need to keep minimum value for each element on left side.
We can think like :
1. Left to right iterate,
2. Keep minimum value at each step.
3. Idea is to use Stack ( Refer similar question : Find Minimum Number from Input Elements in O(1) {remember using stack we were achieving this}
The idea is to use a stack. 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.
Below is stack based algorithm
Let input sequence be 'arr[]' and size of array be 'n'
1) Create a new empty stack S
2) For every element 'arr[i]' in the input sequence 'arr[]',
where 'i' goes from 0 to n-1.
a) while S is nonempty and the top element of
S is greater than or equal to 'arr[i]':
pop S
b) if S is empty:
'arr[i]' has no preceding smaller value
c) else:
the nearest smaller value to 'arr[i]' is
the top element of S
d) push 'arr[i]' onto S
We can think to code it like below from above discussed algorithm and steps for finding nearest minimum number left side in array.
#include
#include
using namespace std;
void printLeftSmaller(int arr[], int n)
{
stack S;
for (int i=0; i<n; i++) { while (!S.empty() && S.top() >= arr[i])
S.pop();
if (S.empty())
cout << "-1, ";
else
//Else print the nearest smaller element
cout << S.top() << ", ";
S.push(arr[i]);
}
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {1, 3, 0, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
printLeftSmaller(arr, n);
return 0;
}
To find Minimum number Left side of array , we can try above mentioned code.
Instead Array , similar approach we can think for Linked Lists as well.
Time Complexity : O(n)
Space Complexity : O(n)
To contribute to Gohired.in please mail to admin@gohired.in, w’ll represent your approach/ solution with your name to enhance your CV