Next Greater Element I

Easy

Swiggy

0 views

Topics:

ArraysStacks

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 nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such 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.

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] <= 10⁴
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Try coding it in LeetCode

Next Greater Element I

Easy

Swiggy

0 views

Topics:

ArraysStacks

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 nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such 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.

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] <= 10⁴
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integers within `nums1` and `nums2`? Can they be negative?
What should I return if there is no next greater element for a number in `nums1` within `nums2`? Should I return -1?
Are the elements within `nums1` guaranteed to be present in `nums2`?
Can `nums1` or `nums2` be empty or null? What should I return in those cases?
Are there duplicate numbers within `nums1` or `nums2`? If so, how should I handle them?

Brute Force Solution

Approach

We want to find the next bigger number for each number in a smaller set, compared to a larger set. The brute force method is all about looking at every single possibility to find the answer. We check each number in the smaller set against every number in the larger set until we find a bigger one.

Here's how the algorithm would work step-by-step:

Take the first number from the smaller set.
Now, look at each number in the larger set, one by one, starting from the beginning.
If you find a number in the larger set that is bigger than the current number from the smaller set, then that's the next bigger number!
Write down this next bigger number.
If you go through the entire larger set and don't find any number bigger than the number from the smaller set, then there is no next bigger number, so write down that there isn't one.
Move on to the next number in the smaller set and repeat the process from step 2 until you've checked all the numbers in the smaller set.

Code Implementation

def next_greater_element_i_brute_force(nums1, nums2):
    result = []

    for number_from_smaller_set in nums1:
        next_greater_number = -1

        for number_from_larger_set in nums2:
            # Finding the next greater number
            if number_from_larger_set > number_from_smaller_set:
                next_greater_number = number_from_larger_set
                break

        result.append(next_greater_number)

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each element of nums1, which has a size of m. For each element in nums1, it iterates through nums2, which has a size of n, to find the next greater element. Therefore, in the worst case, we might have to traverse all elements of nums2 for each element of nums1. This leads to a time complexity of m * n operations. Thus, the overall time complexity is O(m*n).

Space Complexity

O(1) – The described brute force approach iterates through the input arrays but does not use any auxiliary data structures that scale with the input size. It only uses a few variables to store indexes and temporary results, irrespective of the size of the input arrays nums1 and nums2. Thus, the auxiliary space complexity is constant.

Optimal Solution

Approach

The key idea is to use a temporary holding space to keep track of potentially greater numbers we've seen but haven't found a match for yet. This lets us quickly find the next greater number for each number we encounter without repeatedly searching.

Here's how the algorithm would work step-by-step:

First, create a way to remember the next larger number we find for each number in the second set of numbers.
Go through the second set of numbers one by one.
As we go, use a temporary storage to keep track of the numbers we've seen that might be smaller than something coming up later.
If we find a number bigger than something in our temporary storage, we know that's the 'next bigger number' for the smaller number.
Store this 'next bigger number' in our memory from step one.
After going through the second set, we know the next bigger number (if it exists) for each number in the second set.
Finally, use this knowledge to find the next bigger number for each number in the first set by simply looking it up in our memory.

Code Implementation

def next_greater_element(nums1, nums2):
    next_greater = {}
    temporary_storage = []

    # Iterate to find next greater elements
    for number in nums2:

        # Find next greater element for previous elements
        while temporary_storage and number > temporary_storage[-1]:
            next_greater[temporary_storage.pop()] = number

        temporary_storage.append(number)

    # Numbers left in stack have no greater element
    while temporary_storage:
        next_greater[temporary_storage.pop()] = -1

    result = []

    # Build results using next greater elements
    for number in nums1:
        result.append(next_greater[number])

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through nums2 once to build the next greater element map, which takes O(n) time, where n is the length of nums2. The stack operations within this loop (push and pop) take amortized O(1) time per element. Then, the algorithm iterates through nums1 once to find the next greater elements, which takes O(m) time, where m is the length of nums1. Since m <= n, the overall time complexity is dominated by the first loop, resulting in O(n) complexity.

Space Complexity

O(N) – The algorithm uses a hash map (or similar 'memory') to store the next greater element for each number in nums2, where N is the length of nums2. This hash map can potentially store all N elements of nums2. Additionally, a stack (or similar 'temporary storage') is used to keep track of numbers for which we haven't found the next greater element yet, which, in the worst case, could also contain all N elements of nums2. Therefore, the auxiliary space used is proportional to the size of nums2, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
nums1 or nums2 is null or empty	Return an empty array if either input array is null or empty.
nums1 is larger than nums2	The algorithm must still function correctly by only searching through nums2 to find next greater elements for nums1.
nums1 and nums2 contain duplicate values	The stack and hash map will correctly handle duplicates by storing the last seen index/value.
No greater element exists for some elements in nums1	Initialize the result array with -1, which will remain for elements without a greater element.
nums2 contains a decreasing sequence	The stack will only contain decreasing elements and pop them as soon as a greater element is encountered.
nums1 and nums2 contain negative numbers	The algorithm should work correctly with negative numbers without any modifications.
Maximum size arrays exceeding memory constraints	Ensure algorithm uses linear memory and avoids unnecessary copying to prevent memory issues.
Integer overflow possible if elements are very large	The comparison operations and data storage should use appropriate data types (e.g., int) to prevent overflow when dealing with large numbers.