Gas Station (Circular)

📋

Problem

Imagine you have a circular route with gas stations, each providing some fuel, and you want to find a starting station to complete the full circle without running out of gas.

Given two integer arrays gas and cost, both of length n, representing n gas stations arranged in a circle: gas[i] is the amount of gas at station i, and cost[i] is the amount of gas required to travel from station i to station (i+1) mod n. Return the starting gas station's index if you can travel around the circuit once in the clockwise direction without running out of gas; otherwise, return -1.

1 ≤ n ≤ 10^50 ≤ gas[i], cost[i] ≤ 10^4

Edge cases: All gas[i] equal to cost[i] → return any valid index (usually 0)Total gas less than total cost → return -1Single station with gas[i] >= cost[i] → return 0

</>

IDE

def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:public int canCompleteCircuit(int[] gas, int[] cost)int canCompleteCircuit(vector<int>& gas, vector<int>& cost)function canCompleteCircuit(gas, cost)

def canCompleteCircuit(gas, cost):
    # Write your solution here
    pass

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    // Write your solution here
    return -1;
}

function canCompleteCircuit(gas, cost) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when total gas >= total costNot checking total gas vs total cost before attempting to find start station.✅ Add a check: if sum(gas) < sum(cost): return -1 before main logic.

Wrong: Wrong start index due to greedy trapResetting start index incorrectly or too early when tank is positive.✅ Reset start index only when current tank < 0, then continue from next station.

Wrong: Crashes or invalid output on empty inputNo handling for n=0 case.✅ Add explicit check for empty arrays and return -1.

Wrong: Multiple start indices or partial sums returnedConfusing problem with unbounded knapsack or multiple starts allowed.✅ Return only one start index after full circuit check; do not accumulate partial starts.

Wrong: TLE on large inputsUsing brute force O(n^2) approach.✅ Implement O(n) greedy approach with total tank and current tank tracking.

✓

Test Cases

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

Consider tricky cases where greedy choices might fail; test carefully.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}

Expected3

⏱ Performance - must finish in 2000ms

Starting at station 3, you can complete the circuit: gas[3]=4, cost[3]=1, net +3; then station 4 net +3; stations 0,1,2 net negative but total gas is enough to cover cost.

💡 Consider the total gas and total cost to determine if a solution is possible.

💡 Use a greedy approach that resets the start index when the tank goes negative.

💡 Keep track of total tank and current tank; if current tank drops below zero, reset start to next station.

Why it failed: Returned wrong start index or -1 despite total gas >= total cost. Fix by resetting start index when tank < 0 and ensuring total gas check before returning.

✓ Correctly identifies the valid start station using the greedy reset approach.

t1_02basic

Input{"gas":[2,3,4],"cost":[3,4,3]}

Expected-1

⏱ Performance - must finish in 2000ms

Total gas = 9, total cost = 10, so no valid start station exists; return -1.

💡 Check if total gas is less than total cost to quickly return -1.

💡 If total gas is insufficient, no start station can complete the circuit.

💡 Sum gas and cost arrays first; if gas sum < cost sum, return -1 immediately.

Why it failed: Returned a start index despite total gas < total cost. Fix by adding a total gas vs total cost check before attempting greedy search.

✓ Correctly returns -1 when total gas is insufficient.

t2_01edge

Input{"gas":[],"cost":[]}

Expected-1

⏱ Performance - must finish in 2000ms

Empty input means no stations; cannot complete circuit, return -1.

💡 Consider the case when there are no gas stations.

💡 If n=0, no valid start exists; return -1.

💡 Add a check for empty input arrays and return -1 immediately.

Why it failed: Code crashes or returns invalid index on empty input. Fix by handling n=0 case explicitly returning -1.

✓ Handles empty input gracefully by returning -1.

t2_02edge

Input{"gas":[5],"cost":[4]}

Expected0

⏱ Performance - must finish in 2000ms

Single station with gas >= cost; starting at 0 completes circuit.

💡 Test the smallest non-empty input with one station.

💡 If gas[0] >= cost[0], return 0.

💡 Ensure single element arrays return 0 if gas >= cost, else -1.

Why it failed: Fails single station case by returning -1 or invalid index. Fix by checking single station condition explicitly.

✓ Correctly returns 0 for single station with sufficient gas.

t2_03edge

Input{"gas":[3,3,3],"cost":[3,3,3]}

Expected0

⏱ Performance - must finish in 2000ms

All gas equal to cost; any station is valid start, return 0 by convention.

💡 Check cases where gas[i] == cost[i] for all i.

💡 Total gas equals total cost, so a valid start exists.

💡 Return the first station (0) as valid start in this tie case.

Why it failed: Returns -1 despite total gas == total cost. Fix by allowing start at 0 when total gas equals total cost.

✓ Returns 0 correctly when gas equals cost at all stations.

t3_01corner

Input{"gas":[1,2,3,4,5],"cost":[3,4,5,1,1]}

Expected4

⏱ Performance - must finish in 2000ms

Greedy trap: total gas >= total cost but naive greedy picks wrong start; correct start is 4.

💡 Beware of greedy traps where local surplus misleads start choice.

💡 Check total gas vs total cost first, then reset start when tank < 0.

💡 Reset start index only when current tank drops below zero, not on every positive surplus.

Why it failed: Greedy trap: returns 3 or other wrong index by not resetting start correctly. Fix by resetting start only when tank < 0 and continuing search.

✓ Correctly handles greedy trap by resetting start properly.

t3_02corner

