Count the Number of Houses at a Certain Distance I
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the city as a graph and uses the Floyd-Warshall algorithm to find the shortest distance between all pairs of houses. It's a standard algorithm for finding all-pairs shortest paths but is less efficient for this problem's specific graph structure compared to other methods.
Algorithm
- Initialize an
(n+1)x(n+1)distance matrixdistwith infinity, anddist[i][i] = 0for alli. - Populatedistwith initial street lengths:dist[i][i+1] = 1,dist[i+1][i] = 1foriin1..n-1. - Setdist[x][y] = 1anddist[y][x] = 1ifx != y. - Run the Floyd-Warshall algorithm by iterating through all intermediate nodeskfrom 1 tonand updatingdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). - Initialize a result arrayansof sizenwith zeros. - Iterate through all pairs(i, j)with1 <= i < j <= n. - For each pair, get the distanced = dist[i][j]and incrementans[d-1]by 2. - Returnans.
Walkthrough
First, we represent the houses and streets as a graph where houses are vertices from 1 to n. We use an adjacency matrix, let's call it dist, to store the shortest distances between any two houses. The matrix is initialized with a large value for non-adjacent houses and 0 for the distance from a house to itself. We then populate the matrix with the direct street connections: dist[i][i+1] and dist[i+1][i] are set to 1 for all 1 <= i < n, and dist[x][y] and dist[y][x] are set to 1 for the special street. After setting up the initial distances, we apply the Floyd-Warshall algorithm. This algorithm systematically improves the distance estimates by considering every possible house as an intermediate stop in the path between any two houses. After the algorithm finishes, the dist matrix contains the shortest path lengths for all pairs. Finally, we iterate through all unique pairs of houses (i, j) with i < j, retrieve their shortest distance d = dist[i][j], and increment the count for distance d by 2 (for pairs (i, j) and (j, i)). The counts are stored in a result array of size n. java class Solution { public int[] countOfPairs(int n, int x, int y) { int[][] dist = new int[n + 1][n + 1]; int INF = n + 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { dist[i][j] = 0; } else { dist[i][j] = INF; } } } for (int i = 1; i < n; i++) { dist[i][i + 1] = 1; dist[i + 1][i] = 1; } if (x != y) { dist[x][y] = 1; dist[y][x] = 1; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } int[] result = new int[n]; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { int d = dist[i][j]; if (d > 0 && d <= n) { result[d - 1] += 2; } } } return result; } }
Complexity
Time
O(n^3), due to the three nested loops in the Floyd-Warshall algorithm.
Space
O(n^2), for storing the adjacency matrix.
Trade-offs
Pros
Conceptually straightforward for all-pairs shortest path problems.
Guaranteed to work on any graph, including those with negative edge weights (though not relevant here).
Cons
High time complexity of O(n^3), which is inefficient for sparse graphs or when
nis large.High space complexity of O(n^2).
Solutions
Solution
class Solution {public int[] countOfPairs(int n, int x, int y) { int[] ans = new int[n]; x--; y--; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int a = j - i; int b = Math.abs(i - x) + 1 + Math.abs(j - y); int c = Math.abs(i - y) + 1 + Math.abs(j - x); ans[Math.min(a, Math.min(b, c)) - 1] += 2; } } return ans; }}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.