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).
A more efficient approach is to calculate the shortest paths from each house to all other houses individually. Since all streets have a length of 1 (unweighted graph), we can use Breadth-First Search (BFS) from each house. This is more efficient than Floyd-Warshall for this problem.
Algorithm
- Build an adjacency list
adjfor the graph. - Add edges for the linear streets(i, i+1)and the special street(x, y). - Initialize a result arrayansof sizento all zeros. - For each housestartNodefrom 1 ton: - Perform a BFS starting fromstartNode. - Use a queue for the traversal and adistarray to store distances fromstartNode. - When a new nodevis reached fromu, setdist[v] = dist[u] + 1and incrementans[dist[v]-1]by 1. - Returnans.
Walkthrough
We first model the city's streets as a graph using an adjacency list, which is space-efficient for sparse graphs. Then, for each house i from 1 to n, we perform a BFS starting from i to find the shortest distance to all other houses. A BFS explores the graph layer by layer, which naturally finds the shortest paths in an unweighted graph. During the BFS starting from startNode, we keep track of distances in a dist array. When we visit a new node v from u, its distance is dist[u] + 1. We then increment the count for this distance in our final result array. By running a BFS from every single house as the starting point, we ensure that we count every ordered pair (i, j) and its corresponding shortest distance exactly once. java class Solution { public int[] countOfPairs(int n, int x, int y) { java.util.List<Integer>[] adj = new java.util.ArrayList[n + 1]; for (int i = 1; i <= n; i++) { adj[i] = new java.util.ArrayList<>(); } for (int i = 1; i < n; i++) { adj[i].add(i + 1); adj[i + 1].add(i); } if (x != y) { adj[x].add(y); adj[y].add(x); } int[] result = new int[n]; for (int i = 1; i <= n; i++) { bfs(i, n, adj, result); } return result; } private void bfs(int startNode, int n, java.util.List<Integer>[] adj, int[] result) { int[] dist = new int[n + 1]; java.util.Arrays.fill(dist, -1); java.util.Queue<Integer> q = new java.util.LinkedList<>(); q.offer(startNode); dist[startNode] = 0; while (!q.isEmpty()) { int u = q.poll(); for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.offer(v); result[dist[v] - 1]++; } } } } }
Complexity
Time
O(n^2). We run BFS `n` times, and each BFS takes O(V+E) = O(n) time on this graph.
Space
O(n). The adjacency list, queue, and distance array each require O(n) space.
Trade-offs
Pros
More efficient than Floyd-Warshall with O(n^2) time complexity.
Optimal for finding shortest paths in unweighted graphs.
Uses less space (O(n)) than Floyd-Warshall.
Cons
Still involves iterating through all nodes and running a full graph traversal, which has some overhead.
Slightly more complex to implement than the direct calculation approach.
The most efficient approach for this problem avoids explicit graph traversal. It relies on a mathematical formula derived from the graph's specific structure. By iterating through all pairs of houses and applying this formula, we can directly calculate the shortest distance and aggregate the counts.
Algorithm
- Initialize a result array
ansof sizenwith zeros. - Iterate through all pairs of houses(i, j)where1 <= i < j <= n. - For each pair, calculate the three potential shortest path lengths: -d1 = j - i(linear path). -d2 = |i - x| + 1 + |j - y|(via x-y shortcut). -d3 = |i - y| + 1 + |j - x|(via y-x shortcut). - Find the minimum distanced = min(d1, d2, d3). - Incrementans[d-1]by 2 to account for both(i, j)and(j, i). - Returnans.
Walkthrough
The shortest distance between any two houses i and j is the minimum of the possible path lengths. There are three fundamental path types to consider: 1. The direct linear path: |i - j|. 2. The path using the x-y shortcut: |i - x| + 1 + |j - y|. This represents traveling from i to x, crossing the shortcut, and then going from y to j. 3. The path using the y-x shortcut: |i - y| + 1 + |j - x|. This is similar but involves going via y first. The shortest distance is min(|i - j|, |i - x| + 1 + |j - y|, |i - y| + 1 + |j - x|). The algorithm simply iterates through all unique pairs of houses (i, j) with i < j, computes this minimum distance d, and adds 2 to the count for distance d in a result array. This method is very fast as it only involves arithmetic operations inside the loops. java class Solution { public int[] countOfPairs(int n, int x, int y) { int[] result = new int[n]; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { int dist1 = j - i; int dist2 = Math.abs(i - x) + 1 + Math.abs(j - y); int dist3 = Math.abs(i - y) + 1 + Math.abs(j - x); int minDist = Math.min(dist1, Math.min(dist2, dist3)); if (minDist > 0) { result[minDist - 1] += 2; } } } return result; } }
Complexity
Time
O(n^2), due to nested loops iterating through all unique pairs of houses. Operations inside the loop are O(1).
Space
O(n) to store the result array. Auxiliary space is O(1).
Trade-offs
Pros
Most efficient approach with O(n^2) time complexity and very low constant factors.
Minimal space complexity, O(1) auxiliary space.
Simple implementation without complex data structures.
Cons
The correctness relies on a specific formula, which might be less obvious to derive than applying a general-purpose algorithm.
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; }}class Solution: def countOfPairs(self, n: int, x: int, y: int) -> List[int]: x, y = x - 1, y - 1 ans = [0] * n for i in range(n): for j in range(i + 1, n): a = j - i b = abs(i - x) + 1 + abs(j - y) c = abs(i - y) + 1 + abs(j - x) ans[min(a, b, c) - 1] += 2 return ansclass Solution {public: vector<int> countOfPairs(int n, int x, int y) { vector<int> ans(n); x--; y--; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int a = j - i; int b = abs(x - i) + abs(y - j) + 1; int c = abs(y - i) + abs(x - j) + 1; ans[min({a, 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.