FastPrep
Problem · Array

Circular Route Query Distance

Learn this problem
● EasyAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A circular route has n stops numbered from 0 to n - 1. The array distances has length n, where distances[i] is the distance from stop i to stop (i + 1) % n.

You are given several route queries. Each query [start, end] asks for the shorter of the two possible distances between those stops on the circle. Return the sum of the shortest distances over all queries.

Function

minCircularQueryDistance(distances: int[], queries: int[][]) → int

Examples

Example 1

distances = [1,2,3,4]queries = [[0,1],[1,3],[3,0]]return = 10

The shortest distances are 1, 5, and 4, so the total is 10.

Example 2

distances = [7,10,1,12]queries = [[0,2],[2,1]]return = 23

For 0 to 2, the counter-clockwise route is shorter with distance 13. For 2 to 1, the opposite direction has distance 10.

Constraints

Stops are zero-indexed. Each query contains two valid stop indices. No numeric limits were provided in the source; an efficient solution should precompute prefix sums around the circle.

More Amazon problems

drafts saved locally
public int minCircularQueryDistance(int[] distances, int[][] queries) {
    // write your code here
}
distances[1,2,3,4]
queries[[0,1],[1,3],[3,0]]
expected10
checking account