Watch 6 video solutions for Count the Number of Houses at a Certain Distance II, a hard level problem involving Graph, Prefix Sum. This walkthrough by codingMohan has 2,162 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 <= 1051 <= x, y <= nProblem Overview: You are given n houses arranged in a straight line where each house connects to its neighbor. An additional road connects house x and y. For every distance k from 1 to n, compute how many ordered pairs of houses have shortest path distance exactly k.
Approach 1: Recursive Divide and Conquer (O(n) time, O(n) space)
This method splits the street into logical regions around the shortcut edge (x, y). Pairs entirely on the left side, entirely on the right side, or crossing the shortcut are counted separately. Instead of enumerating every pair, the algorithm recursively processes ranges of houses and aggregates how many pairs contribute to each distance bucket. A difference array or prefix-sum style accumulation records how many pairs add to distance ranges, then a final prefix pass converts these updates into the exact counts. The key insight is that distances through the shortcut create symmetric patterns that can be counted in bulk rather than individually. This reduces pair enumeration from O(n^2) to O(n).
Approach 2: Iterative Traversal with Prefix Sum (O(n) time, O(n) space)
An iterative scan treats the houses as positions on a line and computes how the shortcut modifies shortest paths. For a pair (i, j), the direct path distance is |i - j|, but the shortcut allows two alternate routes: i → x → y → j or i → y → x → j. The algorithm determines where the shortcut actually shortens the path and updates distance ranges accordingly. Instead of updating every pair, it pushes range increments into a difference array and later converts them using a prefix sum. This traversal effectively simulates contributions from each house segment while leveraging properties of the linear graph structure.
Recommended for interviews: The iterative prefix-sum counting approach is typically expected. Interviewers want to see that you avoid the naive O(n^2) pair comparison and instead exploit the structure of the line graph with one extra edge. Demonstrating how the shortcut changes distance ranges and converting range updates using a prefix sum shows strong algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Distance Check | O(n^2) | O(1) | Useful for understanding shortest path behavior before optimizing |
| Recursive Divide and Conquer | O(n) | O(n) | When breaking the problem into symmetric segments around the shortcut edge |
| Iterative Traversal with Prefix Sum | O(n) | O(n) | Preferred approach for interviews and competitive programming |