Bird
Raised Fist0

Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?

easy🧾 Code Trace Q12 of Q15
Greedy Algorithms - Gas Station (Circular)
Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?
def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    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

print(canCompleteCircuit(gas, cost))
A-1
B0
C1
D2
Step-by-Step Solution
Solution:
  1. Step 1: Compute net array

    net = [2-3, 3-4, 4-3] = [-1, -1, 1], sum(net) = -1 which is less than 0, so return -1 immediately.
  2. Step 2: Check sum(net)

    Since sum(net) < 0, no start station can complete the circuit.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sum of net gas is negative, no solution exists [OK]
Quick Trick: Sum net gas < 0 means no solution [OK]
Common Mistakes:
MISTAKES
  • Forgetting to check total gas vs cost
  • Misindexing prefix sums
  • Returning wrong start index
Trap Explanation:
PITFALL
  • Candidates may try to find a start index even when total gas is insufficient, leading to wrong answers.
Interviewer Note:
CONTEXT
  • Tests ability to trace prefix sums and understand early termination condition.
Master "Gas Station (Circular)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes