Minimum Platforms (Train Stations)

🎯

Minimum Platforms (Train Stations)

mediumGREEDYAmazonGoogleMicrosoft

Imagine a busy train station where multiple trains arrive and depart at different times. To avoid delays, the station manager wants to know the minimum number of platforms needed so that no train has to wait.

💡 This problem is about scheduling overlapping intervals and figuring out resource allocation. Beginners often struggle because they try to compare intervals pairwise without sorting or using efficient data structures, leading to inefficient solutions.

📋

Problem Statement

Given arrival and departure times of trains on a single day, find the minimum number of platforms required so that no train waits for another to leave. Input consists of two arrays: arrivals and departures, each of length n. Output the minimum number of platforms needed.

1 ≤ n ≤ 10^50 ≤ arrival[i], departure[i] ≤ 10^9arrival[i] ≤ departure[i] for all i

💡

Example

Input"arrivals = [900, 940, 950, 1100, 1500, 1800], departures = [910, 1200, 1120, 1130, 1900, 2000]"

Output3

At time 950, trains arriving at 900, 940, and 950 are all at the station, requiring 3 platforms.

• All trains arrive and depart at the same time → output equals number of trains
• Trains arrive in sorted order but depart in reverse order → maximum overlap
• Only one train → output is 1
• Trains with no overlap → output is 1

⚠️

Common Mistakes

Not sorting arrivals and departures separately

Incorrect platform count due to unordered timeline

✅ Sort arrivals and departures arrays independently before processing

Using <= instead of < when comparing arrival and departure times

Overcounting platforms when trains arrive exactly at departure time

✅ Use arrivals[i] <= departures[j] carefully based on problem definition; clarify with interviewer

Forgetting to update max_platforms after incrementing platforms_needed

Final answer underestimates required platforms

✅ Always update max_platforms after increasing platforms_needed

Using nested loops for large inputs

Time limit exceeded (TLE) in interviews or tests

✅ Use sorting and two-pointer or min-heap approach for efficiency

Not handling empty input arrays

Runtime errors or incorrect output

✅ Check for empty input and return 0 or handle gracefully

🧠

Brute Force (Nested Loops Checking Overlaps)

💡 This approach exists to build intuition by directly checking overlaps between every pair of trains. It is simple but inefficient, helping beginners understand the problem's core challenge.

Intuition

For each train, count how many other trains overlap with it by comparing arrival and departure times pairwise. The maximum count is the minimum platforms needed.

Algorithm

1. Initialize max_platforms to 1.
2. For each train i, count how many trains j overlap with i by checking if arrival[j] is between arrival[i] and departure[i].
3. Update max_platforms if the count for train i is greater.
4. Return max_platforms.

💡 The nested loops make it hard to see efficiency, but they clearly show how overlaps cause platform needs.

</>

Code

def min_platforms_brute_force(arrivals, departures):
    n = len(arrivals)
    max_platforms = 1
    for i in range(n):
        count = 1
        for j in range(i + 1, n):
            if (arrivals[j] >= arrivals[i] and arrivals[j] <= departures[i]) or (arrivals[i] >= arrivals[j] and arrivals[i] <= departures[j]):
                count += 1
        max_platforms = max(max_platforms, count)
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_brute_force(arrivals, departures))

Line Notes

n = len(arrivals)Determine the number of trains to iterate over all pairs.

for i in range(n):Outer loop picks each train as reference to count overlaps.

for j in range(i + 1, n):Inner loop compares train i with all subsequent trains to avoid double counting.

if (arrivals[j] >= arrivals[i] and arrivals[j] <= departures[i]) or (arrivals[i] >= arrivals[j] and arrivals[i] <= departures[j]):Check if trains i and j overlap in time.

count += 1Increment overlap count when trains overlap.

max_platforms = max(max_platforms, count)Update maximum platforms needed so far.

import java.util.*;
public class MinPlatformsBruteForce {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        int n = arrivals.length;
        int maxPlatforms = 1;
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {
                    count++;
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures));
    }
}

Line Notes

int n = arrivals.length;Get number of trains for iteration.