Input{"gas":[2,3,4,5,1],"cost":[3,4,3,2,2]}

Expected3

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded: must start at one station only, not multiple partial starts.

💡 Ensure you do not treat the problem as unbounded or multiple starts.

💡 Only one start index allowed; check tank reset logic carefully.

💡 Return the single valid start index after full check, not partial sums.

Why it failed: Returns multiple start indices or partial sums due to unbounded confusion. Fix by enforcing single start index and full circuit check.

✓ Correctly returns single valid start index respecting 0/1 constraint.

t3_03corner

Input{"gas":[0,0,10,0,0],"cost":[1,1,1,1,1]}

Expected2

⏱ Performance - must finish in 2000ms

Stations with zero gas but enough total gas; valid start exists at station 2.

💡 Check stations with zero gas but total gas sufficient.

💡 Start at station with surplus gas to cover deficits.

💡 Reset start when tank < 0; station 2 has enough gas to complete circuit.

Why it failed: Fails to find valid start due to zero gas stations. Fix by correctly resetting start and accumulating tank.

✓ Correctly identifies start station despite zero gas stations.

t4_01performance

Input{"gas":[10000,9999,10000,9998,10000,9997,10000,9996,10000,9995,10000,9994,10000,9993,10000,9992,10000,9991,10000,9990,10000,9989,10000,9988,10000,9987,10000,9986,10000,9985,10000,9984,10000,9983,10000,9982,10000,9981,10000,9980,10000,9979,10000,9978,10000,9977,10000,9976,10000,9975,10000,9974,10000,9973,10000,9972,10000,9971,10000,9970,10000,9969,10000,9968,10000,9967,10000,9966,10000,9965,10000,9964,10000,9963,10000,9962,10000,9961,10000,9960,10000,9959,10000,9958,10000,9957,10000,9956,10000,9955,10000,9954,10000,9953,10000,9952,10000,9951,10000,9950],"cost":[9999,10000,9998,10000,9997,10000,9996,10000,9995,10000,9994,10000,9993,10000,9992,10000,9991,10000,9990,10000,9989,10000,9988,10000,9987,10000,9986,10000,9985,10000,9984,10000,9983,10000,9982,10000,9981,10000,9980,10000,9979,10000,9978,10000,9977,10000,9976,10000,9975,10000,9974,10000,9973,10000,9972,10000,9971,10000,9970,10000,9969,10000,9968,10000,9967,10000,9966,10000,9965,10000,9964,10000,9963,10000,9962,10000,9961,10000,9960,10000,9959,10000,9958,10000,9957,10000,9956,10000,9955,10000,9954,10000,9953,10000,9952,10000,9951,10000,9950,10000]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) greedy solution must complete within 2 seconds; brute force O(n^2) will time out.

💡 Use O(n) greedy approach with total gas check and start reset.

💡 Avoid brute force O(n^2) which tries all start stations.

💡 Track total tank and current tank to find start in one pass.

Why it failed: TLE due to brute force O(n^2) approach. Fix by implementing O(n) greedy solution with tank reset.

✓ Efficient O(n) solution passes within time limit.

Practice

1. You are given an array representing daily stock prices. You want to maximize profit by making as many buy-sell transactions as you like, but you must sell before you buy again. Which algorithmic approach guarantees the optimal total profit?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming with memoization to explore all buy-sell pairs

C. Single pass to find the maximum single buy-sell pair profit

D. Divide and conquer to split the array and combine profits

Solution

1. Step 1: Understand the problem constraints

   The problem allows unlimited transactions but requires selling before buying again, so multiple buy-sell pairs can be combined.

2. Step 2: Identify the approach that captures all profitable segments

   Summing all positive consecutive day price differences captures every profitable transaction, ensuring maximum total profit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Summing positive differences matches the optimal profit for all test cases [OK]

Hint: Sum all positive consecutive price differences [OK]

Common Mistakes:

• Trying to find only one best buy-sell pair
• Using complex DP when greedy suffices
• Ignoring multiple transactions allowed

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. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Sort trains by arrival time

   Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

2. Step 2: Process trains up to index 1

   After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap size after second train is 1, max_platforms updated to 1 [OK]

Hint: Heap pops departures ≤ arrival before push [OK]

Common Mistakes:

• Not popping from heap before push
• Confusing max_platforms update timing
• Off-by-one in iteration

4. Suppose the Jump Game problem is modified so that you can jump backward as well as forward (i.e., jumps can be negative or positive). Which of the following approaches correctly determines if you can reach the last index from the first index under this new constraint?

hard

A. Use the original greedy approach tracking max reachable index, ignoring backward jumps

B. Use a breadth-first search (BFS) or graph traversal to explore all reachable indices including backward jumps

C. Use dynamic programming with memoization to recursively check reachability from each index

D. Sort the array and apply binary search to find reachable indices efficiently

Solution

1. Step 1: Understand the impact of backward jumps

   Backward jumps mean the problem is no longer monotonic; maxReach tracking fails as reachable indices can decrease.

2. Step 2: Identify suitable approach

   BFS or graph traversal explores all reachable indices in any direction, correctly handling negative jumps.

3. Step 3: Explain why other options fail

   Greedy fails due to backward jumps; DP recursion is possible but less efficient; sorting is irrelevant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS explores all reachable nodes regardless of jump direction [OK]

Hint: Backward jumps break greedy; BFS needed to explore all reachable indices [OK]

Common Mistakes:

• Trying to apply greedy despite backward jumps
• Assuming sorting helps reachability

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