algoadvance

Leetcode 496. Next Greater Element I

Problem Statement:

Given two arrays nums1 and nums2, where nums1 is a subset of nums2, return an array representing the Next Greater Element for each element in nums1 in the order of their appearance in nums1.

The Next Greater Element for an element x in nums1 is the first greater element on the right of x in nums2. If it does not exist, output -1 for that number.

Example:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]

Clarifying Questions:

1. Are the elements in nums1 and nums2 unique?
   • Yes, all elements are unique.
2. What is the maximum value for the lengths of nums1 and nums2?
   • The length of nums1 and nums2 will not exceed 1000.

Strategy:

1. Utilize a stack to track the Next Greater Element.
2. Traverse nums2 from right to left. Maintain a stack that stores elements in decreasing order.
3. For each element in nums2:
   • While the stack is not empty and the top of the stack is less than or equal to the current element, pop from the stack.
   • If the stack is empty, it means there’s no greater element to the right, so store -1.
   • Otherwise, the top of the stack is the next greater element, so store it.
4. Store the results in a hash map to quickly lookup results for elements in nums1.
5. Iterate through nums1 and use the hash map to build the result array.

Code:

Here is the implementation in C++:

#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> ngeMap;
    stack<int> s;
    
    // Traverse nums2 from right to left
    for (int i = nums2.size() - 1; i >= 0; --i) {
        int num = nums2[i];
        // Maintain a decreasing stack
        while (!s.empty() && s.top() <= num) {
            s.pop();
        }
        // If stack is empty, no next greater element
        if (s.empty()) {
            ngeMap[num] = -1;
        } else {
            // Top of stack is the next greater element
            ngeMap[num] = s.top();
        }
        // Push the current num onto the stack
        s.push(num);
    }
    
    // Prepare the result for nums1 based on the hashmap
    vector<int> result;
    for (int num : nums1) {
        result.push_back(ngeMap[num]);
    }
    
    return result;
}

Time Complexity:

• Building the map: O(n) where n is the length of nums2 because each element is pushed and popped from the stack at most once.
• Generating the result: O(m) where m is the length of nums1 by simply looking up in the hash map.

Thus, the overall time complexity is O(n + m).

Space Complexity:

• The space complexity is O(n) for the hash map and stack used to store elements of nums2. Here, n is the length of nums2.

The suggested approach efficiently handles the problem by combining the stack data structure for next greater element calculation and hash map for quick lookups.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?