DSA 450 Notes

Problem Statement

Given an array of integers, find the Next Greater Element (NGE) for every element. The NGE for an element x is the first greater element on its right side. If no greater element exists, output -1.

Example:

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

Explanation:
- 4 -> 5 (first greater element to the right)
- 5 -> 25
- 2 -> 25
- 25 -> -1 (no greater element)

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

Approach 1: Brute Force (Nested Loops)

Intuition

For each element, scan all elements to its right and find the first one that is greater. This is straightforward but inefficient.

Algorithm

For each element at index i
Scan from i+1 to end of array
Return the first element greater than arr[i]
If no such element found, return -1

java

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElementBruteForce(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {
                    result[i] = arr[j];
                    break;
                }
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 25};
        int[] result = nextGreaterElementBruteForce(arr);
        
        System.out.print("Next Greater Elements: ");
        for (int x : result) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n^2) - nested loops
Space Complexity: O(1) - excluding output array

Approach 2: Using Stack (Optimal)

Intuition

Use a stack to keep track of elements for which we haven't found the NGE yet. Traverse from right to left. For each element, pop elements from stack that are smaller (they can't be NGE for current element). The stack top (if exists) is the NGE.

Algorithm

Traverse the array from right to left
For each element:
- Pop elements smaller than or equal to current (they won't be NGE for anyone)
- If stack not empty, top is the NGE
- Push current element to stack
Use stack to maintain elements in decreasing order from bottom to top

java

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        // Traverse from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Pop elements smaller than or equal to current
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            
            // If stack is empty, no greater element exists
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            
            // Push current element
            stack.push(arr[i]);
        }
        
        return result;
    }
    
    // Alternative: Traverse left to right, store indices
    public static int[] nextGreaterElementAlt(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>(); // Stack stores indices
        
        for (int i = 0; i < n; i++) {
            // While stack not empty and current element is greater than stack top
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 25};
        int[] result = nextGreaterElement(arr);
        
        System.out.print("Next Greater Elements: ");
        for (int x : result) {
            System.out.print(x + " ");
        }
        System.out.println();
        
        int[] arr2 = {13, 7, 6, 12};
        result = nextGreaterElement(arr2);
        System.out.print("Next Greater Elements: ");
        for (int x : result) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n) - each element is pushed and popped at most once
Space Complexity: O(n) - stack can hold at most n elements

Variation: Next Greater Element in Circular Array

For a circular array, the next greater element can wrap around.

Key Takeaways

Stack maintains monotonic decreasing order from bottom to top
Elements are popped when a greater element is found (they can't be NGE for future elements)
Two approaches:
- Right to left: find answer immediately for current element
- Left to right: find answer for elements in stack when greater element comes
Circular array: traverse array twice using modulo
Similar problems: Next Smaller Element, Previous Greater Element, Stock Span
This is a fundamental pattern for many stack-based problems

Find the next Greater element

Problem Statement

Approach 1: Brute Force (Nested Loops)

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Stack (Optimal)

Intuition

Algorithm

Complexity Analysis

Variation: Next Greater Element in Circular Array

Key Takeaways