Count the Number of Houses at a Certain Distance II - Problem

You are given three positive integers n, x, and y. In a city, there exist houses numbered 1 to n connected by n streets.

There is a street connecting the house numbered i with the house numbered i + 1 for all 1 <= i <= n - 1. An additional street connects the house numbered x with the house numbered y.

For each k, such that 1 <= k <= n, you need to find the number of pairs of houses (house1, house2) such that the minimum number of streets that need to be traveled to reach house2 from house1 is k.

Return a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k.

Note that x and y can be equal.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, x = 2, y = 4

› Output: [10,8,2,0,0]

💡 Note: With shortcut between houses 2 and 4, some pairs use linear path while others use the shortcut. Distance 1: 10 pairs, Distance 2: 8 pairs, Distance 3: 2 pairs.

Example 2 — No Shortcut Effect

$ Input: n = 4, x = 1, y = 1

› Output: [6,4,2,0]

💡 Note: Since x = y, there's no actual shortcut. All distances are linear: 1→6 pairs, 2→4 pairs, 3→2 pairs.

Example 3 — Adjacent Shortcut

$ Input: n = 3, x = 1, y = 2

› Output: [4,2,0]

💡 Note: Shortcut between adjacent houses doesn't change distances. Distance 1: 4 pairs, Distance 2: 2 pairs.

Constraints

3 ≤ n ≤ 10⁵
1 ≤ x, y ≤ n

Visualization

Tap to expand

Asked in

G Google 15 f Meta 12 a Amazon 10

The key insight is that each pair of houses has two possible paths: the direct linear path and the path using the shortcut edge. We need to count pairs by their shortest distance. The optimal approach uses mathematical formulas to avoid graph traversal. Time: O(n²), Space: O(1).

Common Approaches

✓ Brute Force BFS

⏱️ Time: O(n²) Space: O(n)

For each house, run BFS to compute shortest distances to all other houses, then count pairs by distance. This approach guarantees correctness by explicitly computing all shortest paths.

Mathematical Formula

⏱️ Time: O(n²) Space: O(1)

Instead of running BFS, derive mathematical formulas for counting pairs at each distance. The shortcut edge creates two paths between some houses - use the shorter one.

Brute Force BFS — Algorithm Steps

For each house i from 1 to n
Run BFS to find shortest distance to all other houses
Count pairs for each distance k

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Build graph with linear connections and shortcut

BFS

Run BFS from each house to find all distances

Count

Count pairs for each distance value

Code -

solution.c — C

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

int* solution(int n, int x, int y) {
    int* result = (int*)calloc(n, sizeof(int));
    
    // Build adjacency list using arrays
    int** adj = (int**)malloc((n + 1) * sizeof(int*));
    int* adjSize = (int*)calloc(n + 1, sizeof(int));
    
    for (int i = 0; i <= n; i++) {
        adj[i] = (int*)malloc(4 * sizeof(int)); // max 4 neighbors
    }
    
    for (int i = 1; i < n; i++) {
        adj[i][adjSize[i]++] = i + 1;
        adj[i + 1][adjSize[i + 1]++] = i;
    }
    if (x != y) {
        adj[x][adjSize[x]++] = y;
        adj[y][adjSize[y]++] = x;
    }
    
    // For each starting house
    for (int start = 1; start <= n; start++) {
        int* dist = (int*)malloc((n + 1) * sizeof(int));
        for (int i = 0; i <= n; i++) dist[i] = -1;
        dist[start] = 0;
        
        int* queue = (int*)malloc(n * sizeof(int));
        int front = 0, rear = 0;
        queue[rear++] = start;
        
        while (front < rear) {
            int node = queue[front++];
            for (int i = 0; i < adjSize[node]; i++) {
                int neighbor = adj[node][i];
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    queue[rear++] = neighbor;
                }
            }
        }
        
        // Count distances from this start
        for (int end = 1; end <= n; end++) {
            if (start != end) {
                int d = dist[end];
                if (d >= 1 && d <= n) {
                    result[d - 1]++;
                }
            }
        }
        
        free(dist);
        free(queue);
    }
    
    // Cleanup
    for (int i = 0; i <= n; i++) {
        free(adj[i]);
    }
    free(adj);
    free(adjSize);
    
    return result;
}

int main() {
    int n, x, y;
    scanf("%d", &n);
    scanf("%d", &x);
    scanf("%d", &y);
    
    int* result = solution(n, x, y);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Run BFS from each of n houses, each BFS visits O(n) nodes

⚠ Quadratic Growth

Space Complexity

O(n)

BFS queue and visited array for each traversal

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~25 min Avg. Time

245 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

Count the Number of Houses at a Certain Distance II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler