Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Next Greater Element

Problem Statement

Examples

Solution:

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given an array, print the Next Greater Element (NGE) 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.

Elements for which no greater element exist, consider the next greater element as -1.

Examples

Example 1:

 Input: [4, 5, 2, 25]
 Output: [5, 25, 25, -1]
 Explanation: The NGE for 4 is 5, 5 is 25, 2 is 25, and there is no NGE for 25.

Example 1:

 Input: [13, 7, 6, 12]
 Output: [-1, 12, 12, -1]

Example 1:

 Input: [1, 2, 3, 4, 5]
 Output: [2, 3, 4, 5, -1]

Constraints:

  • 1 <= arr.length <= 10<sup>4</sup>
  • -10<sup>9</sup> <= arr[i] <= 10<sup>9</sup>

Solution:

A simple algorithm is to run two loops: the outer loop picks all elements one by one, and the inner loop looks for the first greater element for the element picked by the outer loop. However, this algorithm has a time complexity of O(n^2).

We can use a more optimized approach using Stack data structure. The algorithm will leverage the nature of the stack data structure, where the most recently added (pushed) elements are the first ones to be removed (popped). Starting from the end of the array, the algorithm always maintains elements in the stack that are larger than the current element. This way, it ensures that it has a candidate for the "next larger element". If there is no larger element, it assigns -1 to that position. It handles each element of the array only once, making it an efficient solution.

Detailed Step-by-Step Walkthrough

  1. The function receives an array arr.

  2. Initialize an empty stack s and an output array res of size equal to the input array, with all elements initialized to -1. res will store the result, i.e., the next larger element for each position in the array.

  3. Start a loop that goes from the last index of the array to the first (0 index).

  4. In each iteration, while there are elements in the stack and the top element of the stack is less than or equal to the current element in the array, remove elements from the stack. This step ensures that we retain only the elements in the stack that are larger than the current element.

  5. After the popping process, if there is still an element left in the stack, it is the next larger element for the current array element. So, assign the top element of the stack to the corresponding position in the res array.

  6. Now, push the current array element into the stack. This action considers the current element as a possible "next larger element" for the upcoming elements in the remaining iterations.

  7. Repeat steps 4-6 for all the elements of the array.

  8. At the end of the loop, res will contain the next larger element for each position in the array. Return this array res.

Algorithm Walkthrough

Let's consider the input and observe how above algorithm works.

  1. Initialize Data Structures:

    • Input Array: [13, 7, 6, 12]
    • Result Array: [0, 0, 0, 0] (Initially set to zeros)
    • Stack: Empty (Will store elements during iteration)

  2. Processing Each Element (Reverse Order):

    • The algorithm processes the array from right to left.

  3. Last Element (Value 12):

    • Stack is empty, indicating no greater element for 12.
    • Result Array: [0, 0, 0, -1] (Updates the last position to -1)
    • Push element 12 onto the stack.

  4. Third Element (Value 6):

    • Stack's top element is 12, which is greater than 6.
    • Result Array: [0, 0, 12, -1] (Updates the value at the third position to 12)
    • Push element 6 onto the stack.

  5. Second Element (Value 7):

    • Stack's top element is 6, which is less than 7, so it's popped.
    • Next, the stack's top element is 12, which is greater than 7.
    • Result Array: [0, 12, 12, -1] (Updates the value at the second position to 12)
    • Push element 7 onto the stack.

  6. First Element (Value 13):

    • Stack's top element is 7, which is less than 13, so it's popped.
    • Next, stack's top element is 12, which is also less than 13, so it's popped.
    • Stack is now empty, indicating no greater element for 13.
    • Result Array: [-1, 12, 12, -1] (Updates the first position to -1)
    • Push element 13 onto the stack.

Here is the visual representation of the algorithm:

mediaLink

1 of 6

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass (reverse iteration): The algorithm iterates through the input list arr in reverse order. Since each element is processed exactly once, this takes O(N) time, where N is the number of elements in the list.

  • Stack operations: For each element in the list, the algorithm performs push and pop operations on the stack. Each element is pushed onto the stack once, and it is popped from the stack at most once. Therefore, the total time complexity for stack operations is also O(N).

