Problem

You are given two integer arrays forward and backward, both of size n. You are also given another integer array queries.

There are n houses arranged in a circle. The houses are connected via roads in a special arrangement:

  • For all 0 <= i <= n - 2, house i is connected to house i + 1 via a road with length forward[i] meters. Additionally, house n - 1 is connected back to house 0 via a road with length forward[n - 1] meters, completing the circle.
  • For all 1 <= i <= n - 1, house i is connected to house i - 1 via a road with length backward[i] meters. Additionally, house 0 is connected back to house n - 1 via a road with length backward[0] meters, completing the circle.

You can walk at a pace of one meter per second. Starting from house 0, find the minimum time taken to visit each house in the order specified by queries.

Return the minimum total time taken to visit the houses.

Examples

Example 1

1
2
3
4
5

Input: forward = [1,4,4], backward = [4,1,2], queries = [1,2,0,2]
Output: 12
Explanation:
The path followed is 0(0) → 1(1) →​​​​​​​ 2(5) → 1(7) →​​​​​​​ 0(8) → 2(12).
Note: The notation used is node(total time), → represents forward road, and → represents backward road.

Example 2

1
2
3
4

Input: forward = [1,1,1,1], backward = [2,2,2,2], queries = [1,2,3,0]
Output: 4
Explanation:
The path travelled is 0 →​​​​​​​ 1 →​​​​​​​ 2 →​​​​​​​ 3 → 0. Each step is in the forward direction and requires 1 second.

Constraints

  • 2 <= n <= 105
  • n == forward.length == backward.length
  • 1 <= forward[i], backward[i] <= 105
  • 1 <= queries.length <= 105
  • 0 <= queries[i] < n
  • queries[i] != queries[i + 1]
  • queries[0] is not 0.

Solution

Method 1 - Prefix sums (direct distances clockwise and counterclockwise)

Intuition

From any current house pos to a target q there are two simple choices: walk around the circle following the forward edges (clockwise) or follow the backward edges (counterclockwise). Precompute prefix sums for forward and for backward (in the form used below) so we can compute either route in O(1) per query. Sum the minimum of the two for each query while updating pos.

Approach

  • Build prefixF where prefixF[i] is distance from house 0 to house i following forward edges (with prefixF[0]=0 and prefixF[n]=totalForward).
  • Build prefixB where prefixB[i] equals sum of backward[1]..backward[i] (with prefixB[0]=0). Also compute sumB = sum(backward).
  • To get clockwise distance from pos to q: if q < pos we wrap and add prefixF[n], so cw = (q < pos ? prefixF[n] : 0) + prefixF[q] - prefixF[pos].
  • To get counterclockwise distance following backward edges from pos to q: if q > pos we wrap and add sumB, so ccw = (q > pos ? sumB : 0) + prefixB[pos] - prefixB[q].
  • For each query pick min(cw, ccw) and accumulate to ans, then set pos = q.

Edge cases and checks:

  • Arrays lengths match by constraint; queries[i] != queries[i+1] and queries[0] != 0 per constraints but algorithm works regardless.
  • Use 64-bit arithmetic for sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public:
        long long minTotalTime(vector<int>& forward, vector<int>& backward, vector<int>& queries) {
            int n = forward.size();
            long long sumB = 0;
            vector<long long> prefixF(n + 1, 0);
            vector<long long> prefixB(n, 0);

            for (int i = 0; i < n; ++i) {
                prefixF[i + 1] = prefixF[i] + forward[i];
            }

            for (int i = 0; i < n; ++i) {
                sumB += backward[i];
                prefixB[i] = (i == 0 ? 0 : prefixB[i - 1]) + (i == 0 ? 0 : backward[i]);
            }

            long long ans = 0;
            int pos = 0;

            for (int q : queries) {
                long long cw = (q < pos ? prefixF[n] : 0) + prefixF[q] - prefixF[pos];
                long long ccw = (q > pos ? sumB : 0) + prefixB[pos] - prefixB[q];
                ans += min(cw, ccw);
                pos = q;
            }

            return ans;
        }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

package main

