Minimum Platforms (Train Stations)

📋

Minimum Platforms (Train Stations)

Edge cases:

</>

IDE

def min_platforms(arrivals: list[int], departures: list[int]) -> int:public int minPlatforms(int[] arrivals, int[] departures)int minPlatforms(vector<int> arrivals, vector<int> departures)function minPlatforms(arrivals, departures)

def min_platforms(arrivals, departures):
    # Write your solution here
    pass

class Solution {
    public int minPlatforms(int[] arrivals, int[] departures) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minPlatforms(vector<int> arrivals, vector<int> departures) {
    // Write your solution here
    return 0;
}

function minPlatforms(arrivals, departures) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Not sorting departures separately, assuming they are sorted with arrivals.✅ Sort both arrivals and departures arrays independently before sweeping.

Wrong: 0Not handling empty input arrays correctly, returning default 0 or uninitialized value.✅ Return 0 immediately if arrivals array is empty.

Wrong: 2Off-by-one error when arrival time equals departure time, causing undercounting platforms.✅ Use <= for arrival pointer comparison and < for departure pointer comparison in sweep.

Wrong: TLEUsing brute force O(n^2) nested loops instead of sorting and sweeping.✅ Implement sorting and two-pointer sweep line algorithm with O(n log n) complexity.

Wrong: Less than actual platformsGreedy assignment without sorting arrivals and departures.✅ Sort both arrays before processing to correctly count overlaps.

✓

Test Cases

Try testing your solution on empty and single train inputs to handle base cases.

Consider tricky overlaps and ordering of arrivals and departures to catch subtle bugs.

Optimize your solution to O(n log n) by sorting and using a two-pointer sweep line.

t1_01basic

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Sort arrival and departure times separately to analyze overlaps.

💡 Use two pointers to sweep through arrivals and departures to count overlaps.

💡 Increment platform count when arrival <= departure pointer, else decrement.

Why it failed: Incorrect platform count due to not sorting arrivals and departures separately or incorrect pointer increments. Fix by sorting both arrays and using two-pointer sweep.

✓ Correctly computed minimum platforms using sorted arrays and two-pointer sweep.

t1_02basic

Input{"arrivals":[100,200,300,400],"departures":[150,250,350,450]}

Expected1

⏱ Performance - must finish in 2000ms

No trains overlap in time; only one platform needed.

💡 Check if any arrival time overlaps with previous departures.

💡 If arrivals are always after previous departures, platforms needed is 1.

💡 Confirm by sorting and sweeping arrivals and departures.

Why it failed: Overcounting platforms by not checking overlaps properly. Fix by comparing arrival and departure pointers correctly during sweep.

✓ Correctly identified no overlaps, so only one platform needed.

t2_01edge

Input{"arrivals":[],"departures":[]}

Expected0

⏱ Performance - must finish in 2000ms

No trains means no platforms needed.

💡 Consider the case when there are no trains at all.

💡 The minimum platforms required should be zero if input arrays are empty.

💡 Return 0 immediately if arrivals array is empty.

Why it failed: Function does not handle empty input arrays, causing errors or wrong output. Fix by returning 0 when arrivals is empty.

✓ Correctly returns 0 platforms for empty input.

t2_02edge

Input{"arrivals":[500],"departures":[500]}

Expected1

⏱ Performance - must finish in 2000ms

Single train arriving and departing at the same time requires one platform.

💡 Check behavior when only one train is present.

💡 Minimum platforms should be 1 regardless of arrival and departure times.

💡 Return 1 if arrivals length is 1.

Why it failed: Fails single element case by returning 0 or more than 1. Fix by returning 1 when only one train is present.

✓ Correctly returns 1 platform for single train.

t2_03edge

Input{"arrivals":[100,100,100],"departures":[100,100,100]}

Expected3

⏱ Performance - must finish in 2000ms

All trains arrive and depart at the same time, so all require separate platforms.

💡 Consider when all trains have identical arrival and departure times.

💡 Platforms needed equals number of trains in this case.

💡 Count maximum simultaneous trains at the same time.

Why it failed: Incorrectly counts overlapping trains when arrival == departure for all. Fix by counting all trains arriving at the same time as separate platforms.

✓ Correctly counts platforms equal to number of trains when all times are identical.

t2_04edge

Input{"arrivals":[100,200,300,400],"departures":[150,250,350,450]}

Expected1

⏱ Performance - must finish in 2000ms

Trains with no overlap require only one platform.

💡 Check if arrivals are always after previous departures.

💡 If no overlaps, minimum platforms is 1.

💡 Confirm by sorting and sweeping arrivals and departures.

Why it failed: Incorrectly counts more than one platform when no overlaps exist. Fix by proper two-pointer comparison.

✓ Correctly identifies single platform needed for non-overlapping trains.

t3_01corner

Input{"arrivals":[100,200,300,400],"departures":[100,200,300,400]}

Expected1

⏱ Performance - must finish in 2000ms

Trains arrive in sorted order but depart in reverse order, causing maximum overlap.

💡 Check if sorting departures independently is done correctly.

💡 Beware of assuming departures are sorted with arrivals.

💡 Sort both arrays separately before sweeping to count overlaps.

Why it failed: Incorrect platform count due to not sorting departures separately or assuming sorted order. Fix by sorting both arrays independently.

✓ Correctly handles maximum overlap by sorting both arrays.

t3_02corner

Input{"arrivals":[100,100,200,300],"departures":[200,200,300,400]}

Expected3

⏱ Performance - must finish in 2000ms

Multiple trains arriving at the same time with overlapping departures require careful counting.

💡 Handle multiple trains arriving at the same time correctly.

💡 Increment platform count for each arrival before decrementing for departures.

💡 Use <= comparison for arrivals and < for departures in sweep.

Why it failed: Off-by-one error in counting platforms when arrivals equal departures. Fix by using correct comparison operators in sweep logic.

✓ Correctly counts platforms with equal arrival and departure times.

t3_03corner

Input{"arrivals":[100,150,200,250],"departures":[180,220,300,400]}

Expected2

⏱ Performance - must finish in 2000ms

Tests greedy trap where one might assign platforms greedily without sorting.

💡 Sorting is essential before assigning platforms.

💡 Greedy assignment without sorting leads to wrong platform count.

💡 Sort arrivals and departures before sweeping to avoid greedy trap.

Why it failed: Greedy approach without sorting causes undercounting platforms. Fix by sorting both arrays before processing.

✓ Correctly avoids greedy trap by sorting and sweeping.

t4_01performance

Input{"arrivals":[0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990],"departures":[5,15,25,35,45,55,65,75,85,95,105,115,125,135,145,155,165,175,185,195,205,215,225,235,245,255,265,275,285,295,305,315,325,335,345,355,365,375,385,395,405,415,425,435,445,455,465,475,485,495,505,515,525,535,545,555,565,575,585,595,605,615,625,635,645,655,665,675,685,695,705,715,725,735,745,755,765,775,785,795,805,815,825,835,845,855,865,875,885,895,905,915,925,935,945,955,965,975,985,995]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 trains with sorted arrivals and departures; O(n log n) solution must complete within 2 seconds.

💡 Use sorting and two-pointer sweep for O(n log n) complexity.

💡 Avoid nested loops which cause O(n^2) time and TLE.

💡 Implement efficient sweep line algorithm with sorted arrays.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n log n) sorting and two-pointer sweep.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. You have a sequence of children standing in a line, each with a rating. You must distribute candies such that each child has at least one candy, and any child with a higher rating than an immediate neighbor gets more candies than that neighbor. Which algorithmic approach guarantees the minimum total candies distributed?

easy

A. Two-pass greedy: first left-to-right to satisfy left neighbors, then right-to-left to satisfy right neighbors

B. Brute force repeated adjustment until no changes occur

C. Single pass greedy from left to right only, assigning candies based on previous child

D. Dynamic programming with memoization over all subsequences

Solution

1. Step 1: Understand the problem constraints

   Each child must have at least one candy, and children with higher rating than neighbors must have more candies.

2. Step 2: Identify algorithm that satisfies both left and right neighbor constraints

   Two-pass greedy first ensures left neighbor condition, then right neighbor condition, guaranteeing minimal total candies.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes ensure both neighbor constraints met [OK]

Hint: Two passes needed to satisfy both neighbors [OK]

Common Mistakes:

• Using single pass left-to-right misses right neighbor constraints
• Assuming brute force is efficient enough
• Confusing DP with greedy here

2. You have different types of boxes, each with a number of boxes and units per box. You want to load a truck with a limited capacity to maximize total units. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer by splitting box types and merging results

B. Greedy algorithm sorting box types by units per box in descending order and picking boxes until the truck is full

C. Breadth-first search exploring all possible box selections up to truck capacity

D. Dynamic programming considering all combinations of boxes and capacities

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing units loaded on a truck with limited capacity by selecting boxes with different units per box.

2. Step 2: Identify optimal approach

   Since the problem involves discrete box counts and a capacity constraint, the greedy approach does not always guarantee an optimal solution. Dynamic programming considering all combinations ensures the optimal solution by exploring all feasible selections.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP guarantees optimality for knapsack-like problems with discrete items [OK]

Hint: Use DP for discrete knapsack problems to guarantee optimality [OK]

Common Mistakes:

• Assuming greedy always works
• Trying BFS which is inefficient
• Ignoring capacity constraints

3. 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

4. Suppose the problem is modified so that the input list can contain negative integers as well. Which of the following approaches correctly adapts the algorithm to handle negatives and still produce the largest concatenated number?

hard

A. Convert negatives to positive strings before sorting with the comparator, then prepend '-' to those in final output

B. Filter out negative numbers since they cannot contribute to the largest concatenation

C. Separate negatives and positives, sort positives with comparator, sort negatives by absolute value descending, then concatenate positives followed by negatives

D. Convert all numbers to strings including negatives, then sort with the same comparator comparing concatenations

Solution

1. Step 1: Recognize negatives affect ordering and concatenation semantics

   Negative numbers cannot be treated the same as positives because concatenation with '-' changes lex order.

2. Step 2: Separate positives and negatives, sort positives with original comparator, sort negatives by absolute value descending

   Concatenate positives first (largest number), then negatives to maintain largest overall concatenation.

3. Step 3: This approach preserves ordering logic and handles negatives correctly

   Other options either ignore negatives or mishandle signs causing incorrect results.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Separating and sorting by sign handles negatives correctly [OK]

Hint: Negatives require separate handling, not just string comparison [OK]

Common Mistakes:

• Treating negatives as strings directly
• Ignoring negatives
• Converting negatives to positives incorrectly

5. Suppose the problem is changed so that some people can be assigned to either city multiple times (reusable assignments), or the number of people sent to each city is not fixed. Which approach correctly adapts the solution?

hard

A. Use a dynamic programming approach to handle variable counts and reuse assignments

B. Use the same greedy sorting by cost difference and assign exactly n people to each city

C. Sort by absolute cost to city A and assign all to city A to minimize cost

D. Assign people greedily without sorting, picking the cheaper city for each person

Solution

1. Step 1: Understand problem change

   Allowing reuse or variable counts breaks the fixed half assignment constraint, invalidating the greedy approach.

2. Step 2: Why DP is needed

   Dynamic programming can explore all valid assignments with reuse or variable counts, ensuring minimal total cost under new constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails when constraints are relaxed; DP handles complex state space [OK]

Hint: Relaxed constraints require DP, not greedy [OK]

Common Mistakes:

• Applying greedy unchanged despite constraint changes
• Ignoring reuse possibility in assignment
• Assuming sorting by absolute cost suffices