Overall time complexity: O(N).

Space Complexity

  • Stack space: The stack stores elements from the input list. In the worst case, if the input list is strictly decreasing, all elements will be pushed onto the stack, requiring O(N) space.

  • Result list: The result list stores the Next Greater Element (NGE) for each element in the input list, so it requires O(N) space.

Overall space complexity: O(N).

S

SK

· 3 years ago

Problem:


public List<Integer> nextLargerElement(List<Integer> arr) {}

Solution:


int[] printNGE(int arr[]) {}
P

Priyanka B

· 3 years ago

I tried to solve this problem by iterating from the beginning, but couldn't solve it. How do we know that we will need to start looking from the last index instead of starting from the beginning?

Show 3 replies
U

US

· 2 years ago

I have a question regarding time complexity. Does using while loop not considered a nested iteration of the given input?

If yes then the time-complexity should be O(n^2).

Show 1 reply
ASHWIN SHIRVA

ASHWIN SHIRVA

· 2 years ago

I think the stack solution has a time complexity of O(n^2) in the worst case.

Consider this input: [4, 1, 2, 3, 5]

If we start from the end of the array, by the time we reach 0th index, the stack would have the following elements:

1

2

3

5

So as we compare the current element 4 with the top element in stack we would end up popping all 1, 2, 3. We have to pop till 5 to get next greater element to 4. So, our inner loop ends up running 4 times (for elements 1, 2, 3, 5 in stack) for our array arr of size 5 in this case. Therefore I believe the worst case time complexity must be O(n^2).

Show 1 reply
Pavel Kostenko

Pavel Kostenko

· 2 years ago

Time Complexity

  • Reversing the result list: The result list is reversed at the end to maintain the original order of the elements. This operation takes  time.

We're not reversing anything here. So this bullet point can be removed I guess?

class Solution {
    nextLargerElement(arr) {
        let stack = []; // Initialize an empty stack to store indices of elements
        let res = new Array(arr.length).fill(-1); // Initialize a result array with -1 values

        // Iterate through the input array from right to left
        for (let i = arr.length - 1; i >= 0; i--) {
            while (stack.length && stack[stack.length - 1] <= arr[i]) {
                // While the stack is not empty and the element at the top of the stack
                // is less than
Show 1 reply
G

gabbygabbylexy

· a year ago

I find this implementation easier to understand

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> nextLargerElement(List<int> arr) {
        List<int> res = new List<int>();
        // ToDo: Write Your Code Here.
        var stack = new Stack<int>();
        var i = arr.Count - 1;

        while (i > -1) {
            if (stack.Count > 0 && stack.Peek() <= arr[i]) {
                stack.Pop();
                continue;
            }

            res.Insert(0, stack.Count > 0 ? stack.Peek() : -1);
            stack.Push(arr[i]);
            --i;
        }

        return res;
    }
}
Nghĩa Huỳnh Trung

Nghĩa Huỳnh Trung

· a year ago

func (this *Solution) nextLargerElement(arr []int) []int {
  res := make([]int, len(arr))
  stack := make([]int, 0)

  for i := len(arr) - 1; i >= 0; i-- {
    length := len(stack)
    for length > 0 {
      if arr[i] < stack[length-1] {
        res[i] = stack[length-1]
        stack = append(stack, arr[i])
        break
      }
      length--
    }

    if length == 0 {
      res[i] = -1
      stack = append(stack, arr[i])
      continue
    }
  }

  return res
}
E

Ejike Nwude

· 9 months ago

public class Solution {

    public List<Integer> nextLargerElement(List<Integer> arr) {
        int size = arr.size();
        List<Integer> res = new ArrayList<>(Collections.nCopies(size, -1));
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && arr.get(i) > arr.get(stack.peek())) {
                int index = stack.pop();
                res.set(index, arr.get(i));
            }
            stack.push(i);
        }
        return res;
    }
}
Faraz Ahmed

Faraz Ahmed

· 8 months ago

next greater element will be the value after the x, this is conflicting because only when input is sorted the next greater element will lie after the x or right side of the x?

On This Page

Problem Statement

Examples

Solution:

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity