Sponsored
Sponsored
This approach leverages the greedy paradigm. The main idea is to iterate over the stations while keeping track of the total gas and total cost. Additionally, we maintain a running sum (which is the cumulative balance of gas at each station) and a start index. If the running sum ever becomes negative, it implies that the current segment of the journey is infeasible. Thus, we reset the running sum and choose the next station as the candidate for the starting point. Finally, if the total gas is greater than or equal to the total cost, the last chosen candidate is the valid starting point.
Time Complexity: O(n), where n is the number of stations.
Space Complexity: O(1), as extra space used is constant.
1#include <stdio.h>
2
3int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
4 int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;
5 for (int i = 0; i < gasSize; i++) {
6 totalGas += gas[i];
7 totalCost += cost[i];
8 currentGas += gas[i] - cost[i];
9 if (currentGas < 0) {
10 start = i + 1;
11 currentGas = 0;
12 }
13 }
14 return totalGas >= totalCost ? start : -1;
15}
16
17int main() {
18 int gas[] = {1, 2, 3, 4, 5};
19 int cost[] = {3, 4, 5, 1, 2};
20 int result = canCompleteCircuit(gas, 5, cost, 5);
21 printf("%d\n", result);
22 return 0;
23}
24The function canCompleteCircuit iterates over the gas stations. It calculates the totalGas and totalCost along the way. While computing the running balance currentGas, if it becomes negative, the potential start index is updated to the next station. After the loop, if totalGas is greater than or equal to totalCost, it returns the last updated starting index; otherwise, it returns -1.
This approach attempts to simulate the journey starting from each station. For each potential start, check if the car can complete the circuit using the available gas at each station. While this approach may be easier to understand, it is inefficient because it checks each station iteratively, leading to potentially high computational costs for longer arrays. It is not recommended for larger datasets but can be useful for understanding how the journey works preliminarily.
Time Complexity: O(n^2) due to double iteration.
Space Complexity: O(1) as no extra space is utilized.
1
class Program {
public static int CanCompleteCircuit(int[] gas, int[] cost) {
int n = gas.Length;
for (int start = 0; start < n; start++) {
int currentGas = 0;
int count = 0;
while (count < n) {
int index = (start + count) % n;
currentGas += gas[index] - cost[index];
if (currentGas < 0) break;
count++;
}
if (count == n) return start;
}
return -1;
}
static void Main(string[] args) {
int[] gas = {1, 2, 3, 4, 5};
int[] cost = {3, 4, 5, 1, 2};
int result = CanCompleteCircuit(gas, cost);
Console.WriteLine(result);
}
}
C# also uses a brute force simulation to iterate over each start index, accumulating the net gas. Immediate stops occur during looping if gas is insufficient, leading the function to attempt subsequent starts.