func minTotalTime(forward []int, backward []int, queries []int) int64 {
  n := len(forward)
  var sumB int64
  prefixF := make([]int64, n+1)
  prefixB := make([]int64, n)

  for i := 0; i < n; i++ {
    prefixF[i+1] = prefixF[i] + int64(forward[i])
  }

  for i := 0; i < n; i++ {
    sumB += int64(backward[i])
    if i == 0 {
      prefixB[i] = 0
    } else {
      prefixB[i] = prefixB[i-1] + int64(backward[i])
    }
  }

  var ans int64
  pos := 0

  for _, q := range queries {
    var cw int64
    if q < pos {
      cw = prefixF[n] + prefixF[q] - prefixF[pos]
    } else {
      cw = prefixF[q] - prefixF[pos]
    }

    var ccw int64
    if q > pos {
      ccw = sumB + prefixB[pos] - prefixB[q]
    } else {
      ccw = prefixB[pos] - prefixB[q]
    }

    if cw < ccw {
      ans += cw
    } else {
      ans += ccw
    }

    pos = q
  }

  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public long minTotalTime(int[] forward, int[] backward, int[] queries) {
        int n = forward.length;
        long sumB = 0;
        long[] prefixF = new long[n + 1];
        long[] prefixB = new long[n];

        for (int i = 0; i < n; i++) {
            prefixF[i + 1] = prefixF[i] + forward[i];
        }

        for (int i = 0; i < n; i++) {
            sumB += backward[i];
            prefixB[i] = (i == 0 ? 0 : prefixB[i - 1]) + (i == 0 ? 0 : backward[i]);
        }

        long ans = 0;
        int pos = 0;

        for (int q : queries) {
            long cw = (q < pos ? prefixF[n] : 0) + prefixF[q] - prefixF[pos];
            long ccw = (q > pos ? sumB : 0) + prefixB[pos] - prefixB[q];
            ans += Math.min(cw, ccw);
            pos = q;
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    fun minTotalTime(forward: IntArray, backward: IntArray, queries: IntArray): Long {
        val n = forward.size
        var sumB = 0L
        val prefixF = LongArray(n + 1)
        val prefixB = LongArray(n)

        for (i in 0 until n) {
            prefixF[i + 1] = prefixF[i] + forward[i]
        }

        for (i in 0 until n) {
            sumB += backward[i].toLong()
            prefixB[i] = if (i == 0) 0 else prefixB[i - 1] + backward[i]
        }

        var ans = 0L
        var pos = 0

        for (q in queries) {
            val cw = if (q < pos) prefixF[n] + prefixF[q] - prefixF[pos] else prefixF[q] - prefixF[pos]
            val ccw = if (q > pos) sumB + prefixB[pos] - prefixB[q] else prefixB[pos] - prefixB[q]
            ans += minOf(cw, ccw)
            pos = q
        }

        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
  def minTotalTime(self, forward: list[int], backward: list[int], queries: list[int]) -> int:
    n = len(forward)
    sum_b = 0
    prefixF = [0] * (n + 1)
    prefixB = [0] * n

    for i in range(n):
      prefixF[i + 1] = prefixF[i] + forward[i]

    for i in range(n):
      sum_b += backward[i]
      prefixB[i] = 0 if i == 0 else prefixB[i - 1] + backward[i]

    ans = 0
    pos = 0

    for q in queries:
      if q < pos:
        cw = prefixF[n] + prefixF[q] - prefixF[pos]
      else:
        cw = prefixF[q] - prefixF[pos]

      if q > pos:
        ccw = sum_b + prefixB[pos] - prefixB[q]
      else:
        ccw = prefixB[pos] - prefixB[q]

      ans += cw if cw < ccw else ccw
      pos = q

    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

pub struct Solution;
impl Solution {
    pub fn min_total_time(forward: Vec<i32>, backward: Vec<i32>, queries: Vec<i32>) -> i64 {
        let n = forward.len();
        let mut sum_b: i64 = 0;
        let mut prefix_f = vec![0i64; n + 1];
        let mut prefix_b = vec![0i64; n];

        for i in 0..n {
            prefix_f[i + 1] = prefix_f[i] + forward[i] as i64;
        }

        for i in 0..n {
            sum_b += backward[i] as i64;
            prefix_b[i] = if i == 0 { 0 } else { prefix_b[i - 1] + backward[i] as i64 };
        }

        let mut ans: i64 = 0;
        let mut pos: usize = 0;

        for q in queries {
            let q = q as usize;
            let cw = if q < pos { prefix_f[n] + prefix_f[q] - prefix_f[pos] } else { prefix_f[q] - prefix_f[pos] };
            let ccw = if q > pos { sum_b + prefix_b[pos] - prefix_b[q] } else { prefix_b[pos] - prefix_b[q] };
            ans += if cw < ccw { cw } else { ccw };
            pos = q;
        }

        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

export class Solution {
    minTotalTime(forward: number[], backward: number[], queries: number[]): number {
        const n = forward.length;
        let sumB = 0;
        const prefixF = new Array<number>(n + 1).fill(0);
        const prefixB = new Array<number>(n).fill(0);

        for (let i = 0; i < n; i++) {
            prefixF[i + 1] = prefixF[i] + forward[i];
        }

        for (let i = 0; i < n; i++) {
            sumB += backward[i];
            prefixB[i] = (i === 0 ? 0 : prefixB[i - 1] + backward[i]);
        }

        let ans = 0;
        let pos = 0;

        for (const q of queries) {
            const cw = q < pos ? prefixF[n] + prefixF[q] - prefixF[pos] : prefixF[q] - prefixF[pos];
            const ccw = q > pos ? sumB + prefixB[pos] - prefixB[q] : prefixB[pos] - prefixB[q];
            ans += Math.min(cw, ccw);
            pos = q;
        }

        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m) where n is the number of houses and m is queries.length — building prefix sums takes O(n) and each query is handled in O(1).
  • 🧺 Space complexity: O(n) for the prefix arrays.