#3015

Medium

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Count the Number of Houses at a Certain Distance I

Determine the number of house pairs at each street distance using graph traversal and breadth-first search efficiently.

Problem Statement

Given a city with n houses numbered 1 through n connected sequentially by n-1 streets, there is an additional street linking house x and house y. Your task is to calculate the number of pairs of houses (house1, house2) where the shortest path in streets between them equals k for all 1 <= k <= n.

For each integer k from 1 to n, count how many distinct house pairs have a minimum distance of k streets. Each pair is considered ordered, so (house1, house2) and (house2, house1) are separate if house1 != house2.

Examples

Example 1

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

Output: [6,0,0]

Let's look at each pair of houses:

For the pair (1, 2), we can go from house 1 to house 2 directly.
For the pair (2, 1), we can go from house 2 to house 1 directly.
For the pair (1, 3), we can go from house 1 to house 3 directly.
For the pair (3, 1), we can go from house 3 to house 1 directly.
For the pair (2, 3), we can go from house 2 to house 3 directly.
For the pair (3, 2), we can go from house 3 to house 2 directly.

Example 2

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

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

For each distance k the pairs are:

For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
For k == 3, the pairs are (1, 5), and (5, 1).
For k == 4 and k == 5, there are no pairs.

Example 3

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

Output: [6,4,2,0]

For each distance k the pairs are:

For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
For k == 3, the pairs are (1, 4), and (4, 1).
For k == 4, there are no pairs.

Constraints

2 <= n <= 100
1 <= x, y <= n

Solution Approach

Build the Graph

Model the houses as nodes and streets as edges. Include the sequential connections and the extra street between x and y. Represent this using an adjacency list for BFS efficiency.

Run BFS from Each House

For every house, perform a breadth-first search to compute distances to all other houses. This ensures that minimum street distances are captured even through the special extra connection.

Count Distances and Aggregate

Iterate over the BFS results for each house, incrementing the count for each distance k. Sum all contributions and construct the final array of counts indexed by distance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n^2) because BFS runs from each of n houses visiting up to n nodes. Space complexity is O(n^2) to store the adjacency list and distance counts, though it can be reduced with in-place counting during BFS.

What Interviewers Usually Probe

Focus on BFS to handle graph traversal efficiently.
Recognize the extra street creates shortcut paths impacting minimum distances.
Expect optimization by avoiding repeated full graph scans when counting pairs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count both (house1, house2) and (house2, house1) pairs.
Ignoring the impact of the extra street, which can reduce distances unexpectedly.
Using DFS or naive iteration which misses minimum distance optimization and increases time complexity.

Follow-up variants

Change the extra street to multiple extra streets creating a more complex graph.
Require counting unordered pairs instead of ordered pairs.
Increase n to larger values, emphasizing the need for BFS optimization or prefix sum aggregation.

FAQ

What is the main pattern to use for this problem?

The primary pattern is graph traversal using breadth-first search to compute distances between nodes.

Can this problem be solved with DFS?

DFS does not guarantee minimum distances efficiently in graphs with cycles or extra edges, so BFS is preferred.

How do we account for the extra street between x and y?

Include the extra street in the graph adjacency list before BFS; BFS will automatically capture shorter paths through it.

What is the expected output format?

An array where index k represents the number of ordered house pairs with minimum distance k streets.

Does GhostInterview provide stepwise BFS distance calculation?

Yes, GhostInterview guides you to start BFS from each house, compute all distances, and aggregate counts correctly.

terminal

Solution

Solution 1: Enumeration

We can enumerate each pair of points $(i, j)$. The shortest distance from $i$ to $j$ is $min(|i - j|, |i - x| + 1 + |j - y|, |i - y| + 1 + |j - x|)$. We add $2$ to the count of this distance because both $(i, j)$ and $(j, i)$ are valid pairs of points.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        x, y = x - 1, y - 1
        ans = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                a = j - i
                b = abs(i - x) + 1 + abs(j - y)
                c = abs(i - y) + 1 + abs(j - x)
                ans[min(a, b, c) - 1] += 2
        return ans

Continue Practicing

#3017 count the number of houses at a certain distance ii #3123 find edges in shortest paths #2858 minimum edge reversals so every node is reachable