Jobs

Interviews

Discussions

Next Greater Element II

Medium

Asked by:

+10

More companies

24 views

Topics:

ArraysStacks

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

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

Constraints:

1 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Next Greater Element II

Medium

Asked by:

More companies

24 views

Topics:

ArraysStacks

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

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

Constraints:

1 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹

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 is the maximum size of the input array nums?
Can the input array contain negative numbers, zeros, or only positive integers?
If an element doesn't have a next greater element, should I return -1 as an integer, or is a different sentinel value expected?
Are duplicate values allowed in the input array, and if so, how should they be handled when searching for the next greater element?
Is the array guaranteed to contain at least one element?

Brute Force Solution

Approach

For each number in the sequence, we want to find the very next number that's bigger than it, wrapping around to the beginning if needed. The brute force way is simple: for each number, we just look at every other number in the sequence until we find one that's bigger.

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

Take the first number in the sequence.
Look at each of the following numbers, one by one, to see if it's bigger than the first number.
If you find a bigger number, remember it and move on to the next number in the original sequence.
If you reach the end of the sequence without finding a bigger number, start back at the beginning of the sequence and keep looking.
If you go all the way through the sequence and still haven't found a bigger number, then there isn't one, so mark that there's no bigger number for the original number you started with.
Now, repeat this process for the second number in the sequence, then the third, and so on, until you've done it for every number in the sequence.

Code Implementation

def next_greater_element_ii_brute_force(numbers):
    result = []
    array_length = len(numbers)

    for i in range(array_length):
        next_greater = -1

        # Search for the next greater element
        for j in range(array_length):
            # Calculate circular index.
            circular_index = (i + j + 1) % array_length

            if numbers[circular_index] > numbers[i]:
                next_greater = numbers[circular_index]
                break

        # Append the next greater element to the result
        result.append(next_greater)

    return result

Big(O) Analysis

Time Complexity

O(n²) – For each of the n elements in the input array, the algorithm iterates through the remaining elements to find the next greater element, potentially wrapping around to the beginning of the array. In the worst-case scenario, for each element, the algorithm may need to iterate through all n elements to either find a greater element or determine that one doesn't exist. This results in nested loops where the outer loop runs n times and the inner loop also runs up to n times, leading to approximately n * n operations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach described iterates through the input array multiple times, but it doesn't create any additional data structures that scale with the input size N, which is the number of elements in the sequence. Only a few constant-size variables are used to track indices and the next greater element found so far. Therefore, the space complexity is constant. It uses a fixed amount of auxiliary space regardless of how large the array is.

Optimal Solution

Approach

This problem asks us to find, for each number, the next larger number in a circular list. Instead of searching the entire list repeatedly, we'll use a special tool to keep track of potential next larger numbers. This helps us efficiently find the answer for each number in one go.

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

Imagine a tool that can hold numbers. This tool helps us remember which numbers might be the 'next greater number' for earlier numbers in the list.
We go through the numbers in the list twice, as if the list were wrapped around itself.
For each number, we compare it with the numbers in our tool. If the current number is bigger than the number at the top of the tool, we know we've found the 'next greater number' for the number at the top of the tool. We record this and remove the number from the tool.
We keep doing this until the current number is no longer bigger than the number at the top of the tool, or the tool is empty.
If we reach a point where the tool is empty or the current number isn't bigger, we add the current number to the top of the tool. This means it's waiting to see if a bigger number comes along later.
After processing all the numbers twice, any numbers left in the tool don't have a 'next greater number' in the list, so their 'next greater number' is considered to be non-existent.

Code Implementation

