Gas Station Problem — Golang solution | by George Onwuasoanya | Jul, 2022 | Medium

Start writinIn today’s post, we’ll be solving the following gas station problem with Golang.

Problem
Given a circular list of gas stations, where we can go from a station i to the station i + 1, and the last one goes back to the first one, find the index of the station from where we start to be able to traverse all the stations and go back to the initial one without running out of gas

Note:

1. we can only move forward
2. the gas tank starts empty
3. gas[i] represents the amount of gas at the station i
4. cost[i] represents the cost to go from station i to the next
5. the answer is guaranteed to be unique
6. if the desired station doesn’t exist, return -1

NB
In real world scenario, many long distance drivers evaluate this with the aid of experience however, 10x long distance drivers (i.e drivers with coding skills) can solve this issue on first trial.

Solution Description #1
This solution has a time complexity of O(n²) and it was the first method that came to my mind when I thought about this problem. In summary, it is a brute force technique that iterates through the array and treats every index as the starting point of transversal. A valid station is the station at index i from where we can start to be able to traverse all the stations and go back to the initial one (i-1) without running out of gas.

When we have a valid transversal from index i to n, where n is the length of the array; the cyclic condition on the gas stations entails that we consider the available gas from the transversal of i to n when we transverse from 0 to i. When we find the ith gas station that we can transverse (i to n) and (0 to i) without running out of gas, we return that i.

Code Solution:

func Execute() {

  gas := []int{1, 5, 3, 3, 5, 3, 1, 3, 4, 5}
  cost := []int{5, 2, 2, 8, 2, 4, 2, 5, 1, 2}
  tP := -1

  for i := 0; i < len(gas); i++ {
    if gas[i] > cost[i] {
      rtTrnv := traverseScore(0, gas[i:], cost[i:])
      if rtTrnv < 0 {
        continue
      }

      lftTrnv := traverseScore(rtTrnv, gas[:i], cost[:i])
      tSum := rtTrnv + lftTrnv
      if tSum >= 0 {
        tP = i
        break
      }
    }
  }
  fmt.Println(tP)
}

func traverseScore(sum int, gas, cost []int) int {
  for k := range gas {
    sum += (gas[k] - cost[k])
    if sum < 0 {
      break
    }
  }
  return sum
}

Solution Description #2
Experience is indeed a great teacher. When a long distance driver embarks on a road trip with the gas station problem, they’d make a mental note on the amount of gas to buy at different stations after several empty gas tank vehicle breakdowns.

We want to implement these mental notes in code for 10x drivers and this will improve the above coding solution and reduce the time complexity to O(n). The principal idea is to keep a record of the visited indexes that make up a bad path.

If we start from a station’s index and reach a negative amount at i, then all the stations between start and i inclusive are invalid. we need to save the previous sum that got us to the negative value so that we don’t have to recalculate the sum required to traverse that path repeatedly. The next traversal path of interest is from i+1

Code Solution:

func Execute2() {
  gas := []int{1, 5, 3, 3, 5, 3, 1, 3, 4, 5}
  cost := []int{5, 2, 2, 8, 2, 4, 2, 5, 1, 2}
  sum := 0
  tP := 0
  prevSum := 0
  for i := 0; i < len(gas); i++ {
    sum += (gas[i] - cost[i])
    if sum < 0 {
      tP = i + 1
      prevSum = sum
      sum = 0
    }
  }

  if tP == len(gas) || prevSum+sum < 0 {
    tP = -1
  }
  fmt.Println(tP)
}

Executed Solution:
In both cases, the valid index is 8. Feel free to manipulate the gas and cost arrays and play with the solutions.

If this teaching technique was useful, you can share the solution across your social media accounts for your friends' benefits. You can also share problems that you’d like me to solve. Visit https://omept.com to contact me.