Next Greater Element - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a list of integers dreams, representing a sequence of dream elements.
• Q: What is the output?
  • A: The output is a list of integers where each element represents the next greater dream element in the sequence for the corresponding element in dreams. If no greater element exists, return -1 for that element.
• Q: How should the sequence be traversed?
  • A: The sequence is circular, meaning that after the last element, the sequence continues with the first element.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to keep track of indices of elements for which the next greater element has not been found. Iterate through the list twice (simulating the circular nature) and update the result for each element when a greater element is found.

1. Initialize a list `result` of the same length as `dreams`, filled with `-1`.
2. Initialize an empty stack to store indices of elements.
3. Iterate over the sequence twice (using modulo to simulate the circular nature):
   1. For each element, check if it is greater than the element at the index stored on top of the stack.
   2. If it is, pop the index from the stack and set `result` at that index to the current element.
   3. If the current index is within the original list length (not during the second pass), push the current index onto the stack.
4. Return the `result` list.

⚠️ Common Mistakes

• Forgetting to correctly simulate the circular nature of the sequence by using modulo operation.
• Not handling cases where no greater element exists by ensuring the default value of -1 is properly retained.

I-mplement

def next_greater_dream(dreams):
    n = len(dreams)
    result = [-1] * n
    stack = []

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

    return result

# Example usage
print(next_greater_dream([1, 2, 1]))  # Output: [2, -1, 2]
print(next_greater_dream([1, 2, 3, 4, 3]))  # Output: [2, 3, 4, -1, 4]