Problem

Given an array, print the Next Smaller Element (NSR) for every element. The Next greater element for an element x is the first greater element on the right side of x in the array.

The elements for which no greater element exist, print -1.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input:  {1, 3, 2, 4} 
Output: {-1, 1, 1, 1}

Element     Next greater element on the right
1           -1
3           1
2           1
4           1

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:  {6, 4, 12, 5, 2, 10} 
Output: {-1, -1, 4, 4, -1, 2} 

Element     Next greater element on the right
6           -1
4           -1
12          4
5           4
2           -1
10          2

Solution

We have already seen - NGR - Nearest Greater Element to Right of every element.

Method 1 - Brute Force

The Brute force approach is to iterate over the array and for each element at index i,

  • Iterate from i+1 to n to find the next smaller element.

Time Complexity: O(n^2) | Space Complexity: O(1)

Method 2 - Using Monotonic Stack

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

private int[] NSR(int[] arr) {
	int n = arr.length;
	int[] right = new int[n];

	Stack<Integer> stack = new Stack<>();
	for (int i = arr.length - 1; i >= 0; i--) {
		if (stack.isEmpty()) {
			right[i] = n - 1;
		} else {
			while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
				stack.pop();
			}
			right[i] = stack.isEmpty() ? n - 1 : stack.peek() - 1;

		}
		stack.push(i);
	}
	return right;
}