Stacks & QueuesProblem 30 of 38
Find the first circular tour that visits all Petrol Pumps
Problem Statement
There are N petrol pumps on a circular route. Each petrol pump has two values:
petrol[i]: Amount of petrol the pump providesdistance[i]: Distance to the next pump
Find the first petrol pump from which a truck can complete the entire circular tour. The truck has an unlimited capacity tank. Return -1 if no such starting point exists.
Example:
Input:
petrol[] = [4, 6, 7, 4]
distance[] = [6, 5, 3, 5]
Output: 1 (0-indexed)
Explanation: Starting from pump 1:
- At pump 1: petrol = 6, distance = 5, remaining = 1
- At pump 2: petrol = 1+7 = 8, distance = 3, remaining = 5
- At pump 3: petrol = 5+4 = 9, distance = 5, remaining = 4
- At pump 0: petrol = 4+4 = 8, distance = 6, remaining = 2
Successfully completed the tour!
Approach 1: Brute Force (Try Each Starting Point)
Intuition
Try starting from each petrol pump and simulate the journey. If we can complete the tour, return that starting index. If not, try the next pump.
Algorithm
- For each pump i from 0 to n-1:
- Try to complete the circular tour starting from pump i
- Track current petrol at each step
- If petrol goes negative, this start point doesn't work
- If we return to start with non-negative petrol, return i
- Return -1 if no valid starting point found
java
public class CircularTour {
public static int circularTourBruteForce(int[] petrol, int[] distance) {
int n = petrol.length;
for (int start = 0; start < n; start++) {
int currentPetrol = 0;
boolean canComplete = true;
for (int i = 0; i < n; i++) {
int index = (start + i) % n;
currentPetrol += petrol[index] - distance[index];
if (currentPetrol < 0) {
canComplete = false;
break;
}
}
if (canComplete) {
return start;
}
}
return -1;
}
public static void main(String[] args) {
int[] petrol = {4, 6, 7, 4};
int[] distance = {6, 5, 3, 5};
int result = circularTourBruteForce(petrol, distance);
System.out.println("Starting point: " + result); // 1
}
}Complexity Analysis
- Time Complexity: O(n^2) - for each of n starts, we check n pumps
- Space Complexity: O(1) - only using variables
Approach 2: Optimal (Single Pass with Queue Concept)
Intuition
Key insight: If we can't reach pump j from pump i, then any pump between i and j also can't be the starting point. This is because the petrol only gets worse (we had extra petrol from earlier pumps).
Use this insight to skip invalid starting points. Also, if total petrol >= total distance, a solution must exist.
Algorithm
- Track total balance (petrol - distance for all pumps)
- Track current balance starting from potential start
- If current balance goes negative:
- All pumps from start to current can't be start points
- Set next pump as new start, reset current balance
- If total balance >= 0, return the start; else return -1
java
public class CircularTour {
public static int circularTour(int[] petrol, int[] distance) {
int n = petrol.length;
int totalBalance = 0;
int currentBalance = 0;
int start = 0;
for (int i = 0; i < n; i++) {
int balance = petrol[i] - distance[i];
totalBalance += balance;
currentBalance += balance;
// If current balance is negative, this start point doesn't work
if (currentBalance < 0) {
start = i + 1; // Try starting from next pump
currentBalance = 0;
}
}
// If total petrol >= total distance, solution exists
return (totalBalance >= 0) ? start : -1;
}
public static void main(String[] args) {
int[] petrol = {4, 6, 7, 4};
int[] distance = {6, 5, 3, 5};
int result = circularTour(petrol, distance);
System.out.println("Starting point: " + result); // 1
// Test case 2: No solution
int[] petrol2 = {1, 2, 3};
int[] distance2 = {3, 4, 3};
int result2 = circularTour(petrol2, distance2);
System.out.println("Starting point: " + result2); // -1
}
}Complexity Analysis
- Time Complexity: O(n) - single pass through all pumps
- Space Complexity: O(1) - only using variables
Approach 3: Using Queue (Explicit Simulation)
Intuition
Use a queue to simulate adding pumps to the route. Keep adding pumps while the balance is non-negative. If balance becomes negative, remove pumps from the front until balance becomes non-negative or queue is empty.
Algorithm
- Start from pump 0, use a queue to track current route
- Add pumps to the end of queue
- If balance becomes negative, remove pumps from front
- Continue until all pumps are visited
- If queue contains all pumps at end, front of queue is answer
java
public class CircularTour {
public static int circularTourQueue(int[] petrol, int[] distance) {
int n = petrol.length;
int start = 0; // Current starting point
int end = 1; // Current ending point
int currentPetrol = petrol[0] - distance[0];
// While we haven't visited all pumps and haven't returned to start
while (start != end || currentPetrol < 0) {
// If petrol is negative, remove pumps from start
while (currentPetrol < 0 && start != end) {
currentPetrol -= petrol[start] - distance[start];
start = (start + 1) % n;
// If start becomes 0 again, no solution exists
if (start == 0) return -1;
}
// Add next pump to route
currentPetrol += petrol[end] - distance[end];
end = (end + 1) % n;
}
return start;
}
public static void main(String[] args) {
int[] petrol = {4, 6, 7, 4};
int[] distance = {6, 5, 3, 5};
int result = circularTourQueue(petrol, distance);
System.out.println("Starting point: " + result); // 1
}
}Complexity Analysis
- Time Complexity: O(n) - each element added and removed at most once
- Space Complexity: O(1) - using pointers instead of actual queue
Key Takeaways
- Key Insight: If you can't reach j from i, you can't reach j from any pump between i and j
- Total Check: If total petrol < total distance, no solution exists
- Greedy Works: The single-pass approach is both optimal and correct
- Circular Array: Use modulo for circular indexing
- This is LeetCode #134 - Gas Station
- Real-world use: Route planning, resource allocation in circular systems