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 - NGL - Nearest Greater Element to Left of every element

Method 1 - Brute Force

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[] NSL(int[] arr) {
	int n = arr.length;
	int[] left = new int[n];

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

	return left;
}