TIP102 Unit 3 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
schedule1
and schedule2
, where schedule1
is a subset of schedule2
.schedule2
for each event in schedule1
. If there is no such greater event, the output is -1
for that event.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.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
next_greater
dictionary.schedule2
to schedule1
.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]