Count the Number of Houses at a Certain Distance I - 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 <= 1001 <= x, y <= n
Approach Overview
Problem 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 1: Dynamic Programming Approach
This approach involves using dynamic programming to solve the problem. The idea is to break down the problem into overlapping sub-problems and solve each one just once, storing the results for future reference to ensure that each sub-problem is solved only once.
This C code uses a simple dynamic programming technique. An array dp is employed to store the solutions of all sub-problems from 0 up to n. For example, if you wanted to optimize a task whose complexity depends on previous results, this approach would help you achieve that.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Recursive Approach with Memoization
This approach uses recursion combined with memoization to minimize the number of computations. By storing already computed values, recursive approaches can avoid redundant calculations and improve time efficiency.
This C code implements a recursive solution improved with memoization. The memo array stores results of already computed sub-problems to prevent re-calculation.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to stack space from recursion and the memoization array.
Approach 3: 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.
The time complexity is O(n^2), where n is the n given in the problem. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: |
| Recursive Approach with Memoization | Time Complexity: |
| Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count the Number of Houses at a Certain Distance I | Why Graph | Leetcode 3015 | Weekly Contest • codestorywithMIK • 5,268 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Number of Houses at a Certain Distance I easy or hard?
Count the Number of Houses at a Certain Distance I Python/Java solution
How to solve Count the Number of Houses at a Certain Distance I in O(n)?
What is the best approach for Count the Number of Houses at a Certain Distance I?
Is Count the Number of Houses at a Certain Distance I asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Houses at a Certain Distance I?
What is the time complexity of Count the Number of Houses at a Certain Distance I?
Ready to solve this problem?
Practice Count the Number of Houses at a Certain Distance I with our built-in code editor and test cases.
Practice on FleetCode