Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Next Greater Element

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]

.....

.....

.....

Like the course? Get enrolled and start learning!
S

SK

· 3 years ago

Problem:


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

Solution:


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

Priyanka B

· 2 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

· 8 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

· 7 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?