Next Greater Event - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Standard (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 consists of two distinct integer arrays, schedule1 and schedule2, where schedule1 is a subset of schedule2.
• Q: What is the output?
  • A: The output is an array of integers where each element corresponds to the next greater event's popularity score in schedule2 for each event in schedule1. If there is no such greater event, the output is -1 for that event.
• Q: How should the next greater event be determined?
  • A: For each event in schedule1, find its position in schedule2 and determine the next event with a higher popularity score. If no such event exists, return -1 for that event.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to efficiently determine the next greater event for each element in schedule2. Store these results in a dictionary and then use the dictionary to build the result for schedule1.

1. Initialize an empty dictionary `next_greater` to map each event to its next greater event in `schedule2`.
2. Initialize an empty stack to keep track of events for which we haven't found the next greater event yet.
3. Iterate over each event in `schedule2`:
   1. While the stack is not empty and the current event is greater than the event at the top of the stack, pop the stack and record the current event as the next greater event for the popped event in `next_greater`.
   2. Push the current event onto the stack.
4. After processing all events in `schedule2`, for any remaining events in the stack, set their next greater event as `-1` in `next_greater`.
5. Construct the result array for `schedule1` by looking up the next greater event in `next_greater` for each event.
6. Return the result array.

⚠️ Common Mistakes

• Forgetting to handle events that have no next greater event, resulting in incorrect or incomplete results.
• Mismanaging the stack operations, leading to incorrect mapping in the next_greater dictionary.
• Failing to correctly map results from schedule2 to schedule1.

I-mplement

def next_greater_event(schedule1, schedule2):
    next_greater = {}
    stack = []

    # Iterate over the events in schedule2
    for event in schedule2:
        while stack and stack[-1] < event:
            next_greater[stack.pop()] = event
        stack.append(event)

    # For any remaining events in the stack, there is no greater event
    for event in stack:
        next_greater[event] = -1

    # Construct the result list for events in schedule1
    return [next_greater[event] for event in schedule1]

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