41-Circular-Tour.md

Circular Tour

Problem Link

Practice Problem

---

Pattern

• Queue
• Greedy

---

Approach

Track current balance and restart the start position whenever the balance becomes negative.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int circularTour(int[] petrol, int[] distance) {
        int start = 0, balance = 0, deficit = 0;
        for (int i = 0; i < petrol.length; i++) {
            balance += petrol[i] - distance[i];
            if (balance < 0) {
                start = i + 1;
                deficit += balance;
                balance = 0;
            }
        }
        return balance + deficit >= 0 ? start : -1;
    }
}