Bird
Raised Fist0

What is the auxiliary space complexity of the sweep line algorithm for minimum platforms with n trains?

medium🪤 Complexity Trap Q6 of Q15
Intervals - Minimum Number of Platforms Required
What is the auxiliary space complexity of the sweep line algorithm for minimum platforms with n trains?
AO(1)
BO(n)
CO(n²)
DO(log n)
Step-by-Step Solution
Solution:

  1. Step 1: Count extra space

    Events array stores 2n entries -> O(n) space.

  2. Step 2: Consider recursion or stack

    Algorithm is iterative, no recursion stack, so no extra stack space.

  3. Step 3: Verify no quadratic space

    Only O(n) space used, not O(n²).

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Events array size dominates space -> O(n) [OK]
Quick Trick: Events array size -> O(n) space [OK]
Common Mistakes:
MISTAKES
  • Assuming O(1) space ignoring events array
Trap Explanation:
PITFALL
  • Candidates forget auxiliary arrays and count only variables, underestimating space.
Interviewer Note:
CONTEXT
  • Tests understanding of auxiliary space beyond input arrays.
Master "Minimum Number of Platforms Required" in Intervals

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Intervals Quizzes
Count of Intervals Containing Each Point - Count of Intervals Containing Each Point - Quiz 1easy Employee Free Time - Employee Free Time - Quiz 12easy Insert Interval - Insert Interval - Quiz 9hard Meeting Rooms II (Minimum Conference Rooms) - Meeting Rooms II (Minimum Conference Rooms) - Quiz 6medium Meeting Rooms II (Minimum Conference Rooms) - Meeting Rooms II (Minimum Conference Rooms) - Quiz 14medium Merge Intervals - Merge Intervals - Quiz 3easy Minimum Interval to Include Each Query - Minimum Interval to Include Each Query - Quiz 10hard Minimum Interval to Include Each Query - Minimum Interval to Include Each Query - Quiz 14medium Non-overlapping Intervals (Max Non-Overlap) - Non-overlapping Intervals (Max Non-Overlap) - Quiz 3easy Remove Covered Intervals - Remove Covered Intervals - Quiz 6medium