Minimum Number of Platforms in DSA Typescript - Time & Space Complexity

Time Complexity: Minimum Number of Platforms

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to calculate the minimum number of train platforms changes as the number of trains increases.

Specifically, how does the code handle more arrival and departure times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findMinPlatforms(arrivals: number[], departures: number[]): number {
  arrivals.sort((a, b) => a - b);
  departures.sort((a, b) => a - b);

  let platformNeeded = 0, maxPlatforms = 0;
  let i = 0, j = 0;

  while (i < arrivals.length && j < departures.length) {
    if (arrivals[i] <= departures[j]) {
      platformNeeded++;
      i++;
      if (platformNeeded > maxPlatforms) maxPlatforms = platformNeeded;
    } else {
      platformNeeded--;
      j++;
    }
  }
  return maxPlatforms;
}
    

This code finds the minimum number of platforms needed so that no train waits, by sorting arrival and departure times and comparing them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the arrival and departure arrays.
• How many times: Each sort runs once on n elements, and the while loop runs at most 2n times.

How Execution Grows With Input

As the number of trains (n) grows, sorting takes more time, and the loop compares arrivals and departures more times.

Input Size (n)	Approx. Operations
10	About 10 log 10 + 20 = 50 operations
100	About 100 log 100 + 200 = 1200 operations
1000	About 1000 log 1000 + 2000 = 13000 operations

Pattern observation: The operations grow a bit faster than the input size because of sorting, but the main loop grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little faster than the number of trains because sorting takes more time than just checking each train.

Common Mistake

[X] Wrong: "The while loop alone makes this O(n²) because it compares arrivals and departures repeatedly."

[OK] Correct: The loop actually moves forward through both arrays without restarting, so it runs at most 2n times, which is linear, not quadratic.

Interview Connect

Understanding how sorting and linear scanning combine helps you explain your approach clearly and shows you can analyze real problems efficiently.

Self-Check

"What if the arrival and departure arrays were already sorted? How would the time complexity change?"