JavaScript Coding Test Course, Finding the Next Greater Number

Hello! Today we will learn about one of the important topics in JavaScript coding tests, ‘Finding the Next Greater Element’. This problem involves finding the next greater number for each element in an array, requiring efficient algorithm design. In this article, we will cover the problem description, approach, and algorithm implementation in detail.

Problem Description

The problem is to find the first number that appears to the right of each element in the given array that is larger than that element. If there is no such number, return -1.

Examples

  • Input: [2, 3, 3, 5, 4, 9, 6]

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

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

    Output: [-1, -1, -1, -1, -1]

Approach to the Problem

There are two approaches to solving this problem. The first is using a simple nested loop, and the second is using a stack. The second method is more efficient in terms of time complexity.

1. Nested Loop Approach

This method involves checking all elements to the right of each element to find the next greater element. Although this method is easy to implement, it has a time complexity of O(N^2), making it inefficient.


function findNextGreaterElements(arr) {
    const result = [];
    const n = arr.length;
    
    for (let i = 0; i < n; i++) {
        let found = false;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                result[i] = arr[j];
                found = true;
                break;
            }
        }
        if (!found) {
            result[i] = -1;
        }
    }
    return result;
}

// Example usage
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// Output: [3, 5, 5, 9, 9, -1, -1]

2. Stack Approach

This method uses a stack to solve the problem. Since this method processes each element using a stack, it has a time complexity of O(N) and a space complexity of O(N).

The algorithm is as follows:

  1. Initialize the stack.
  2. Iterate over each element.
  3. If the top element of the stack is smaller than the current element, pop it from the stack and set its next greater element to the current element.
  4. Push the index of the current element onto the stack.
  5. At the end of the iteration, set remaining elements in the stack to -1.

function findNextGreaterElements(arr) {
    const result = new Array(arr.length).fill(-1);
    const stack = [];
    
    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const index = stack.pop();
            result[index] = arr[i];
        }
        stack.push(i);
    }
    
    return result;
}

// Example usage
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// Output: [3, 5, 5, 9, 9, -1, -1]

Conclusion

The problem of finding the next greater element is a great way to develop algorithmic problem-solving skills by identifying larger numbers that appear later based on the elements of an array. It is important to understand and apply both the simple approach using loops and the efficient approach using stacks. I hope you continue to study more algorithms and data structures through such problems!

References

  • Data structures and algorithms: lectures and books
  • Online coding test platforms (e.g., LeetCode, HackerRank)
  • Official JavaScript documentation