Minimum Time to Visit All Houses - Practice Coding Problems

Minimum Time to Visit All Houses - 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.

Input & Output

Example 1 — Basic Circular Path

$ Input: forward = [3,1,2,4], backward = [5,2,1,3], queries = [1,2,0]

› Output: 11

💡 Note: Start at house 0. Go to house 1 (min(3,5)=3), then to house 2 (min(1,2)=1), then to house 0 (min(6,1)=1). Total: 3+1+1=5

Example 2 — Same House Query

$ Input: forward = [2,3], backward = [1,4], queries = [0,1,0]

› Output: 3

💡 Note: Start at house 0. Stay at house 0 (0 time), go to house 1 (min(2,4)=2), return to house 0 (min(3,1)=1). Total: 0+2+1=3

Example 3 — Larger Circle

$ Input: forward = [1,2,3,4,5], backward = [6,5,4,3,2], queries = [2,4,1]

› Output: 8

💡 Note: Start at house 0. Go to house 2 (min(3,9)=3), then to house 4 (min(9,6)=6), then to house 1 (min(9,1)=1). Total: 3+6+1=10

Constraints

1 ≤ forward.length = backward.length = n ≤ 1000
1 ≤ forward[i], backward[i] ≤ 1000
1 ≤ queries.length ≤ 1000
0 ≤ queries[i] < n

Visualization

Tap to expand

Understanding the Visualization

Input

Circular houses with forward/backward road lengths and query sequence

Process

For each query, calculate minimum time between clockwise and counterclockwise paths

Output

Total minimum time to visit all houses in query order

Key Takeaway

🎯 Key Insight: Use prefix sums to calculate any segment distance in O(1) time, avoiding redundant path calculations in the circular arrangement

Asked in

G Google 15 a Amazon 12 M Meta 8

The key insight is to precompute prefix sums for both forward and backward directions, allowing O(1) distance calculation between any two houses. The optimal approach uses prefix sums to avoid redundant path calculations. Time: O(n + q), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n)	O(1)	For each query, calculate clockwise and counterclockwise distances by summing individual road lengths
Prefix Sum Optimization	O(n + q)	O(n)	Precompute cumulative distances in both directions to calculate any path in O(1) time

Brute Force — Algorithm Steps

Step 1: For each query pair, calculate clockwise distance by summing forward array segments
Step 2: Calculate counterclockwise distance by summing backward array segments
Step 3: Take minimum of both distances and add to total time

Visualization

Tap to expand

Step-by-Step Walkthrough

Current Position

Start at house 0

Calculate Paths

Sum forward/backward arrays for both directions

Choose Minimum

Take the shorter path time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* forward, int* backward, int* queries, int n, int q) {
    int totalTime = 0;
    int currentPos = 0;
    
    for (int i = 0; i < q; i++) {
        int target = queries[i];
        if (currentPos == target) {
            continue;
        }
        
        // Calculate clockwise distance
        int clockwise = 0;
        int pos = currentPos;
        while (pos != target) {
            clockwise += forward[pos];
            pos = (pos + 1) % n;
        }
        
        // Calculate counterclockwise distance
        int counterclockwise = 0;
        pos = currentPos;
        while (pos != target) {
            counterclockwise += backward[pos];
            pos = (pos - 1 + n) % n;
        }
        
        // Take minimum distance
        int minTime = (clockwise < counterclockwise) ? clockwise : counterclockwise;
        totalTime += minTime;
        currentPos = target;
    }
    
    return totalTime;
}

int main() {
    char line[10000];
    int forward[1000], backward[1000], queries[1000];
    int n = 0, q = 0;
    
    // Parse forward array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 1000) {
        if (token[0] != '\n' && token[0] != ' ' && token[0] != ']') {
            forward[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse backward array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    int b = 0;
    while (token != NULL && b < n) {
        if (token[0] != '\n' && token[0] != ' ' && token[0] != ']') {
            backward[b++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse queries array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL && q < 1000) {
        if (token[0] != '\n' && token[0] != ' ' && token[0] != ']') {
            queries[q++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(forward, backward, queries, n, q);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

For each query (q queries), we may need to traverse up to n houses

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current position and distances

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler