These are the notes for DSA episode 60: two interview classics where a short proof turns a slow search into one pass. Part 1, Gas Station: a delivery van on a ring road of petrol pumps; where should it start? Trying every start is correct but O(n²): about 15 seconds for 1,00,000 pumps (Time Limit Exceeded on LeetCode). Two facts (the total decides whether any start works, and if the tank runs dry at pump i, no pump from the start to i can be the start) give an O(n) answer. Part 2, Task Scheduler: a CPU with a cooldown between runs of the same task. Trying every order is correct but Time Limit Exceeded on 20 tasks; a greedy "first ready task, alphabetically" gives 4 where 3 is possible; the frame built by the most frequent task gives a formula. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.
The problem, in real life
Part 1. A delivery van must drive once around a ring road (like a city's Outer Ring Road). At pump i it can fill gas[i] litres; driving from pump i to the next burns cost[i] litres. The tank starts empty. Where should it start so it gets all the way round? If nowhere works, answer -1.
Part 2. In cricket a bowler can't bowl two overs in a row. A CPU has a similar rule: each time unit it runs one task or sits idle, and two runs of the same task type need at least n units between them (a cooldown). What's the fewest time units to finish all tasks?
| Real life | In code |
|---|---|
Pump i's fuel / the stretch to the next pump |
gas[i] / cost[i] |
Net fuel at pump i |
d = gas[i] - cost[i] |
| Tank level while driving | running sum of d from the start |
| A bowler / an over / rest rule | a task letter / one time unit / cooldown n |
Every word, from zero
- Circular route (ring): after the last pump comes pump 0 again;
(s + k) % nwraps around. - Net gain
gas[i] - cost[i]: what the tank gains (or loses) from pumpito the next. - Total:
Σ (gas[i] - cost[i])over all pumps. - Prefix sum / running sum: the tank after each stretch, starting from some pump (episode 5).
- Cooldown
n: at leastntime units between two runs of the same task. - Idle: a time unit where the CPU runs nothing.
- Frequency / count: how many times a task letter appears.
max,numMax: the largest count, and how many letters have it.- Greedy: best-looking choice now, never undone (episode 59); it needs a proof.
- Bottleneck: the part that limits the whole schedule; here, the most frequent task.
Part 1: Gas Station (LeetCode 134)
Problem
| gas | cost | Answer |
|---|---|---|
[1, 2, 3, 4, 5] |
[3, 4, 5, 1, 2] |
3 |
[2, 3, 4] |
[3, 4, 3] |
-1 |
Constraints: 1 ≤ n ≤ 10^5, 0 ≤ gas[i], cost[i] ≤ 10^4. If a solution exists, it is unique.
Example 1 from pump 3: fill 4, burn 1 → 3; fill 5 → 8, burn 2 → 6; fill 1 → 7, burn 3 → 4; fill 2 → 6, burn 4 → 2; fill 3 → 5, burn 5 → 0. Back at pump 3 with 0 litres: it works.
Obvious idea: try every start
import java.util.*;
public class Main {
static int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int s = 0; s < n; s++) {
int tank = 0, k = 0;
for (; k < n; k++) {
int i = (s + k) % n;
tank += gas[i] - cost[i];
if (tank < 0) break;
}
if (k == n) return s;
}
return -1;
}
public static void main(String[] args) {
System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
}
}
3
-1
Correct. Now 1,00,000 pumps where every start fails near the end of the ring except the last pump (gas = cost = 1 everywhere, except cost[n - 2] = 2 and gas[n - 1] = 2):
start 99999, 14713 ms
About 15 seconds (it varies by machine); LeetCode allows about one second: Time Limit Exceeded. n starts × up to n stretches = O(n²) ≈ 500 crore steps.
The key insight: two facts
- Fact 1: if
total = Σ (gas - cost) < 0, no start works (the van burns more than all the fuel on the ring):-1. Iftotal ≥ 0, some start works (a classic result; the second fact finds it). - Fact 2: start at
s, and say the tank first goes negative at pumpi. Then no pump betweensandican be the start: we reached each of them with a tank of zero or more, so starting there with an empty tank is no better, and we'd still run dry byi. So jump the start toi + 1with an empty tank. - The start still standing after one pass is the answer (when
total ≥ 0).
By hand on example 1 (d = [-2, -2, -2, +3, +3]):
| i | d | tank | start |
|---|---|---|---|
| 0 | -2 | -2 → reset 0 | 1 |
| 1 | -2 | -2 → reset 0 | 2 |
| 2 | -2 | -2 → reset 0 | 3 |
| 3 | +3 | 3 | 3 |
| 4 | +3 | 6 | 3 |
total = 0 ≥ 0: answer 3.
Solution in Java
import java.util.*;
public class Main {
static int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int d = gas[i] - cost[i];
total += d;
tank += d;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total < 0 ? -1 : start;
}
public static void main(String[] args) {
System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
System.out.println(canCompleteCircuit(new int[]{5}, new int[]{4}));
System.out.println(canCompleteCircuit(new int[]{3, 1}, new int[]{1, 3}));
}
}
3
-1
0
0
The 1,00,000 pumps: start 99999, 4 ms.
The same Gas Station solution in C++
#include <bits/stdc++.h>
using namespace std;
// Gas Station (LeetCode 134): one pass; restart after any pump where the tank goes negative.
int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < (int)gas.size(); i++) {
int d = gas[i] - cost[i];
total += d;
tank += d;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total < 0 ? -1 : start;
}
int main() {
cout << canCompleteCircuit({1, 2, 3, 4, 5}, {3, 4, 5, 1, 2}) << "\n";
cout << canCompleteCircuit({2, 3, 4}, {3, 4, 3}) << "\n";
cout << canCompleteCircuit({5}, {4}) << "\n";
cout << canCompleteCircuit({3, 1}, {1, 3}) << "\n";
}
3
-1
0
0
The same Gas Station solution in Python
# Gas Station (LeetCode 134): total decides; restart at i + 1 with an empty tank when it goes negative.
def can_complete_circuit(gas, cost):
total = tank = start = 0
for i, (g, c) in enumerate(zip(gas, cost)):
total += g - c
tank += g - c
if tank < 0:
start, tank = i + 1, 0
return -1 if total < 0 else start
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(can_complete_circuit([2, 3, 4], [3, 4, 3]))
print(can_complete_circuit([5], [4]))
print(can_complete_circuit([3, 1], [1, 3]))
3
-1
0
0
Part 2: Task Scheduler (LeetCode 621)
Problem
tasks are letters A-Z, run in any order, one per time unit (or idle). Two runs of the same letter need at least n units between them. Return the fewest units.
| tasks | n | Answer | A schedule |
|---|---|---|---|
AAABBB |
2 | 8 |
A B idle A B idle A B |
AAABBB |
0 | 6 |
A A A B B B |
AAAAAABCDEFG |
2 | 16 |
A B C A D E A F G A idle idle A idle idle A |
Constraints: 1 ≤ tasks.length ≤ 10^4, 0 ≤ n ≤ 100.
Obvious idea: try every order
best tries every letter as the next task, waits until it's ready, and recurses; ready[c] is when letter c may run again.
import java.util.*;
public class Main {
static int leastInterval(char[] tasks, int n) {
int[] count = new int[26], ready = new int[26];
for (char t : tasks) count[t - 'A']++;
return best(count, ready, 0, tasks.length, n);
}
static int best(int[] count, int[] ready, int time, int left, int n) {
if (left == 0) return time;
int res = Integer.MAX_VALUE;
for (int c = 0; c < 26; c++) {
if (count[c] == 0) continue;
int start = Math.max(time, ready[c]), old = ready[c];
count[c]--;
ready[c] = start + n + 1;
res = Math.min(res, best(count, ready, start + 1, left - 1, n));
count[c]++;
ready[c] = old;
}
return res;
}
public static void main(String[] args) {
System.out.println(leastInterval("AAABBB".toCharArray(), 2));
System.out.println(leastInterval("AAABBB".toCharArray(), 0));
System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
}
}
8
6
16
On 20 tasks (AABBCC…JJ, ten letters twice each): Time Limit Exceeded: 20! / 2^10 ≈ 2,400 trillion orders.
A greedy trap: the first ready letter
Every unit, run the first ready letter in alphabetical order; idle if none is ready:
import java.util.*;
public class Main {
static int leastInterval(char[] tasks, int n) {
int[] count = new int[26], ready = new int[26];
for (char t : tasks) count[t - 'A']++;
int time = 0, left = tasks.length;
while (left > 0) {
for (int c = 0; c < 26; c++)
if (count[c] > 0 && ready[c] <= time) {
count[c]--;
ready[c] = time + n + 1;
left--;
break;
}
time++;
}
return time;
}
public static void main(String[] args) {
System.out.println(leastInterval("AAABBB".toCharArray(), 2));
System.out.println(leastInterval("AAABBB".toCharArray(), 0));
System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
System.out.println(leastInterval("ACC".toCharArray(), 1));
}
}
8
6
16
4
The examples pass, but ACC with n = 1 gives 4 (A C idle C); C A C takes 3. The rule ignores the bottleneck: the letter with the most copies left should go first (that rule, with a max-heap, is correct; see the mini project).
The key insight: the frame of the most frequent task
Let max = the largest count and numMax = how many letters have it.
- The
maxcopies of the bottleneck letter neednslots after each of the firstmax - 1copies:max - 1blocks ofn + 1slots, then a last row. - The last row holds every letter tied for
max:numMaxslots. frame = (max - 1) × (n + 1) + numMax. Other letters fill the gaps; leftover gaps are idle.- If there are more tasks than gaps, widen the blocks: the cooldown still holds and there's no idle at all, so the answer is just
tasks.length. - Answer =
max(tasks.length, frame).
AAABBB, n = 2:
A B idle | A B idle | A B (3 - 1) × 3 + 2 = 8
Solution in Java
import java.util.*;
public class Main {
static int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
for (char t : tasks) count[t - 'A']++;
int max = 0, numMax = 0;
for (int c : count) {
if (c > max) { max = c; numMax = 1; }
else if (c == max) numMax++;
}
return Math.max(tasks.length, (max - 1) * (n + 1) + numMax);
}
public static void main(String[] args) {
System.out.println(leastInterval("AAABBB".toCharArray(), 2));
System.out.println(leastInterval("AAABBB".toCharArray(), 0));
System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
System.out.println(leastInterval("ACC".toCharArray(), 1));
System.out.println(leastInterval("A".toCharArray(), 100));
}
}
8
6
16
3
1
The 20 tasks that timed out: 20 units, 0 ms; 10,000 random tasks with n = 100: 41613 units, 0 ms.
The same Task Scheduler solution in C++
#include <bits/stdc++.h>
using namespace std;
// Task Scheduler (LeetCode 621): answer = max(len, (max - 1) * (n + 1) + numMax).
int leastInterval(const string& tasks, int n) {
int count[26] = {0};
for (char t : tasks) count[t - 'A']++;
int mx = *max_element(count, count + 26);
int numMax = count_if(count, count + 26, [&](int c) { return c == mx; });
return max((int)tasks.size(), (mx - 1) * (n + 1) + numMax);
}
int main() {
cout << leastInterval("AAABBB", 2) << "\n";
cout << leastInterval("AAABBB", 0) << "\n";
cout << leastInterval("AAAAAABCDEFG", 2) << "\n";
cout << leastInterval("ACC", 1) << "\n";
cout << leastInterval("A", 100) << "\n";
}
8
6
16
3
1
The same Task Scheduler solution in Python
from collections import Counter
# Task Scheduler (LeetCode 621): the most frequent task builds the frame.
def least_interval(tasks, n):
counts = Counter(tasks).values()
mx = max(counts)
num_max = sum(1 for c in counts if c == mx)
return max(len(tasks), (mx - 1) * (n + 1) + num_max)
print(least_interval("AAABBB", 2))
print(least_interval("AAABBB", 0))
print(least_interval("AAAAAABCDEFG", 2))
print(least_interval("ACC", 1))
print(least_interval("A", 100))
8
6
16
3
1
Three real bugs
Bug 1: no total check (Gas Station)
return start;:
3
2
Example 2 should be -1: the last start standing only works if there's enough fuel in total.
Bug 2: moving the start but not emptying the tank
Without tank = 0;:
4
-1
Example 1 gives 4 instead of 3: the new start carried the old debt (-6).
Bug 3: the frame without max (Task Scheduler)
return (max - 1) * (n + 1) + numMax;:
8
4
16
AAABBB with n = 0 gives 4, but there are 6 tasks: you can't finish 6 tasks in 4 units.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Gas: every start | O(n²) | O(1) | 1 lakh pumps: ~15 s |
| Gas: one pass | O(n) | O(1) | 4 ms |
| Tasks: every order | exponential | O(26) + recursion | 20 tasks: Time Limit Exceeded |
| Tasks: first ready letter | O(answer · 26) | O(26) | wrong (4 instead of 3) |
| Tasks: max-heap simulation | O(answer · log 26) | O(26) | correct, prints the order |
| Tasks: frame formula | O(n) | O(26) | instant |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| No total check | 2 instead of -1 |
not enough fuel overall | total < 0 ? -1 : start |
| Start moved, tank kept | 4 instead of 3 |
carried the old debt | tank = 0 |
Restart at i instead of i + 1 |
wrong start | pump i itself made the tank negative |
start = i + 1 |
| First ready letter (alphabetical) | 4 instead of 3 |
ignores the bottleneck | most frequent first, or the frame |
| Frame only | 4 instead of 6 |
more tasks than slots | max(tasks.length, frame) |
Counting only one letter at max |
7 instead of 8 |
ties fill the last row | numMax |
Mini project: print an actual schedule
A max-heap of counts: every unit, run the ready letter with the most copies left (the bottleneck first); letters cooling down wait in a queue.
import java.util.*;
public class Main {
// Mini project: Task Scheduler simulation with a max-heap (most remaining first) and a cooldown queue.
static String schedule(String tasks, int n) {
int[] count = new int[26];
for (char t : tasks.toCharArray()) count[t - 'A']++;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? b[1] - a[1] : a[0] - b[0]);
for (int c = 0; c < 26; c++) if (count[c] > 0) heap.add(new int[]{c, count[c]});
Deque<int[]> cooling = new ArrayDeque<>(); // {letter, left, ready time}
StringBuilder out = new StringBuilder();
for (int time = 0; !heap.isEmpty() || !cooling.isEmpty(); time++) {
if (!cooling.isEmpty() && cooling.peek()[2] == time) {
int[] c = cooling.poll();
heap.add(new int[]{c[0], c[1]});
}
if (heap.isEmpty()) { out.append("_ "); continue; }
int[] t = heap.poll();
out.append((char) ('A' + t[0])).append(' ');
if (t[1] > 1) cooling.add(new int[]{t[0], t[1] - 1, time + n + 1});
}
return out.toString().trim();
}
public static void main(String[] args) {
System.out.println(schedule("AAABBB", 2));
System.out.println(schedule("ACC", 1));
System.out.println(schedule("AAAABBC", 2));
}
}
A B _ A B _ A B
C A C
A B C A B _ A _ _ A
(_ is an idle unit; the lengths 8, 3 and 10 match the formula.)
Practice
1. Reorganize String (LeetCode 767). Rearrange a string so no two adjacent letters are equal, or return "".
Solution
Task Scheduler with n = 1 and no idles allowed: possible exactly when max ≤ (len + 1) / 2. Place the most frequent letter at even indices first, then the rest.
from collections import Counter
# Reorganize String (LeetCode 767): fill even indices, then odd, most frequent letter first.
def reorganize_string(s):
counts = Counter(s)
if max(counts.values()) > (len(s) + 1) // 2:
return ""
res, i = [""] * len(s), 0
for ch, c in sorted(counts.items(), key=lambda x: -x[1]):
for _ in range(c):
res[i] = ch
i += 2
if i >= len(s):
i = 1
return "".join(res)
print(reorganize_string("aab"))
print(reorganize_string("aaab"))
print(reorganize_string("aaabbc"))
aba
ababac
(The middle line is the empty string: aaab can't be rearranged.)
2. Gas Station, but return the tank level at every pump for the answer's start. Hint: run the one-pass algorithm, then simulate once from start.
3. Candy (LeetCode 135). Children in a line with ratings; each gets at least one candy, and a child with a higher rating than a neighbour gets more than that neighbour. Fewest candies? Hint: two greedy passes, left-to-right then right-to-left, taking the max.
Solution
import java.util.*;
public class Main {
// Candy (LeetCode 135): left pass for the left neighbour, right pass for the right neighbour.
static int candy(int[] r) {
int n = r.length;
int[] c = new int[n];
Arrays.fill(c, 1);
for (int i = 1; i < n; i++) if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
for (int i = n - 2; i >= 0; i--) if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
int sum = 0;
for (int x : c) sum += x;
return sum;
}
public static void main(String[] args) {
System.out.println(candy(new int[]{1, 0, 2}));
System.out.println(candy(new int[]{1, 2, 2}));
System.out.println(candy(new int[]{1, 3, 4, 5, 2}));
}
}
5
4
11
Quick quiz
tasks = "AAAABBC", n = 2. What does leastInterval return? A) 10 B) 7 C) 9 D) 12
Answer
A) 10. max = 4 (A), numMax = 1: (4 - 1) × 3 + 1 = 10, bigger than the 7 tasks. A schedule: A B C A B _ A _ _ A.
Interview questions
- Why does
total ≥ 0guarantee a start exists? Start right after the point where the running sum ofdis lowest; from there, every prefix sum is ≥ 0. The one-pass algorithm finds exactly that point. - Why can we skip pumps
s..iafter failing ati? Each was reached with a non-negative tank; starting there empty can only be worse, and it would still fail byi. - Gas Station complexity?
O(n)time,O(1)space. - Explain the task-scheduler formula. The most frequent letter forces
max - 1blocks ofn + 1slots plus a last row of the tied letters; if other tasks overflow the gaps, there's no idle and the answer is the task count. - When is the answer exactly
tasks.length? When(max - 1)(n + 1) + numMax ≤ tasks.length: enough variety to fill every gap. - How would you print the schedule? Simulate with a max-heap of remaining counts and a queue of cooling letters.
- Why is "first ready letter" wrong? It may spend the slots on a rare letter and leave the frequent one to cool down with nothing else to run.
Glossary
| Term | Meaning |
|---|---|
| Circular route | After the last pump comes the first |
| Net gain | gas[i] - cost[i] |
| Total | The sum of all net gains |
| Running sum (tank) | Net gains added from the start pump |
Cooldown n |
Minimum gap between two runs of the same task |
| Idle | A time unit with no task |
Frequency, max, numMax |
A letter's count; the largest count; letters with that count |
| Frame | (max - 1) × (n + 1) + numMax slots |
| Bottleneck | The part that limits the whole schedule |
| Max-heap | Gives the largest item first (episode 43) |
Summary
- Gas Station:
total < 0→-1; otherwise, whenever the tank goes negative ati, restart ati + 1with an empty tank. One pass,O(n). - Task Scheduler: the most frequent task builds the frame; answer =
max(tasks.length, (max - 1)(n + 1) + numMax),O(n). - Trying every start is
O(n²); trying every order is exponential; "first ready letter" is a greedy trap. - Watch for: no total check, no tank reset, and forgetting the
maxwith the task count. - Next episode: Huffman coding and minimum cost to connect ropes: greedy with a heap.