Count the Number of Houses at a Certain Distance II

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

Understanding the Visualization

Input

Houses 1-n with linear connections plus shortcut x↔y

Process

Calculate shortest distance for each pair of houses

Output

Array where result[k] = number of pairs at distance k

Key Takeaway

🎯 Key Insight: The shortcut creates alternative paths - count pairs by their minimum distance using either linear or shortcut route

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

Approach	Time	Space	Notes
✓ Brute Force BFS	O(n²)	O(n)	Run BFS from each house to find all distances
Mathematical Formula	O(n²)	O(1)	Use closed-form formulas to count distances without BFS

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler