Java Coding Test Course, Finding the Next Greater Element

The problem of finding the next greater number (Next Greater Element) for a given array is one of the frequently asked algorithm problems in coding tests. In this article, we will define the next greater element problem, explain various approaches to solve it, and describe efficient algorithms. Additionally, we will provide a step-by-step explanation of how to implement it in Java, and we will discuss the time complexity and space complexity after the implementation.

Problem Definition

In a given integer array, the next greater element is defined as the first number that appears after an element that is greater than that element. If a next greater element does not exist, -1 should be placed for that element.

Problem Example

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

Problem Analysis

The traditional method to solve this problem is to use a nested loop. However, this method is inefficient with a time complexity of O(N^2). Therefore, a more efficient method needs to be found.

Efficient Approach: O(N) Solution Using Stack

To solve this problem, we can use the stack data structure. Below is the main idea of the algorithm for finding the next greater element using a stack:

Algorithm Explanation

1. Initialize the result array with the length of the given array.
2. Initialize the stack. The stack will store the indices of the array.
3. Traverse the array from left to right.
4. Check the value (index) at the top of the stack. If the current element is greater than the element at that index:
• The next greater element is the current element.
• Store that value in the result array.
• Pop that index from the stack.
5. Push the current index onto the stack.
6. Once all elements have been processed, the remaining indices in the stack do not have a next greater element, so set those to -1 in the result array.

Java Implementation

Now let’s implement the above algorithm in Java.

import java.util.Stack;

public class NextGreaterElement {
    public static int[] findNextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Stack stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        // Set -1 for the indices remaining in the stack, which do not have a next greater element
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3, 2, 5};
        int[] result = findNextGreaterElements(nums);
        
        System.out.print("Result: [");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

Time Complexity and Space Complexity

The algorithm implemented above has a time complexity of O(N). Each element is pushed and popped from the stack at most once. The space complexity is O(N) because the stack can be used up to N.

Conclusion

The problem of finding the next greater element can be efficiently solved using an algorithm that utilizes a stack. Since this problem is frequently included in coding tests, it is important to familiarize yourself with how to use stacks and solve these types of problems. Practice with various examples to enhance your problem-solving abilities.