for (int i = 0; i < n; i++) {Outer loop selects each train as base.

for (int j = i + 1; j < n; j++) {Inner loop compares with subsequent trains to avoid repeats.

if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {Check if trains i and j overlap.

count++;Increment overlap count when overlap found.

maxPlatforms = Math.max(maxPlatforms, count);Update max platforms needed.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPlatformsBruteForce(const vector<int>& arrivals, const vector<int>& departures) {
    int n = arrivals.size();
    int maxPlatforms = 1;
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = i + 1; j < n; j++) {
            if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {
                count++;
            }
        }
        maxPlatforms = max(maxPlatforms, count);
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsBruteForce(arrivals, departures) << endl;
    return 0;
}

Line Notes

int n = arrivals.size();Determine number of trains for iteration.

for (int i = 0; i < n; i++) {Outer loop picks each train as reference.

for (int j = i + 1; j < n; j++) {Inner loop compares with subsequent trains to avoid double counting.

if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {Check if trains i and j overlap.

count++;Increment count when overlap detected.

maxPlatforms = max(maxPlatforms, count);Update maximum platforms needed.

function minPlatformsBruteForce(arrivals, departures) {
    const n = arrivals.length;
    let maxPlatforms = 1;
    for (let i = 0; i < n; i++) {
        let count = 1;
        for (let j = i + 1; j < n; j++) {
            if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {
                count++;
            }
        }
        maxPlatforms = Math.max(maxPlatforms, count);
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsBruteForce(arrivals, departures));

Line Notes

const n = arrivals.length;Get number of trains for iteration.

for (let i = 0; i < n; i++) {Outer loop selects each train as base.

for (let j = i + 1; j < n; j++) {Inner loop compares with subsequent trains to avoid repeats.

if ((arrivals[j] >= arrivals[i] && arrivals[j] <= departures[i]) || (arrivals[i] >= arrivals[j] && arrivals[i] <= departures[j])) {Check if trains i and j overlap.

count++;Increment overlap count when overlap found.

maxPlatforms = Math.max(maxPlatforms, count);Update max platforms needed.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each iterating over n trains lead to n*(n-1)/2 comparisons.

💡 For n=20, this means about 190 comparisons, which is manageable, but for n=100000, it becomes 5 billion comparisons, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, so it is only useful to understand the problem and not for actual coding in interviews.

🧠

Sorting and Two Pointer Sweep Line

💡 This approach improves efficiency by sorting arrival and departure times separately and using two pointers to simulate the timeline, counting platforms needed dynamically.

Intuition

Sort arrivals and departures. Move through both arrays with pointers. If next arrival is before next departure, increment platform count; else decrement. Track max platforms needed.

Algorithm

1. Sort the arrivals and departures arrays.
2. Initialize two pointers i and j to 0, and variables platforms_needed and max_platforms to 0.
3. While i < n and j < n, compare arrivals[i] and departures[j]:
4. If arrivals[i] <= departures[j], increment platforms_needed and i; update max_platforms if needed.
5. Else, decrement platforms_needed and increment j.
6. Return max_platforms.

💡 The two-pointer technique simulates the timeline efficiently, avoiding nested loops and counting overlaps in linear time after sorting.

</>

Code

def min_platforms_two_pointer(arrivals, departures):
    arrivals.sort()
    departures.sort()
    n = len(arrivals)
    i = j = 0
    platforms_needed = max_platforms = 0
    while i < n and j < n:
        if arrivals[i] <= departures[j]:
            platforms_needed += 1
            max_platforms = max(max_platforms, platforms_needed)
            i += 1
        else:
            platforms_needed -= 1
            j += 1
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_two_pointer(arrivals, departures))

Line Notes

arrivals.sort()Sort arrivals to process trains in chronological order.

departures.sort()Sort departures to know when platforms free up.

i = j = 0Initialize pointers for arrivals and departures arrays.

if arrivals[i] <= departures[j]:If next train arrives before earliest departure, need a platform.

platforms_needed += 1Increment platform count for new train arrival.

max_platforms = max(max_platforms, platforms_needed)Track maximum platforms needed so far.

else:If next departure is before next arrival, free a platform.

platforms_needed -= 1Decrement platform count as train departs.

import java.util.*;
public class MinPlatformsTwoPointer {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        Arrays.sort(arrivals);
        Arrays.sort(departures);
        int n = arrivals.length;
        int i = 0, j = 0, platformsNeeded = 0, maxPlatforms = 0;
        while (i < n && j < n) {
            if (arrivals[i] <= departures[j]) {
                platformsNeeded++;
                maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
                i++;
            } else {
                platformsNeeded--;
                j++;
            }
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures));
    }
}

Line Notes

Arrays.sort(arrivals);Sort arrivals to process in chronological order.

Arrays.sort(departures);Sort departures to track platform freeing times.

int i = 0, j = 0Initialize pointers for arrivals and departures.

if (arrivals[i] <= departures[j]) {If next arrival is before or at next departure, need platform.

platformsNeeded++;Increment platform count for arriving train.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Update max platforms needed.

else {If next departure is before next arrival, free a platform.

platformsNeeded--;Decrement platform count.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPlatformsTwoPointer(vector<int>& arrivals, vector<int>& departures) {
    sort(arrivals.begin(), arrivals.end());
    sort(departures.begin(), departures.end());
    int n = arrivals.size();
    int i = 0, j = 0, platformsNeeded = 0, maxPlatforms = 0;
    while (i < n && j < n) {
        if (arrivals[i] <= departures[j]) {
            platformsNeeded++;
            maxPlatforms = max(maxPlatforms, platformsNeeded);
            i++;
        } else {
            platformsNeeded--;
            j++;
        }
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsTwoPointer(arrivals, departures) << endl;
    return 0;
}

Line Notes

sort(arrivals.begin(), arrivals.end());Sort arrivals to process in chronological order.

sort(departures.begin(), departures.end());Sort departures to track platform freeing times.

int i = 0, j = 0Initialize pointers for arrivals and departures.

if (arrivals[i] <= departures[j]) {If next arrival is before or at next departure, need platform.

platformsNeeded++;Increment platform count for arriving train.

maxPlatforms = max(maxPlatforms, platformsNeeded);Update max platforms needed.

else {If next departure is before next arrival, free a platform.

platformsNeeded--;Decrement platform count.

function minPlatformsTwoPointer(arrivals, departures) {
    arrivals.sort((a, b) => a - b);
    departures.sort((a, b) => a - b);
    const n = arrivals.length;
    let i = 0, j = 0, platformsNeeded = 0, maxPlatforms = 0;
    while (i < n && j < n) {
        if (arrivals[i] <= departures[j]) {
            platformsNeeded++;
            maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
            i++;
        } else {
            platformsNeeded--;
            j++;
        }
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsTwoPointer(arrivals, departures));

Line Notes

arrivals.sort((a, b) => a - b);Sort arrivals to process in chronological order.

departures.sort((a, b) => a - b);Sort departures to track platform freeing times.

let i = 0, j = 0Initialize pointers for arrivals and departures.

if (arrivals[i] <= departures[j]) {If next arrival is before or at next departure, need platform.

platformsNeeded++;Increment platform count for arriving train.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Update max platforms needed.

else {If next departure is before next arrival, free a platform.

platformsNeeded--;Decrement platform count.

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Sorting takes O(n log n), and the two-pointer sweep is O(n), so overall O(n log n).

💡 For n=100000, sorting is feasible and the linear sweep is very efficient compared to brute force.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem.

🧠

Using Min-Heap (Priority Queue) to Track Platforms

💡 This approach uses a min-heap to track the earliest departure time among trains currently occupying platforms, allowing dynamic allocation of platforms.

Intuition

Sort trains by arrival time. For each train, if its arrival is after or equal to the earliest departure (top of min-heap), reuse that platform by popping from heap. Otherwise, allocate a new platform by pushing departure time. The heap size at any time is platforms needed.

Algorithm

1. Create a list of pairs (arrival, departure) and sort by arrival time.
2. Initialize a min-heap to store departure times.
3. Iterate over sorted trains:
4. If heap is not empty and current arrival >= earliest departure (heap top), pop from heap (platform freed).
5. Push current train's departure time into heap (platform allocated).
6. Track max heap size during iteration as minimum platforms needed.
7. Return max heap size.

💡 The heap dynamically tracks platform availability, making it easy to allocate or free platforms in O(log n) time per train.

</>

Code

import heapq

def min_platforms_min_heap(arrivals, departures):
    trains = sorted(zip(arrivals, departures), key=lambda x: x[0])
    heap = []
    max_platforms = 0
    for arrival, departure in trains:
        while heap and heap[0] <= arrival:
            heapq.heappop(heap)
        heapq.heappush(heap, departure)
        max_platforms = max(max_platforms, len(heap))
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_min_heap(arrivals, departures))

Line Notes

trains = sorted(zip(arrivals, departures), key=lambda x: x[0])Pair and sort trains by arrival time for chronological processing.

heap = []Initialize min-heap to track earliest departure times.

while heap and heap[0] <= arrival:Remove all trains that have departed before or exactly at current arrival, freeing platforms.

heapq.heappop(heap)Pop earliest departure time from heap to free platform.

heapq.heappush(heap, departure)Add current train's departure time to heap, allocating platform.

max_platforms = max(max_platforms, len(heap))Track maximum platforms needed as heap size.

import java.util.*;
public class MinPlatformsMinHeap {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        int n = arrivals.length;
        int[][] trains = new int[n][2];
        for (int i = 0; i < n; i++) {
            trains[i][0] = arrivals[i];
            trains[i][1] = departures[i];
        }
        Arrays.sort(trains, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int maxPlatforms = 0;
        for (int[] train : trains) {
            while (!heap.isEmpty() && heap.peek() <= train[0]) {
                heap.poll();
            }
            heap.offer(train[1]);
            maxPlatforms = Math.max(maxPlatforms, heap.size());
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures));
    }
}

Line Notes

int[][] trains = new int[n][2];Create array of train arrival and departure pairs.

Arrays.sort(trains, Comparator.comparingInt(a -> a[0]));Sort trains by arrival time.

PriorityQueue<Integer> heap = new PriorityQueue<>();Min-heap to track earliest departure times.

while (!heap.isEmpty() && heap.peek() <= train[0]) {Remove trains that have departed before or exactly at current arrival.

heap.poll();Pop earliest departure to free platform.

heap.offer(train[1]);Add current train's departure time to heap.

maxPlatforms = Math.max(maxPlatforms, heap.size());Track max platforms needed.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int minPlatformsMinHeap(vector<int>& arrivals, vector<int>& departures) {
    int n = arrivals.size();
    vector<pair<int,int>> trains(n);
    for (int i = 0; i < n; i++) {
        trains[i] = {arrivals[i], departures[i]};
    }
    sort(trains.begin(), trains.end());
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int maxPlatforms = 0;
    for (auto& train : trains) {
        while (!minHeap.empty() && minHeap.top() <= train.first) {
            minHeap.pop();
        }
        minHeap.push(train.second);
        maxPlatforms = max(maxPlatforms, (int)minHeap.size());
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsMinHeap(arrivals, departures) << endl;
    return 0;
}

Line Notes

vector<pair<int,int>> trains(n);Pair arrival and departure times for sorting.

sort(trains.begin(), trains.end());Sort trains by arrival time.

priority_queue<int, vector<int>, greater<int>> minHeap;Min-heap to track earliest departure times.

while (!minHeap.empty() && minHeap.top() <= train.first) {Remove trains that have departed before or exactly at current arrival.

minHeap.pop();Pop earliest departure to free platform.

minHeap.push(train.second);Add current train's departure time to heap.

maxPlatforms = max(maxPlatforms, (int)minHeap.size());Track max platforms needed.

class MinHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0 && this.heap[this.parent(i)] > this.heap[i]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 0) return null;
        const root = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.heapify(0);
        }
        return root;
    }
    heapify(i) {
        let smallest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
        if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
        if (smallest !== i) {
            this.swap(i, smallest);
            this.heapify(smallest);
        }
    }
    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
    size() {
        return this.heap.length;
    }
}

function minPlatformsMinHeap(arrivals, departures) {
    const trains = arrivals.map((a, i) => [a, departures[i]]).sort((a, b) => a[0] - b[0]);
    const heap = new MinHeap();
    let maxPlatforms = 0;
    for (const [arrival, departure] of trains) {
        while (heap.size() > 0 && heap.peek() <= arrival) {
            heap.pop();
        }
        heap.push(departure);
        maxPlatforms = Math.max(maxPlatforms, heap.size());
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsMinHeap(arrivals, departures));

Line Notes

const trains = arrivals.map((a, i) => [a, departures[i]]).sort((a, b) => a[0] - b[0]);Pair and sort trains by arrival time.

const heap = new MinHeap();Initialize min-heap to track earliest departure times.

while (heap.size() > 0 && heap.peek() <= arrival) {Remove trains that have departed before or exactly at current arrival.

heap.pop();Pop earliest departure to free platform.

heap.push(departure);Add current train's departure time to heap.

maxPlatforms = Math.max(maxPlatforms, heap.size());Track maximum platforms needed.

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), and each train is pushed and popped from heap at most once, each operation O(log n).

💡 For n=100000, this approach is efficient and uses extra space for the heap but is practical.

Interview Verdict: Accepted

This approach is optimal and useful when you want to track platforms dynamically or extend to more complex constraints.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer approach is the best balance of simplicity and efficiency, and is recommended for interviews unless the problem requires dynamic allocation where min-heap shines.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting and Two Pointer Sweep Line	O(n log n)	O(1)	No	N/A	Code this approach in 95% of interviews
3. Min-Heap (Priority Queue)	O(n log n)	O(n)	No	N/A	Mention or code if asked for dynamic allocation or extensions

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then explain optimizations clearly. Practice coding the two-pointer approach as it is the most common solution.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of overlaps.Discuss inefficiency and propose sorting with two pointers.Optionally mention min-heap approach if asked for alternatives.Write clean code for the two-pointer approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of interval overlaps, sorting, and efficient iteration. They also check if you can optimize from brute force to O(n log n) and handle edge cases.

Common Follow-ups

• What if arrival and departure times are not sorted? → Sort first.
• How to handle trains arriving and departing at the same time? → Decide if arrival <= departure counts as overlap.
• Can you solve with O(n) time? → Not without constraints; sorting is needed.
• What if trains have platform preferences? → Use min-heap or segment tree for allocation.

💡 These follow-ups test your ability to handle input variations and extend the problem logically.

🔍

Pattern Recognition

When to Use

1. Problem involves intervals with start and end times 2. Need to find maximum overlap or resource allocation 3. Sorting intervals by start or end time is possible 4. Counting simultaneous events or scheduling resources

Signature Phrases

minimum number of platformstrains arriving and departingno train waits

NOT This Pattern When

Problems that require maximum non-overlapping intervals or interval partitioning without resource counting

Similar Problems

Meeting Rooms II - also finds minimum rooms for overlapping meetingsCar Pooling - scheduling resources over intervalsInterval Scheduling - selecting non-overlapping intervals

Practice

1. You are given a numeric string and an integer k. The task is to remove exactly k digits from the string so that the resulting number is the smallest possible. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Backtracking to try all combinations of digits to remove

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest

C. Sorting the digits and removing the largest k digits

D. Greedy algorithm using a stack to maintain a monotonically increasing sequence of digits

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach to decide which digits to remove as we scan the string.

2. Step 2: Why greedy with stack works

   The stack-based greedy approach maintains a monotonically increasing sequence by popping larger digits when a smaller digit is encountered, ensuring the smallest possible prefix at each step.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy stack approach is known optimal for this problem [OK]

Hint: Monotonic stack ensures smallest prefix greedily [OK]

Common Mistakes:

• Assuming sorting digits works ignores digit order
• Thinking DP is needed for this greedy problem
• Trying brute force is too slow for large inputs

2. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

3. What is the time complexity of the optimal greedy algorithm for partitioning labels using a fixed-size array for last occurrences, given a string of length n?

medium

A. O(n) because each character is processed a constant number of times

B. O(n log n) due to sorting characters by last occurrence

C. O(n^2) due to nested scanning for last occurrences

D. O(n * 26) because of fixed alphabet size iteration

Solution

1. Step 1: Analyze last occurrence computation

   We scan the string once to record last occurrence of each character in O(n).

2. Step 2: Analyze partitioning loop

   We iterate over the string once more, updating partition end in O(1) per character.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans over string length n -> O(n) time [OK]

Hint: Two passes over string -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing fixed alphabet size iteration as O(n*26)
• Thinking sorting is needed

4. Suppose the problem is modified so that dominoes can be rotated multiple times (reused) to achieve uniformity, or the arrays can contain values outside 1-6. Which approach correctly adapts the solution?

hard

A. Check all unique values appearing in either array as candidates with early exit

B. Continue checking only the first domino's two values as candidates, ignoring others

C. Use dynamic programming to track rotations for all possible values 1 to 6 only

D. Sort arrays and greedily pick the most frequent value to minimize rotations

Solution

1. Step 1: Identify candidate values

   With values outside 1-6 and reuse allowed, candidates are all unique values in A and B, not just first domino.

2. Step 2: Check feasibility for each candidate

   For each candidate, verify if all dominoes can be rotated to match it, counting minimal rotations.

3. Step 3: Early exit optimization

   Stop checking candidates as soon as a valid minimal rotation count is found.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Checking all unique values covers extended domain and reuse [OK]

Hint: Check all unique values when domain expands [OK]

Common Mistakes:

• Checking only first domino candidates
• Limiting candidates to 1-6 values only

5. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), and you want to generate a string of length n with no two adjacent characters the same. Which modification to the max heap approach is necessary to handle this variant correctly?

hard

A. No change needed; the original heap approach works as is for infinite reuse

B. Track only the last used character and pick any other character from the set for the next position

C. Use a queue instead of a heap to cycle through characters ensuring no adjacency

D. Remove frequency counts and always push characters back immediately after use to allow reuse

Solution

1. Step 1: Understand infinite reuse implication

   Since characters can be reused infinitely, frequency counts are irrelevant; characters must be available again immediately after use.

2. Step 2: Modify heap usage

   Remove frequency decrement logic and always push characters back immediately after use to allow reuse while avoiding adjacency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Immediate pushback enables infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means no frequency decrement [OK]

Common Mistakes:

• Assuming original approach works unchanged
• Using queue without frequency logic
• Ignoring adjacency constraints