Next Greater Element I

Updated on 04 July, 2025
Next Greater Element I header image

Problem Statement

In the problem, we are provided with two distinct integer arrays, nums1 and nums2, where nums1 is a subset of nums2. The arrays are indexed starting from zero. For every element x in the nums1, we need to identify its position in nums2 and then find the first element in nums2 that is greater than this x and appears to its right. If no such greater element exists, the result for this element should be -1. The goal is to return an array where each element corresponds to the result of the above search for the respective element in nums1.

Examples

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.

Example 2

Input:

nums1 = [2,4], nums2 = [1,2,3,4]

Output:

[3,-1]

Explanation:

The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Approach and Intuition

  1. Mapping Indexes: Begin by creating a map (or dictionary) to store the position of each element of nums2. This helps in quickly locating any element of nums1 within nums2.

  2. Finding Next Greater Element:

    • Traverse each element x in nums1.
    • Use the previously constructed map to find the index j of x in nums2.
    • Starting from the next index to j in nums2, look for the first element that is greater than x.
  3. Handling None Case:

    • If we reach the end of the list nums2 without finding a greater element, record -1 as the result for that particular element of nums1.

Example Explanation from the Provided Scenarios: * In the first example, for 4 we look to its right in nums2 but find no greater values hence -1 is recorded.

By using a map to track the indices, we significantly reduce the need for repetitive searches within nums2, thereby optimizing our approach. This is crucial given the constraints with lengths up to 1000. This mapping strategy followed by a simple scan for the greater element caters effectively to the problem requirements.

Solutions

  • C++
cpp
class Solution {
public:
    vector<int> findNextGreater(vector<int>& first, vector<int>& second) {
        stack<int> elements;
        unordered_map<int, int> result_map;
    
        for (int value : second) {
            while (!elements.empty() && value > elements.top()) {
                result_map[elements.top()] = value;
                elements.pop();
            }
            elements.push(value);
        }
    
        while (!elements.empty()) {
            result_map[elements.top()] = -1;
            elements.pop();
        }
    
        vector<int> result;
        for (int value : first) {
            result.push_back(result_map[value]);
        }
    
        return result;
    }
};

The provided C++ solution finds the "Next Greater Element I" using a stack and hash mapping technique. Here’s a breakdown of the implementation:

  • Initialize a stack to keep elements from the second list and an unordered map to store mappings of the next greater element.
  • Traverse each element in the second list:
    • If the stack is not empty and the current element is greater than the element on top of the stack, map the top element of the stack to the current element in the result map and then pop from the stack.
    • Push the current element onto the stack.
  • After processing all elements of the second list, pop remaining elements from the stack, assigning them a next greater value of -1 in the result map, as they do not have a greater element to their right.
  • Create a vector to store the results for elements in the first list, utilizing the previously built map to fill this vector with their corresponding next greater elements.

Finally, return this result vector, facilitating a straightforward access to the next greater elements for the queried indices of the first list. This method ensures efficient computation of results, leveraging stack operations and hashmap for quick lookup.

  • Java
java
public class Solution {
    
    public int[] findNextGreaterElements(int[] firstArray, int[] secondArray) {
        Stack<Integer> processingStack = new Stack<>();
        HashMap<Integer, Integer> resultMap = new HashMap<>();
    
        for (int index = 0; index < secondArray.length; index++) {
            while (!processingStack.isEmpty() && secondArray[index] > processingStack.peek()) resultMap.put(
                processingStack.pop(),
                secondArray[index]
            );
            processingStack.push(secondArray[index]);
        }
    
        while (!processingStack.isEmpty()) resultMap.put(processingStack.pop(), -1);
    
        int[] result = new int[firstArray.length];
        for (int i = 0; i < firstArray.length; i++) {
            result[i] = resultMap.get(firstArray[i]);
        }
    
        return result;
    }
}

The Java program provided defines a class Solution with a method findNextGreaterElements intended to find the next greater element for each element in the first array (firstArray) based on elements in the second array (secondArray). The method employs a stack and hashmap to efficiently map each element in secondArray to its next greater element, if it exists; otherwise, it maps to -1.

Follow these steps to understand the resolution approach:

  1. Initialize a Stack<Integer> called processingStack and a HashMap<Integer, Integer> called resultMap to keep track of each element and its next greater element.
  2. Traverse each element in secondArray using an index-based loop. For each element:
    • While the stack is not empty and the current element is greater than the element at the top of the stack:
      • Pop the stack and map this value in resultMap to the current secondArray element.
    • Push the current element onto the stack.
  3. After iterating through secondArray, pop any remaining elements from the stack and map them to -1 in resultMap, indicating no greater element exists.
  4. Initialize an array result to store the results for the firstArray.
  5. For each element in firstArray, retrieve its corresponding next greater element from resultMap, and store this in the result array.
  6. Return the result array.

This solution efficiently determines and maps the next greater elements by leveraging a stack to keep track of the processed elements and a hashmap for quick look-up capabilities.

  • Python
python
class Solution:
    def nextLargerElement(self, first_list, second_list):
        temp_stack = []
        dict_mapping = {}
    
        for element in second_list:
            while temp_stack and element > temp_stack[-1]:
                dict_mapping[temp_stack.pop()] = element
            temp_stack.append(element)
    
        while temp_stack:
            dict_mapping[temp_stack.pop()] = -1
    
        return [dict_mapping.get(item, -1) for item in first_list]

The Python solution for the "Next Greater Element I" problem uses a stack and dictionary to efficiently determine the next larger element for each number in the given first_list using numbers from second_list. Follow these steps to understand the implemented approach:

  1. Initialize an empty list temp_stack to hold elements temporarily and a dictionary dict_mapping to store the relationship between elements in second_list and their next greater element.

  2. Iterate through each element in second_list:

    • While temp_stack is not empty and the current element is greater than the last element in temp_stack, map the element popped from temp_stack to the current element in dict_mapping.
    • Push the current element onto temp_stack.
  3. After the loop, clear out any remaining elements in temp_stack:

    • Map each remaining element in temp_stack to -1 in dict_mapping, indicating no greater element exists for these items.
  4. Construct the result for first_list by iterating through its elements:

    • For each item in first_list, use dict_mapping to find the next greater element, defaulting to -1 if not found.

This solution ensures each element from both lists is processed efficiently, and the use of a stack helps in keeping track of elements for which a next larger element has yet to be determined.

Comments

No comments yet.