1184. Distance Between Bus Stops #

Problem #

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

Problem Summary #

There are n stops on a circular bus route, numbered in order from 0 to n - 1. We know the distance between each pair of adjacent bus stops, where distance[i] represents the distance between the stop numbered i and the stop numbered (i + 1) % n. Buses on the circular route can travel both clockwise and counterclockwise. Return the shortest distance for a passenger from the starting point start to the destination destination.

Note:

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

Solution Approach #

• Given an array representing the distance between each pair of adjacent bus stops. The distances are given in the order of the array indices. The bus can travel clockwise or counterclockwise. Find the shortest travel distance.
• According to the problem statement, calculate the clockwise and counterclockwise travel distances respectively, compare the two distances, and the smaller value is the result.

Code #

package leetcode

func distanceBetweenBusStops(distance []int, start int, destination int) int {
	clockwiseDis, counterclockwiseDis, n := 0, 0, len(distance)
	for i := start; i != destination; i = (i + 1) % n {
		clockwiseDis += distance[i]
	}
	for i := destination; i != start; i = (i + 1) % n {
		counterclockwiseDis += distance[i]
	}
	if clockwiseDis < counterclockwiseDis {
		return clockwiseDis
	}
	return counterclockwiseDis
}