In questo articolo parleremo della soluzione per il quesito 134 Gas Station, presente sulla piattaforma Leetcode.

Perché utilizzare LeetCode?
Per chi non lo conoscesse, si tratta di una delle principali piattaforme web per prepararsi ad una “coding interview”. Un’azienda informatica che vuole assumere una persona e verificare le proprie skill, sottopone un problema simile a questo al candido. È fondamentale per quest’ultimo avere dimestichezza in queste situazioni, provando la capacità di trovare una soluzione. Può essere usato anche da chi dispone già di un lavoro, come meccanismo di allineamento in ambito data structure e algorithm.
Leetcode 134 Gas Station
Il problema originale si trova in questa pagina e ha una difficoltà media. Prima di parlare della soluzione, che verrà realizzata in Java, è necessario capire meglio il problema.
Si suppone di disporre di due array:
- gas[i]: identifica la disponibilità di rifornimento per quella stazione
- cost[i]: rappresenta il costo per compiere il tragitto dalla stazione i a quella successiva
L’unità di misura è indifferente ed è la stessa tra i due vettori. Si suppone che la macchina, all’instante iniziale abbia un valore 0 di riferimento. Il serbatoio è illimitato, per cui può fare sempre rifornimento alla stazione. Il compito del problema, è quello di stabilire il punto di partenza iniziale, che permetta di percorre un circuito in senso orario, potendo ritornare a quello iniziale. In caso affermativo, bisogna ritornare proprio tale indice/punto di partenza, in caso contrario si restituirà il valore -1. Si precisa che se la soluzione esiste, è unica.
Analisi iniziale
Come indicato in precedenza, il problema è di livello medio, dove la soluzione è esattamente semplice e/o intuitiva. Vi sono due osservazioni da fare, che si intuiscono dai test. Sottolineo che ancora prima di scrivere una linea di codice, è necessario prepararsi qualche test, in modo tale da scrivere del codice semplice da testare e da mantere.
Partendo dall’ultimo test, si capisce che se la somma dei costi, è strettamente minore della somma degli elementi nel vettore gas, non esiste una soluzione e pertanto bisogna restituire -1. Ora tocca capire meglio come gestire il caso positivo.
Di solito, per questa tipologia di problemi, esistono diverse soluzioni possibili. Questo perché la programmazione, non è una materia deterministica, pertanto due sviluppatori possono arrivare a soluzioni differenti. La piattaforma Leetcode, tiene traccia di due metriche importanti: performance e memory usage. Per la prima si intende la velocità con cui si riesce ad ottenere il risultato. La seconda si riferisce il consumo di memoria. L’obiettivo è quello di avere programmi veloci e che occupino poca memoria.
Ritornando alla risoluzione del problema, occorre sfruttare l’unicità della soluzione. Pertanto bisogna stabilire quando la variabile che tiene traccia della differenza tra gas[i] e cost[i] diventi positiva. Per risolvere il problema, si ritiene siano necessarie le seguenti variabili:
- indice di partenza ipotetico, che sarà poi il risultato in caso di positività
- la differenza tra cost[i] e gas[i] dall’azzeramento dell’indice di partenza
- la differenza tra cost[i] e gas[i] dall’inizio dell’iterazione
Soluzione Java LeetCode 134 Gas Station
Alla luce dell’analisi precedente, ecco, finalmente, la soluzione in Java del quesito:
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0;
int currRemaining = 0;
int totalRemaining = 0;
for (int i = 0; i < cost.length; i ++){
int remaining = gas[i] - cost[i];
// Check if the start index is fine
if (currRemaining < 0){
start = i;
currRemaining = remaining;
}
else{
currRemaining += remaining;
}
totalRemaining += remaining;
}
// Check if there is a solution
if (totalRemaining < 0)
return -1;
else
return start;
}
Conclusioni
In questo articolo, abbiamo visto come risolvere il problema numero 134 Gas Station presente sulla piattaforma LeetCode. Se hai qualche dubbio riguardo alla soluzione, scrivilo nei commenti!