Finding Next Greater Element in Python

In this problem, we will be given an array of integers, and we have to find the Next Greater Element for every element of each element of the array.

The Next Greater Element is the first element on the right-hand side of the current element that is greater than the current element. For the elements of the array for which no greater element exists, we will return -1 for those elements.

Let us see some examples to understand the problem.

Input: array = [ 7, 3, 9, 12, 8 ]

Output:

7 -> 9

3 -> 9

9 -> 12

12 -> -1

8 -> -1

The first element that is greater than 7 and is present on the right side of it is 9. Likewise, for every element except for 8 and 12, there exists a greater element on the right side of the element

Input: arr = [ 19, 10, 7, 5, 13 ]

Output:

19 -> -1

10 -> 13

7 -> 13

5 -> 13

13 -> -1

Except for 19, other elements have 13 as their greater counterparts.

Approach - 1

In this approach, we will use two for loops to iterate over the array. The outer loop will iterate over every element of the array. The inner loop will be responsible for finding the greater element for the current element. This loop will run over the rest of the loop on the right-hand side of the current element. If there is no greater element, we will print -1 for that element.

We will follow the following steps to solve this problem:

• We will initiate the outer loop from index 0 to the last element, i.e., len(array) - 1.
  • For every ith element of the outer loop, another loop will run from i + 1 to the last index of the array.
  • If we find an element greater than the ith element of the array, we will break the loop; otherwise, we will print -1.

Below is the Python code for the approach mentioned above.

Code

Output:

7 - 9 3 - 9 9 - 12 12 - -1 8 - -1 

Time Complexity: Since we are using two loops in this approach, the time complexity of this approach is O(N2)

Space Complexity: Since we are not creating any extra data structure, the space complexity of this approach is O(1).

Approach - 2

In this approach, we will use the stack data structure.

In this approach, we will use the stack to store the elements for which we have to find the next greater element. When traversing the array, we will pair a greater element with the elements of the stack. We will continue the process until the stack's top element has a lesser value than the current element.

We will follow the following steps to solve the problem using the approach mentioned above:

• We will start by pushing the first element of the array to the stack.
• Now we will iterate over the array and push the rest of the elements to the stack. Also, we follow these steps:
  • We will mark the current element as the greater element.
  • If the stack is non-empty for the current iteration, we will compare the top element of the stack with the greater element.
  • If the top element of the stack is smaller than the greater element, we will pop the top element from the stack. Therefore, the greater the NGE of all the popped elements of the stack.
  • When we encounter an element that is greater than the top element of the stack, we will push the greater element in the stack.
• Once the loop is complete, we will pop all stack elements and return -1 as the NGE.

Below is the Python code for the approach mentioned above.

Code

Output:

3 - 9 7 - 9 9 - 12 8 - -1 12 - -1 

Time Complexity: Since we are running a linear loop, the time complexity of this approach is O(N).

Space Complexity: We have used an extra space to store the elements, i.e., the stack; hence the space complexity is O(N).

Approach - 3

In this new approach, we will use a map to find the NGE of the elements of the array.

The approach is similar to the one we saw earlier. The difference in this method is that we will push and pop the elements from the stack only once. Also, the array will be changed in place. We will push the elements of the array in the stack until we find an element greater than the top element of the stack. Hence, we will pop the top element from the stack when we find an element smaller than the current array element.

When all the array elements are visited, and the stack is still not empty, the rest of the stack elements do not have any NGE in the array. Hence, we will pop those elements from the stack and change the value at their index to -1 in the original array.

Code

Output:

[9, 9, 12, -1, -1] 

Time Complexity: We are using a linear loop. Hence the time complexity is O(N).

Space Complexity: The space complexity of this approach is O(N). We have used this space to store the stack and map.

Approach - 4

There is a better and more optimized approach to solving this problem. Let us now see that approach.

Below are the steps to solve the problem using the optimized approach.

• We will start by initializing an array, res, of size n, where n is the length of the given array, that will contain the resultant NGEs. We will add -1 to the array as the initial NGE of every element.
• We will initialize another variable to store the maximum element encountered until now. This variable will be max_so_far. The initial value of this variable will be the element at index -1 of the given array.
• Now we will initiate a loop traversing the array from left to right.
  • For every ith element of the array, if the subsequent element, i.e., (i + 1)th element, is greater than the ith element of the array, then we will set res[i] = res[i +1]. The reason is that the (i + 1)th element is the next greater element of the ith element.
  • However, suppose the (i + 1)th element of the given array is smaller than the ith element of the same array. In that case, we will check if the (i +1)th element of the array res is smaller or greater than the ith element of the given array. If res[i +1] > array[i], then we will set the ith element of res equal to the (i + 1)th element of res.
  • If the (i + 1)th element of res is smaller than the ith element of the given array, then we will check the maximum element seen till now, i.e., max_so_far. If this value is greater than the ith element, then we will start another loop to traverse the subarray that is on the right side of the ith element. The loop will continue until we find an element greater than the array's ith element. If we find such an element, we will set res[i] equal that element.
  • Else, if max_so_far < array[i], then we will leave res[i] as -1 only.
  • We must keep updating the max_so_far as the maximum element of the array until the ith element.
• The final answer will be the array res.

Code

Output:

[9, 9, 12, -1, -1] 

Time complexity: Since we traverse the element only once, the time complexity is O(N). This is the average time complexity; however, the worst time complexity can be O(N2) because we have a nested loop for some specific conditions.

Space Complexity: Since we are not using any extra space to store the elements, the space complexity is constant, hence, O(1).