def next_greater_elements_two(numbers):
    result = [-1] * len(numbers)
    stack = []

    # Iterate through the array twice to simulate circularity
    for i in range(2 * len(numbers)):
        current_index = i % len(numbers)

        # Pop elements from stack if current element is greater
        while stack and numbers[stack[-1]] < numbers[current_index]:
            result[stack.pop()] = numbers[current_index]

        # Store the index if within the original array length
        if i < len(numbers):
            stack.append(i)

    return result

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array nums of size n twice in a loop, effectively simulating a circular traversal. Inside this loop, we use a stack. While the worst-case inner loop (while stack is not empty) might seem like it adds another factor of n, each element is pushed onto and popped from the stack at most once. Therefore, the number of stack operations is bounded by 2n. Thus, the dominant operations are proportional to n, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a stack to store elements from the input array, where N is the size of the input array. In the worst-case scenario, all elements of the input array could be pushed onto the stack before any element is popped, leading to a stack size proportional to N. Therefore, the auxiliary space required is directly dependent on the input size N. The space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to process.
Array with one element	Return an array containing only -1 as a single element array will never have a next greater element.
Array with all elements being equal	Return an array filled with -1 since no element is greater than any other.
Array sorted in descending order	Return an array filled with -1 since no element has a next greater element within the circular array.
Large input array with potential for stack overflow (if using recursion)	Use an iterative approach with a stack to avoid stack overflow issues for very large input sizes.
Array containing large positive and negative numbers (integer overflow concerns)	Ensure the data type used for calculations (e.g., comparisons) can handle the range of possible values to prevent integer overflows.
Array contains duplicates of the largest element	The algorithm must correctly handle these duplicates when determining the next greater element for other elements.
Circular wrap-around with the greatest number at the end	The circular nature of the array needs to be correctly handled when the greatest number is at the end, and the next greater element for earlier numbers might be at the beginning.

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 is the maximum size of the input array nums?
Can the input array contain negative numbers, zeros, or only positive integers?
If an element doesn't have a next greater element, should I return -1 as an integer, or is a different sentinel value expected?
Are duplicate values allowed in the input array, and if so, how should they be handled when searching for the next greater element?
Is the array guaranteed to contain at least one element?

Brute Force Solution

Approach

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

Take the first number in the sequence.
Look at each of the following numbers, one by one, to see if it's bigger than the first number.
If you find a bigger number, remember it and move on to the next number in the original sequence.
If you reach the end of the sequence without finding a bigger number, start back at the beginning of the sequence and keep looking.
If you go all the way through the sequence and still haven't found a bigger number, then there isn't one, so mark that there's no bigger number for the original number you started with.
Now, repeat this process for the second number in the sequence, then the third, and so on, until you've done it for every number in the sequence.

Code Implementation

def next_greater_element_ii_brute_force(numbers):
    result = []
    array_length = len(numbers)

    for i in range(array_length):
        next_greater = -1

        # Search for the next greater element
        for j in range(array_length):
            # Calculate circular index.
            circular_index = (i + j + 1) % array_length

            if numbers[circular_index] > numbers[i]:
                next_greater = numbers[circular_index]
                break

        # Append the next greater element to the result
        result.append(next_greater)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a tool that can hold numbers. This tool helps us remember which numbers might be the 'next greater number' for earlier numbers in the list.
We go through the numbers in the list twice, as if the list were wrapped around itself.
For each number, we compare it with the numbers in our tool. If the current number is bigger than the number at the top of the tool, we know we've found the 'next greater number' for the number at the top of the tool. We record this and remove the number from the tool.
We keep doing this until the current number is no longer bigger than the number at the top of the tool, or the tool is empty.
If we reach a point where the tool is empty or the current number isn't bigger, we add the current number to the top of the tool. This means it's waiting to see if a bigger number comes along later.
After processing all the numbers twice, any numbers left in the tool don't have a 'next greater number' in the list, so their 'next greater number' is considered to be non-existent.

Code Implementation

def next_greater_elements_two(numbers):
    result = [-1] * len(numbers)
    stack = []

    # Iterate through the array twice to simulate circularity
    for i in range(2 * len(numbers)):
        current_index = i % len(numbers)

        # Pop elements from stack if current element is greater
        while stack and numbers[stack[-1]] < numbers[current_index]:
            result[stack.pop()] = numbers[current_index]

        # Store the index if within the original array length
        if i < len(numbers):
            stack.append(i)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to process.
Array with one element	Return an array containing only -1 as a single element array will never have a next greater element.
Array with all elements being equal	Return an array filled with -1 since no element is greater than any other.
Array sorted in descending order	Return an array filled with -1 since no element has a next greater element within the circular array.
Large input array with potential for stack overflow (if using recursion)	Use an iterative approach with a stack to avoid stack overflow issues for very large input sizes.
Array containing large positive and negative numbers (integer overflow concerns)	Ensure the data type used for calculations (e.g., comparisons) can handle the range of possible values to prevent integer overflows.
Array contains duplicates of the largest element	The algorithm must correctly handle these duplicates when determining the next greater element for other elements.
Circular wrap-around with the greatest number at the end	The circular nature of the array needs to be correctly handled when the greatest number is at the end, and the next greater element for earlier numbers might be at the beginning.