brute-force O(n^2) java 1ms


  • 0
    Y
    public int canCompleteCircuit(int[] gas, int[] cost) {
               int n = gas.length;
               if (1 == n) return gas[0] >= cost[0] ? 0 : -1;
               
               int rest[] = new int[n];
               for (int i = 0; i < n; ++i) rest[i] = gas[i] - cost[i];
               
               // try the 1st positive number in positive sequence.
               for (int i = 0; i < n; ++i) {
                   if (rest[i] >= 0 && rest[(n + i - 1) % n] < 0) {               
                       // try i.
                       boolean failed = false;
                       int resource = 0;
                       for (int j = i; j < n || j % n < i; ++j) {
                           resource += rest[j % n];
                           if (resource < 0) {
                               failed = true;
                               break;
                           }
                       }
                       if (!failed) return i;
                   }
                   
               }
               
               return -1;
           } 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.