algoadvance

Given a circular array (the next element of the last element is the first element of the array), find the Next Greater Number for every element. 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, output -1 for this number.

You are provided with an integer array nums. You need to return an array where for each index i in the original array, the result array contains the Next Greater Number of nums[i].

Clarifying Questions

  1. Does the circular nature mean that the array wraps around, so the element after the last element is the first element again?
    • Yes, the array is circular in nature.
  2. What is the expected output if an element does not have a next greater element?
    • In such cases, we return -1 for that element.
  3. Can the elements in the array be negative?
    • Yes, the elements in the array can be negative, positive, or zero.
  4. What is the size range of nums?
    • The array size can vary. It’s typically between 0 and 10^4 inclusive.

Strategy

We’ll use a monotonic decreasing stack to solve this problem efficiently. Here’s the approach we can take:

  1. Initialize a result array with the same length as nums and fill it with -1.
  2. Use a stack to keep track of the indices of the elements in the array.
  3. Since the array is circular, simulate the array twice by iterating from 0 to 2 * n - 1 where n is the length of the nums. The modulo operation helps us wrap around.
  4. For each element, check if the current element is greater than the element at the index on the top of the stack. If so, it means we have found the next greater element for the indices stored in the stack.
  5. Pop elements from the stack until you find one that is greater than the current element or the stack becomes empty.
  6. Push the current index onto the stack.

Time Complexity

Code

def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    
    return result

Explanation

  1. Initialization: We start with a result array filled with -1 and an empty stack.
  2. Two Passes Simulation: We iterate through 2 * n indices. The modulo operation ensures that after reaching the end of the array, we start again from the beginning, simulating the circular behavior.
  3. Stack Operations:
    • While the stack is not empty and the current number is greater than the number at the index at the top of the stack, update the result for the index at the top of the stack.
    • Push the current index onto the stack if the index is within the original array bounds.

This way, we ensure that we efficiently find the next greater elements in a circular array using a monotonic stack.

Try our interview co-pilot at AlgoAdvance.com