Valid Starting City

• Time : O(n)
• Space : O(1)

c++

int validStartingCity(vector<int> distances, vector<int> fuel, int mpg) {
    int n = distances.size(), res = 0;
    for(int i = 1, f = 0, dp = 0; i < n; i++) {
        f += mpg * fuel[i - 1] - distances[i - 1];
        if(dp > f) {
            dp = f, res = i;
        }
    }

    return res;
}