Immediate Smaller Element Problem:
Given an integer array
arr
of size $n$. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, update the current index to that element. If not, then update it to –1.
Input: arr[] = {4, 2, 1, 5, 3}
Output: arr[] = {2, 1, -1, 3, -1}
Explanation: Next to 4 is 2 which is smaller, so we replace 4 with 2. Next of 2 is 1 which is smaller, so we replace 2 with 1. Next of 1 is 5 which is greater, so replace 1 with -1. Next of 5 is 3 which is smaller, so replace 5 with 3. The output for the last element is always going to be -1 because there is no element on right.
This is my solution:
void immediateSmaller(int arr[], int n) {
int i = 0, j = i + 1;
while(i < n - 1) {
if(arr[i] > arr[j])
arr[i] = arr[j];
else
arr[i] = -1;
i++;
j++;
}
arr[j - 1] = -1;
}
My queries are:
- Is the time complexity of my solution $O(n)$ or $O(n^2)$? I think it should be $O(n)$ since there is only one loop here.
- How can this question be implemented using a
Stack
data structure? (My solution works fine but recommended approach is to use aStack
)