Count the Number of Houses at a Certain Distance II - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Recursive Divide and Conquer
This approach involves using the divide and conquer technique to break the problem into smaller subproblems, solve each recursively, and then combine the results to solve the larger problem. This is particularly helpful for problems that can be broken into independent parts.
This C program uses a recursive method 'divideAndConquer' that splits the array into two halves, recursively solves each half, and combines the results by summing. The base case occurs when the 'left' and 'right' indices converge, indicating a single element.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(log n) due to the recursion stack.
Approach 2: Iterative Traversal
An iterative method that solves the problem by systematically traversing the entire dataset and accumulating the results. This avoids recursion, thereby eliminating the associated overhead of the recursive call stack.
The C version uses a simple for loop to accumulate the sum of all elements, providing an iterative solution that's straightforward and avoids recursion.
Complexity
Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), using only a constant amount of additional space.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Divide and Conquer | Time Complexity: O(n), where n is the number of elements in the array. |
| Iterative Traversal | Time Complexity: O(n), where n is the number of elements. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3017. Count the Number of Houses at a Certain Distance II | Weekly Leetcode 381 • codingMohan • 2,186 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Count the Number of Houses at a Certain Distance II easy or hard?
Count the Number of Houses at a Certain Distance II Python/Java solution
How to solve Count the Number of Houses at a Certain Distance II in O(n)?
What is the best approach for Count the Number of Houses at a Certain Distance II?
Is Count the Number of Houses at a Certain Distance II asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Houses at a Certain Distance II?
What is the time complexity of Count the Number of Houses at a Certain Distance II?
Ready to solve this problem?
Practice Count the Number of Houses at a Certain Distance II with our built-in code editor and test cases.
Practice on FleetCode