Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Problem 4: Next Greater Element (easy)

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]

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>

.....

.....

.....

Like the course? Get enrolled and start learning!
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