Count the Number of Houses at a Certain Distance II
HardPrompt
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.
Example 1:
Input: n = 3, x = 1, y = 3
Output: [6,0,0]
Explanation: 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]
Explanation: 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]
Explanation: 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 <= 1051 <= x, y <= n
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to model the city and streets as a graph. We can then find the shortest distance between all pairs of houses. A standard algorithm for finding shortest paths in an unweighted graph is Breadth-First Search (BFS).
Algorithm
- Create an adjacency list to represent the
nhouses and their connections. - Add edges for the streets:
(i, i+1)forifrom1ton-1, and the special street(x, y). - Initialize a result array
ansof sizenwith zeros. - For each house
start_nodefrom1ton: a. Perform a BFS starting fromstart_nodeto calculate the shortest distance to all other houses. b. Use a queue and adistancearray, initialized to infinity, for the BFS. Setdistance[start_node] = 0. c. While the queue is not empty, dequeue a houseu, and for each neighborv, ifvis unvisited, update its distance and enqueue it. d. After the BFS fromstart_nodeis complete, iterate through all housesjfrom1ton. e. Ifj != start_node, get the distanced = distance[j]. Incrementans[d-1]. - The problem asks for pairs, and our process counts ordered pairs
(i, j). The finalansarray contains the required counts. Returnans.
Walkthrough
First, we construct an explicit graph representation, like an adjacency list, from the input n, x, and y. The graph has n nodes. There are edges (i, i+1) for 1 <= i < n, and an additional edge (x, y).
Then, we iterate through each house i from 1 to n and use it as the starting source for a BFS traversal. The BFS algorithm will find the shortest distance from house i to all other houses j. During the BFS from i, we maintain a distance array. After the BFS is complete, for each house j, we increment the count for the calculated distance dist(i, j) in our result array.
Since the problem asks for the number of pairs (house1, house2), and distance is symmetric (dist(i, j) = dist(j, i)), running BFS from every node i and summing up the distances to all other nodes j correctly counts every ordered pair (i, j).
Complexity
Time
O(N^2). We run a BFS from each of the N nodes. Each BFS takes O(N + E) time, where E is the number of edges. In our graph, E is approximately N. So, one BFS is O(N). Repeating this for all N nodes gives a total time complexity of O(N^2). With N up to 10^5, this is not feasible.
Space
O(N). The adjacency list requires O(N) space. The distance array and queue used in each BFS also require O(N) space.
Trade-offs
Pros
Simple to understand and implement.
It's a general solution for any graph structure, not just this specific one.
Cons
Very inefficient for the given constraints. The time complexity is too high.
Solutions
Solution
class Solution {public long[] countOfPairs(int n, int x, int y) { --x; --y; if (x > y) { int temp = x; x = y; y = temp; } long[] diff = new long[n]; for (int i = 0; i < n; ++i) { diff[0] += 1 + 1; ++diff[Math.min(Math.abs(i - x), Math.abs(i - y) + 1)]; ++diff[Math.min(Math.abs(i - y), Math.abs(i - x) + 1)]; --diff[Math.min(Math.abs(i - 0), Math.abs(i - y) + 1 + Math.abs(x - 0))]; --diff[Math.min(Math.abs(i - (n - 1)), Math.abs(i - x) + 1 + Math.abs(y - (n - 1)))]; --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 0) / 2]; --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 1) / 2]; } for (int i = 0; i + 1 < n; ++i) { diff[i + 1] += diff[i]; } return diff; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.