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 where each element represents the maximum jump length from that position. You need to determine if you can reach the last index starting from the first index. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Dynamic Programming with bottom-up tabulation to check reachability for each index

B. Breadth-first search using a queue to explore reachable indices level by level

C. Depth-first search exploring all possible jump paths recursively without memoization

D. Greedy algorithm tracking the maximum reachable index while iterating through the array

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if the last index is reachable from the first index using jumps defined by array values.

2. Step 2: Identify optimal approach

   Greedy approach efficiently tracks the furthest reachable index in one pass, guaranteeing O(n) time complexity, unlike exhaustive search or DP which are slower.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy approach is linear and optimal for this problem [OK]

Hint: Greedy tracks max reachable index in one pass [OK]

Common Mistakes:

• Confusing DP with greedy, thinking recursion is needed

2. Consider the following code snippet for the Jump Game problem. What is the value of maxReach after the third iteration (i = 2) when the input is [2, 3, 1, 1, 4]?

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace maxReach updates for each iteration

   i=0: maxReach = max(0, 0+2) = 2 i=1: maxReach = max(2, 1+3) = 4 i=2: maxReach = max(4, 2+1) = 4

2. Step 2: Identify maxReach after i=2

   After third iteration (i=2), maxReach remains 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   maxReach does not decrease; it stays at 4 after i=2 [OK]

Hint: maxReach never decreases, track max(i+jump) [OK]

Common Mistakes:

• Off-by-one in iteration count
• Confusing maxReach update with i only

3. What is the time complexity of the optimal Task Scheduler algorithm using a max-heap for t total tasks and m unique tasks?

medium

A. O(t log m) because each task is pushed and popped from a heap of size up to m

B. O(t + m) because counting frequencies and scheduling are linear

C. O(m log t) because heap operations depend on total tasks

D. O(t * m) because each task may be compared with all unique tasks

Solution

1. Step 1: Analyze heap operations

   Heap size is at most m (unique tasks). Each task is pushed and popped at most once per execution.

2. Step 2: Calculate total operations

   For t tasks, each heap operation costs O(log m), so total is O(t log m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size depends on unique tasks, not total tasks [OK]

Hint: Heap operations scale with unique tasks, not total tasks [OK]

Common Mistakes:

• Confusing total tasks and unique tasks
• Assuming linear heap operations
• Ignoring log factor in heap push/pop

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