Immediate Smaller Element

Easy
0/40
Average time to solve is 15m
41 upvotes
Asked in company
Visa

Problem statement

You are given an integer array 'a' of size 'n'.


For each element in the array, check whether the immediate right element of the array is smaller or not.


If the next element is smaller, update the current index to that element. If not, then -1. The last element does not have any elements on its right.


Example : 
Input: 'a' = [4, 7, 8, 2, 3, 1]

Output: Modified array 'a' = [-1, -1, 2, -1, 1, -1]

Explanation: In the array 'a':
4 has 7 on its right. Since 7 is not smaller, we update 4 to -1.

7 has 8 on its right. Since 8 is not smaller, we update 7 to -1.

8 has 2 on its right. Since 2 is smaller than 8, we update 8 to 2.

2 has 3 on its right. Since 3 is not smaller, we update 2 to -1.

3 has 1 on its right. Since 1 is smaller than 3, we update 3 to 1.

1 does not have any element on right. So we update 1 to -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer 'n' denoting the size of the array.
The second line contains 'n' space-separated integers denoting the array elements at various indices.


Output format : 
The output contains 'n' integers in a single line, the modified array 'a'.


Note : 
You don’t have to print anything; it has already been taken care of. Just implement the given function and make the changes in the given array 'a'.
Sample Input 1 :
6
4 7 8 2 3 1


Sample Output 1 :
-1 -1 2 -1 1 -1


Explanation of The Sample Input 1 :
In the array 'a':
4 has 7 on its right. Since 7 is not smaller, we update 4 to -1.
7 has 8 on its right. Since 8 is not smaller, we update 7 to -1.
8 has 2 on its right. Since 2 is smaller than 8, we update 8 to 2.
2 has 3 on its right. Since 3 is not smaller, we update 2 to -1.
3 has 1 on its right. Since 1 is smaller than 3, we update 3 to 1.
1 does not have any element on right. So we update 1 to -1.


Sample Input 2 :
4
1 2 3 4


Sample Output 2 :
-1 -1 -1 -1


Sample Input 3 :
4
4 3 2 1


Sample Output 3 :
3 2 1 -1


Expected time complexity :
The expected time complexity is O(n).


Constraints :
1 <= 'n' <= 10 ^ 5
1 <= 'a[i]' <= 10 ^ 9

Time Limit : 1 sec
Hint

Try and think of how you can check for each element, whether its previous element is greater or lesser than current.

Approaches (2)
Using stack

The idea is to traverse the array and store the just previous element of the current element in a data structure, say Stack, and then compare its top with the next element

  • Initialize the stack ‘s’ to store the previous element that is a[i - 1] for a[i].
  • Push the first element of a to s.
  • Now run a loop from index i = 1  till the end of the array and check for each element if(s.peek() > a[i]).
  • If the conditions satisfy, update a[i - 1] as a[i].
  • Else put a[i - 1] = -1
  • Now push the current element for the next iteration.
  • Finally, in the update a[n - 1] = -1 because there are no further elements to check.
Time Complexity

O(n), Where ‘n’ denotes the number of elements in the array

We are traversing the array once to find the final array that takes O(n) time. Hence, the overall Time Complexity is O(n).

Space Complexity

O(n), Where ‘n’ denotes the number of elements in the array.

The Space Complexity O(n) is required for Stack to store elements.  Hence, the overall Space Complexity is O(n).

Code Solution
(100% EXP penalty)
Immediate Smaller Element
Full screen
Console