Next greater element I, II, III

XXX. Next Greater Element I, II, III

Stack

Monotonic Stack

Problem Statement:

This collection of problems revolves around finding the next greater element for elements in an array or number:

• Next Greater Element I: Find the next greater element for each number in a subset array findNums from a larger array nums.
• Next Greater Element II: The array is circular. Find the next greater element for each number considering the array wraps around.
• Next Greater Element III: Given a number, find the smallest integer that is greater than it using its digits. Return -1 if no such number exists.

Approach:

1. **Next Greater Element I**: Use a monotonic stack to precompute the next greater elements in nums and store them in a map for quick lookup.
2. **Next Greater Element II**: Extend the stack-based approach to handle circular arrays by iterating through the array twice.
3. **Next Greater Element III**: Use a greedy approach with swapping and reversing to find the next permutation of the given number's digits.

Java Implementation:

// Next Greater Element I
public int[] nextGreaterElement(int[] findNums, int[] nums) {
    Map map = new HashMap<>(); // Map to store next greater elements
    Stack stack = new Stack<>();
    for (int num : nums) {
        while (!stack.isEmpty() && stack.peek() < num)
            map.put(stack.pop(), num);
        stack.push(num);
    }   
    for (int i = 0; i < findNums.length; i++)
        findNums[i] = map.getOrDefault(findNums[i], -1);
    return findNums;
}

// Next Greater Element II
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length, next[] = new int[n];
    Arrays.fill(next, -1);
    Stack stack = new Stack<>(); // Stack to store indices
    for (int i = 0; i < n * 2; i++) { // Iterate twice for circular array
        int num = nums[i % n]; 
        while (!stack.isEmpty() && nums[stack.peek()] < num)
            next[stack.pop()] = num;
        if (i < n) stack.push(i);
    }   
    return next;
}

// Next Greater Element III
public int nextGreaterElement(int n) {
    char[] a = ("" + n).toCharArray();
    int i = a.length - 2;
    while (i >= 0 && a[i + 1] <= a[i]) i--; // Find the first decreasing element
    if (i < 0) return -1;
    int j = a.length - 1;
    while (j >= 0 && a[j] <= a[i]) j--; // Find the next larger element
    swap(a, i, j);
    reverse(a, i + 1);
    try {
        return Integer.parseInt(new String(a));
    } catch (Exception e) {
        return -1; // Handle overflow
    }
}
private void reverse(char[] a, int start) {
    int i = start, j = a.length - 1;
    while (i < j) swap(a, i++, j--);
}
private void swap(char[] a, int i, int j) {
    char temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
        

Python Implementation:

# Next Greater Element I
def nextGreaterElement(findNums, nums):
    stack, map = [], {}
    for num in nums:
        while stack and stack[-1] < num:
            map[stack.pop()] = num
        stack.append(num)
    return [map.get(x, -1) for x in findNums]

# Next Greater Element II
def nextGreaterElements(nums):
    n = len(nums)
    next = [-1] * n
    stack = []
    for i in range(2 * n):
        num = nums[i % n]
        while stack and nums[stack[-1]] < num:
            next[stack.pop()] = num
        if i < n:
            stack.append(i)
    return next

# Next Greater Element III
def nextGreaterElement(n):
    a = list(str(n))
    i = len(a) - 2
    while i >= 0 and a[i + 1] <= a[i]:
        i -= 1
    if i < 0:
        return -1
    j = len(a) - 1
    while j >= 0 and a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
    a = a[:i + 1] + a[i + 1:][::-1]
    res = int(''.join(a))
    return res if res <= 2**31 - 1 else -1
        

C++ Implementation:

// Next Greater Element I
vector nextGreaterElement(vector& findNums, vector& nums) {
    unordered_map map;
    stack s;
    for (int num : nums) {
        while (!s.empty() && s.top() < num) {
            map[s.top()] = num;
            s.pop();
        }
        s.push(num);
    }
    vector res;
    for (int num : findNums)
        res.push_back(map.count(num) ? map[num] : -1);
    return res;
}

// Next Greater Element II
vector nextGreaterElements(vector& nums) {
    int n = nums.size();
    vector next(n, -1);
    stack s;
    for (int i = 0; i < 2 * n; i++) {
        int num = nums[i % n];
        while (!s.empty() && nums[s.top()] < num) {
            next[s.top()] = num;
            s.pop();
        }
        if (i < n) s.push(i);
    }
    return next;
}

// Next Greater Element III
int nextGreaterElement(int n) {
    string a = to_string(n);
    int i = a.size() - 2;
    while (i >= 0 && a[i + 1] <= a[i]) i--;
    if (i < 0) return -1;
    int j = a.size() - 1;
    while (j >= 0 && a[j] <= a[i]) j--;
    swap(a[i], a[j]);
    reverse(a.begin() + i + 1, a.end());
    long res = stol(a);
    return res > INT_MAX ? -1 : res;
}