[AlgoExpert] Valid Starting City

Valid Starting City

  • Time : O(n)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
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;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/09/PS/AlgoExpert/valid-starting-city/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.