Truck Tour Hackerrank Solution

Understanding the Truck Tour Problem

The HackerRank Truck Tour problem asks you to find a starting petrol pump in a circular arrangement such that a truck can complete one full round. Each pump gives you a certain amount of petrol and charges you a certain distance to reach the next pump. The truck starts with zero fuel and the question is whether you can find a valid starting point. This looks like it might need complex graph traversal or brute-force checking every possible start, but there is a clean O(n) greedy solution that most experienced programmers land on after struggling with the naive approach first. I spent about twenty minutes once trying to implement a sliding window with a deque before realizing the problem had a much simpler structure.

Truck Tour Hackerrank Solution

The core insight is this: if you start at pump A and run out of fuel before reaching pump B, then every pump between A and B is also an invalid starting point. There is no scenario where starting later in that range somehow gives you enough surplus to make up for the deficit you already encountered. This lets you skip entire sections of the array in a single pass. Here is how the algorithm works in practice: Initialize a variable called start_pos to 0 and another called surrplus to 0. Loop through each pump from left to right. At each pump i, add the net fuel (petrol[i] - distance[i]) to surrplus. If surrplus ever drops below zero, that means the current start_pos cannot reach pump i. Reset surrplus back to 0 and move start_pos forward to i + 1. Continue until the loop finishes.

After the single pass, check whether the total sum of all net values across the entire array is non-negative. If it is, then start_pos is your answer. If the total is negative, no valid starting point exists and you return -1. Here is a Python implementation that handles this cleanly:

def truck_tour(petrol, distance):
    start_pos = 0
    surplus = 0
    total = 0
    for i in range(len(petrol)):
        net = petrol[i] - distance[i]
        surplus += net
        total += net
        if surplus < 0:
            start_pos = i + 1
            surplus = 0
    return start_pos if total >= 0 else -1

The time complexity is O(n) because you visit each pump exactly once. The space complexity is O(1) since you only maintain a handful of integer variables regardless of input size. I ran into an edge case once on a practice run where the test included a pump with zero petrol and a distance of zero to the next pump. My initial implementation had a bug where it returned the wrong start position because the surplus comparison was slightly off. The fix was straightforward: make sure you are comparing surplus strictly less than zero, not less than or equal to zero. That subtle difference matters when a pump contributes exactly zero net fuel. Another thing to watch out for is integer overflow in languages like Java or C++. If the petrol and distance values are large and the array is long, the total sum can exceed the 32-bit integer range. Use 64-bit integers or the language equivalent to avoid silent failures on larger test cases.

Why the Greedy Approach Works

The proof is fairly short. Suppose pump A is your candidate start and you fail at pump B with a negative surplus. For any pump C between A and B to be a valid start, it would need to carry enough cumulative surplus from C back through B to cover whatever deficit existed from A to B. But since the deficit from A to B is the sum of all net values in that range, and C is inside that range, removing the segment from A to C can only reduce or maintain the total deficit. It cannot create new surplus. So C is also invalid. This means skipping ahead is always safe. You never miss a valid solution by jumping past the failed segment. The algorithm also handles the circular nature without explicitly duplicating the array. Because you only do a single forward pass and then verify the global total, the circular constraint is satisfied implicitly. If the total net fuel is non-negative, a valid tour must exist, and the greedy scan finds the earliest valid starting index.

One limitation worth noting: this approach finds the first valid starting index, not all of them. If the problem asks for every possible starting pump, you would need additional logic. The HackerRank version typically only asks for one valid answer or -1 if none exists. If you are implementing this in a different language, the logic stays identical. Just be careful with array indexing conventions and make sure your loop bounds match the problem's expectations. Some variants use 1-based indexing in their test cases even though the input is given as a standard array. The solution is compact, efficient, and easy to verify. Once you internalize the greedy skip logic, you can write it from memory in under five minutes during a coding interview. That alone makes it one of the more useful patterns to have in your toolkit.