Leetcode 134 Solution

This article provides solution to leetcode question 134 (gas-station).
Categories:
Tags:
Access this page by simply typing in "lcs 134" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/gas-station

Solution

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> a(gas.size());
        
        for (int i = 0; i < gas.size(); i++)
            a[i] = gas[i] - cost[i];
        
        int sum = 0;
        for (int i = 0; i < a.size(); i++)
            sum += a[i];
        
        if (sum < 0)
            return -1;
            
        int min_val = 0;
        int min_index = 0;
        int s = 0;
        
        for (int i = 0; i < a.size(); i++)
        {
            s += a[i];

            if (min_val > s)
            {
                min_val = s;
                min_index = (i + 1) % a.size();
            }
        }
        
        return min_index;
    }
};