Watch 10 video solutions for Count the Number of Houses at a Certain Distance I, a medium level problem involving Breadth-First Search, Graph, Prefix Sum. This walkthrough by codestorywithMIK has 4,741 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= x, y <= nProblem Overview: You are given n houses arranged in a line with roads between consecutive houses, plus one additional road connecting houses x and y. For every distance d from 1 to n-1, count how many ordered pairs of houses have the shortest path distance exactly equal to d. The challenge is computing shortest paths efficiently for all house pairs.
Approach 1: Dynamic Programming / Distance Enumeration (O(n^2) time, O(n) space)
Treat the houses as a graph with edges between i and i+1, plus the shortcut edge (x, y). For every pair of houses (i, j), compute the shortest distance by comparing three possibilities: the direct linear path |i-j|, a path that goes through x → y, and another through y → x. The key insight is that the extra edge may shorten paths that cross the x-y region. Once the minimum distance is determined, increment the frequency for that distance. This behaves like a dynamic programming style enumeration because each pair reuses the same distance formulas. Time complexity is O(n^2) for evaluating all pairs, and space complexity is O(n) for the result array.
Approach 2: Recursive Approach with Memoization (O(n^2) time, O(n^2) space)
Model the houses as an adjacency list and recursively compute shortest distances between nodes while caching results. Each recursive call explores neighbors and returns the minimum distance to the target. Memoization prevents recomputing distances for the same pair of houses. This mirrors a depth‑first exploration of the breadth-first search distance logic but stores intermediate results in a cache table. After computing the shortest path for each pair, update the distance frequency array. The recursion with memoization ensures each pair is evaluated once, leading to O(n^2) time with O(n^2) space for the memo table.
Optimization Insight: Prefix Counting
Instead of running a full shortest-path search for every pair, the formula-based distance calculation effectively collapses the graph structure into simple arithmetic comparisons. Some implementations further optimize counting using prefix sum style accumulation to update distance ranges efficiently, avoiding repeated pair updates.
Recommended for interviews: The pairwise distance formula (DP-style enumeration) is typically expected. It shows that you recognized the graph structure but avoided expensive BFS from every node. Explaining the brute-force pair check first demonstrates understanding, while the optimized counting approach shows algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n^2) | O(n^2) | Useful for understanding shortest paths with cached recursion on small graphs |
| Dynamic Programming Distance Enumeration | O(n^2) | O(n) | Best practical solution when computing shortest distance for all pairs |
| BFS from Every Node | O(n^2) | O(n) | Conceptually simple graph approach for verifying shortest paths |