DAY 106 - Next Greater Element I

#learning #cpp #beginners #algorithms

Question: Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1is a subset of nums2.

For each 0 <= i < nums1.length, find the index jsuch that nums1[i] == nums2[j] and determine the next greater element of nums2[j]in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:

4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.

2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Problem Breakdown:

Before we dive into the code, let's break down the problem and understand what's expected:

We have two arrays, nums1 and nums2, of non-negative integers.
Each element in nums1 is present in nums2.
For each element in nums1, we need to find the next greater element in nums2.
If there is no greater element in nums2, we should return -1 for that element in the result array.

Approach:

To solve this problem efficiently, we can use a stack and a hash map. Here's the step-by-step approach:

We initialize an empty stack s and an empty unorderd_map mp.
We traverse through nums2, which serves as our parent array to find the next greater elements.
In each iteration, we compare the current element, it, with the top element of the stack (s.top()). If it is greater, we update the hash map mp with the mapping of the top element of the stack to it. We also pop the top element from the stack because we have found the next greater element for it.
After processing nums2, we have a complete mapping of each element to its next greater element in mp.
We initialize the result vector res with the same size as nums1, filled with -1.
We iterate through nums1 and check if the element exists in mp. If it does, we update the corresponding position in res with the next greater element found in mp.
Finally, we return the res vector, which contains the next greater elements for each element in nums1.

Code:


vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> mp;
        stack<int> s;
        for(auto it : nums2){
            while(!s.empty() && s.top() < it){
                mp[s.top()] = it;
                s.pop();
            }
            s.push(it);
        }
        vector<int> res(nums1.size(),-1);

        for(int i = 0; i < nums1.size(); ++i){
            if(mp[nums1[i]]){
                res[i] = mp[nums1[i]];
            }
        }
        return res;
    }

Time and Space Complexity:

Let's analyze the time and space complexity of our solution:

Time Complexity: The solution processes both nums1 and nums2 exactly once, so the time complexity is O(N1 + N2), where N1 is the length of nums1, and N2 is the length of nums2.
Space Complexity: We use a stack and a hash map to store intermediate results. The space complexity is O(N2) in the worst case, where N2 is the length of nums2.

DEV Community