Count the Number of Houses at a Certain Distance II
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to model the city and streets as a graph. We can then find the shortest distance between all pairs of houses. A standard algorithm for finding shortest paths in an unweighted graph is Breadth-First Search (BFS).
Algorithm
- Create an adjacency list to represent the
nhouses and their connections. - Add edges for the streets:
(i, i+1)forifrom1ton-1, and the special street(x, y). - Initialize a result array
ansof sizenwith zeros. - For each house
start_nodefrom1ton: a. Perform a BFS starting fromstart_nodeto calculate the shortest distance to all other houses. b. Use a queue and adistancearray, initialized to infinity, for the BFS. Setdistance[start_node] = 0. c. While the queue is not empty, dequeue a houseu, and for each neighborv, ifvis unvisited, update its distance and enqueue it. d. After the BFS fromstart_nodeis complete, iterate through all housesjfrom1ton. e. Ifj != start_node, get the distanced = distance[j]. Incrementans[d-1]. - The problem asks for pairs, and our process counts ordered pairs
(i, j). The finalansarray contains the required counts. Returnans.
Walkthrough
First, we construct an explicit graph representation, like an adjacency list, from the input n, x, and y. The graph has n nodes. There are edges (i, i+1) for 1 <= i < n, and an additional edge (x, y).
Then, we iterate through each house i from 1 to n and use it as the starting source for a BFS traversal. The BFS algorithm will find the shortest distance from house i to all other houses j. During the BFS from i, we maintain a distance array. After the BFS is complete, for each house j, we increment the count for the calculated distance dist(i, j) in our result array.
Since the problem asks for the number of pairs (house1, house2), and distance is symmetric (dist(i, j) = dist(j, i)), running BFS from every node i and summing up the distances to all other nodes j correctly counts every ordered pair (i, j).
Complexity
Time
O(N^2). We run a BFS from each of the N nodes. Each BFS takes O(N + E) time, where E is the number of edges. In our graph, E is approximately N. So, one BFS is O(N). Repeating this for all N nodes gives a total time complexity of O(N^2). With N up to 10^5, this is not feasible.
Space
O(N). The adjacency list requires O(N) space. The distance array and queue used in each BFS also require O(N) space.
Trade-offs
Pros
Simple to understand and implement.
It's a general solution for any graph structure, not just this specific one.
Cons
Very inefficient for the given constraints. The time complexity is too high.
Instead of building a graph and running BFS, we can compute the shortest distance for each pair of houses (i, j) directly. The structure of the connections allows for a simple formula to calculate this distance.
Algorithm
- If
x > y, swap them to ensurex <= y. This simplifies distance calculations slightly but is not essential. - Initialize a result array
ansof sizenwith zeros. - Iterate through all pairs of houses
(i, j)where1 <= i < j <= n. - For each pair
(i, j): a. Calculate the distance along the main street:dist_line = j - i. b. Calculate the distance using the shortcut:dist_shortcut = |i - x| + 1 + |j - y|. c. The minimum distance isk = min(dist_line, dist_shortcut). d. Incrementans[k-1]by 2, for the ordered pairs(i, j)and(j, i). - Return the
ansarray.
Walkthrough
The shortest path between any two houses i and j can be one of two types: the direct path along the line of houses, or a path that utilizes the shortcut between house x and house y.
The distance along the line is simply |i - j|. A path using the shortcut would go from i to x, cross the shortcut to y, and then go from y to j. The length of this path is |i - x| + 1 + |j - y|. The path could also go from i to y, then to x, then to j, with length |i - y| + 1 + |j - x|. The shortest distance is the minimum of all these possibilities. Since the shortcut is bidirectional, we only need to consider one version of it. So, dist(i, j) = min(|i - j|, |i - x| + 1 + |j - y|).
We can iterate through all unique pairs of houses (i, j) with i < j, calculate their shortest distance k using this formula, and add 2 to the count for distance k (to account for both (i, j) and (j, i)).
Complexity
Time
O(N^2). There are two nested loops to iterate through all pairs of houses, which is `N * (N-1) / 2` pairs. The calculation inside the loop is O(1). Thus, the total time complexity is O(N^2).
Space
O(N) to store the result array. No other significant space is needed.
Trade-offs
Pros
Conceptually simpler than the BFS approach as it avoids explicit graph construction.
Easy to implement.
Cons
The
O(N^2)time complexity makes it too slow for the given constraints.
The O(N^2) approaches are too slow. A more efficient O(N) solution can be achieved by analyzing the structure of the graph and counting pairs combinatorially. The houses can be partitioned into three segments relative to the shortcut (x, y), and we can count pairs within and between these segments.
Algorithm
- Ensure
x <= yby swapping if needed. - Define segment lengths:
len_L = x - 1,len_M = y - x + 1,len_R = n - y. - Initialize a
countsarray for unordered pairs and adiffarray for prefix sum calculations, both of sizen+2. - Pairs within L, R, M:
- L-L: For
kfrom1tolen_L-1, addlen_L-ktocounts[k]. - R-R: For
kfrom1tolen_R-1, addlen_R-ktocounts[k]. - M-M: For
kfrom1to(len_M-1)/2, addlen_Mtocounts[k]. Iflen_Mis even, addlen_M/2tocounts[len_M/2].
- L-L: For
- Pairs L-R:
- Calculate the number of pairs
(i, j)for each possible sum of distancesS = (x-i) + (j-y). Add this tocounts[k]wherek = S + min(y-x, 1).
- Calculate the number of pairs
- Pairs L-M and M-R (using difference array):
- For each distance
dfrom a cycle endpoint (xory) to a node in M, find the number of nodescat that distanced. - For L-M pairs, this contributes
cpairs for each distance in[1+d, len_L+d]. Updatediffarray:diff[1+d] += c,diff[len_L+d+1] -= c. - Do symmetrically for M-R pairs with
len_R.
- For each distance
- Finalize counts:
- Compute prefix sums on
diffto get the total contribution for L-M and M-R pairs, and add tocounts. current_sum = 0. Forkfrom1ton,current_sum += diff[k], thencounts[k] += current_sum.
- Compute prefix sums on
- Create the final
resultarray. For eachk,result[k-1] = counts[k] * 2.
Walkthrough
Assuming x <= y, we can divide the houses 1...n into three parts:
- Left part (L): houses
1tox-1. - Middle part (M): houses
xtoy(which form a cycle with the shortcut). - Right part (R): houses
y+1ton.
We can count the number of pairs for each distance k by considering where the two houses in a pair are located (L-L, M-M, R-R, L-M, L-R, M-R).
- Pairs within L or R: These segments are simple lines. For a line of
Snodes, there areS-kpairs at distancek. We can add these counts directly. - Pairs within M: The houses
x...yand the shortcut(x,y)form a cycle of lengthB = y-x+1. On a cycle of lengthB, there areBpairs for each distancek < B/2, andB/2pairs for distancek = B/2(ifBis even). - Pairs between segments (L-R, L-M, M-R): Calculating these counts for each
kindividually can be complex. A better way is to use a difference array (or prefix sums). For example, for L-M pairs, for each nodejin M, its distance to the cycle entry pointxisd_j. For any nodeiin L at distancelfromx, the total distance isl + d_j. For a fixedd_j, aslvaries from1tox-1, the distances form an arithmetic progression1+d_j, 2+d_j, ..., (x-1)+d_j. We can update the counts for this range of distances efficiently using a difference array. We iterate through all possible values ofd_j, find how many nodes in M have this distance tox, and perform a range update on our difference array. The same logic applies to L-R and M-R pairs.
After calculating contributions from all pair types, we compute the prefix sums of the difference array to get the final counts for each distance. Finally, we multiply by 2 for ordered pairs.
Complexity
Time
O(N). Each step of the combinatorial counting involves loops that run up to N, A, B, or C times (where A+B+C is approx N). The prefix sum calculation is also O(N). The overall complexity is linear.
Space
O(N) for storing the counts and the difference array.
Trade-offs
Pros
Highly efficient with linear time complexity.
Scales well for large N.
Cons
The logic is complex and involves careful case analysis and combinatorial counting.
Implementation is more error-prone than simpler approaches.
Solutions
Solution
class Solution {public long[] countOfPairs(int n, int x, int y) { --x; --y; if (x > y) { int temp = x; x = y; y = temp; } long[] diff = new long[n]; for (int i = 0; i < n; ++i) { diff[0] += 1 + 1; ++diff[Math.min(Math.abs(i - x), Math.abs(i - y) + 1)]; ++diff[Math.min(Math.abs(i - y), Math.abs(i - x) + 1)]; --diff[Math.min(Math.abs(i - 0), Math.abs(i - y) + 1 + Math.abs(x - 0))]; --diff[Math.min(Math.abs(i - (n - 1)), Math.abs(i - x) + 1 + Math.abs(y - (n - 1)))]; --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 0) / 2]; --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 1) / 2]; } for (int i = 0; i + 1 < n; ++i) { diff[i + 1] += diff[i]; } return diff; }}class Solution {public: vector<long long> countOfPairs(int n, int x, int y) { --x, --y; if (x > y) { swap(x, y); } vector<long long> diff(n); for (int i = 0; i < n; ++i) { diff[0] += 1 + 1; ++diff[min(abs(i - x), abs(i - y) + 1)]; ++diff[min(abs(i - y), abs(i - x) + 1)]; --diff[min(abs(i - 0), abs(i - y) + 1 + abs(x - 0))]; --diff[min(abs(i - (n - 1)), abs(i - x) + 1 + abs(y - (n - 1)))]; --diff[max(x - i, 0) + max(i - y, 0) + ((y - x) + 0) / 2]; --diff[max(x - i, 0) + max(i - y, 0) + ((y - x) + 1) / 2]; } for (int i = 0; i + 1 < n; ++i) { diff[i + 1] += diff[i]; } return diff; }};class Solution: def countOfPairs(self, n: int, x: int, y: int) -> List[int]: if abs(x - y) <= 1: return [2 * x for x in reversed(range(n))] cycle_len = abs(x - y) + 1 n2 = n - cycle_len + 2 res = [2 * x for x in reversed(range(n2))] while len(res) < n: res . append(0) res2 = [cycle_len * 2] * (cycle_len >> 1) if not cycle_len & 1: res2[- 1] = cycle_len res2[0] -= 2 for i in range(len(res2)): res[i] += res2[i] if x > y: x, y = y, x tail1 = x - 1 tail2 = n - y for tail in (tail1, tail2): if not tail: continue i_mx = tail + (cycle_len >> 1) val_mx = 4 * min((cycle_len - 3) >> 1, tail) i_mx2 = i_mx - (1 - (cycle_len & 1)) res3 = [val_mx] * i_mx res3[0] = 0 res3[1] = 0 if not cycle_len & 1: res3[- 1] = 0 for i, j in enumerate(range(4, val_mx, 4)): res3[i + 2] = j res3[i_mx2 - i - 1] = j for i in range(1, tail + 1): res3[i] += 2 if not cycle_len & 1: mn = cycle_len >> 1 for i in range(mn, mn + tail): res3[i] += 2 for i in range(len(res3)): res[i] += res3[i] return resVideo 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.