496.next-greater-element-i.md

496. Next Greater Element I

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

• We can use monotonic stack (decreasing) to track the next greater element, for example, [3, 2, 1, 6, 5] we will push 3, 2, 1 but pop 3, 2, 1 when encountering 6, means that the next greater element for 3, 2, 1 is 6.
• We use hash table to track the item and its next greater element.

Monotonic Stack

fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
    // Store the value and its next greater element
    val hashTable = hashMapOf<Int, Int>()
    val stack = Stack<Int>()
    for (i in 0 until nums2.size) {
        val value = nums2[i]
        while (!stack.isEmpty() && stack.peek() < value) {
            hashTable[stack.pop()] = value
        }
        stack.push(value)
    }
    val results = IntArray(nums1.size)
    for (i in 0 until nums1.size) {
        results[i] = hashTable[nums1[i]] ?: -1
    }
    return results
}

• Time Complexity: O(m + n) for m, n is the size of two arrays.
• Space Complexity: O(m + n), O(n) for stack and hash table, O(m) for results.