# Count the Number of Houses at a Certain Distance II
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-houses-at-a-certain-distance-ii
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-the-number-of-houses-at-a-certain-distance-ii/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-the-number-of-houses-at-a-certain-distance-ii/image1.png) 

**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:**

![](https://assets.glich.co/dsa/count-the-number-of-houses-at-a-certain-distance-ii/image2.png) 

**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 <= 105`
* `1 <= x, y <= n`

# Approaches
## Brute-force with Breadth-First Search (BFS)
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).
**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.
**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.
### Explanation
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)`.
### Algorithm
1. Create an adjacency list to represent the `n` houses and their connections.
2. Add edges for the streets: `(i, i+1)` for `i` from `1` to `n-1`, and the special street `(x, y)`.
3. Initialize a result array `ans` of size `n` with zeros.
4. For each house `start_node` from `1` to `n`:
   a. Perform a BFS starting from `start_node` to calculate the shortest distance to all other houses.
   b. Use a queue and a `distance` array, initialized to infinity, for the BFS. Set `distance[start_node] = 0`.
   c. While the queue is not empty, dequeue a house `u`, and for each neighbor `v`, if `v` is unvisited, update its distance and enqueue it.
   d. After the BFS from `start_node` is complete, iterate through all houses `j` from `1` to `n`.
   e. If `j != start_node`, get the distance `d = distance[j]`. Increment `ans[d-1]`.
5. The problem asks for pairs, and our process counts ordered pairs `(i, j)`. The final `ans` array contains the required counts. Return `ans`.

## Brute-force with Direct Distance Formula
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.
**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.
**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.
### Explanation
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)`).
### Algorithm
1. If `x > y`, swap them to ensure `x <= y`. This simplifies distance calculations slightly but is not essential.
2. Initialize a result array `ans` of size `n` with zeros.
3. Iterate through all pairs of houses `(i, j)` where `1 <= i < j <= n`.
4. 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 is `k = min(dist_line, dist_shortcut)`.
   d. Increment `ans[k-1]` by 2, for the ordered pairs `(i, j)` and `(j, i)`.
5. Return the `ans` array.

## Combinatorial Counting with Prefix Sums
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.
**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.
**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.
### Explanation
Assuming `x <= y`, we can divide the houses `1...n` into three parts:
- Left part (L): houses `1` to `x-1`.
- Middle part (M): houses `x` to `y` (which form a cycle with the shortcut).
- Right part (R): houses `y+1` to `n`.

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 `S` nodes, there are `S-k` pairs at distance `k`. We can add these counts directly.
- **Pairs within M**: The houses `x...y` and the shortcut `(x,y)` form a cycle of length `B = y-x+1`. On a cycle of length `B`, there are `B` pairs for each distance `k < B/2`, and `B/2` pairs for distance `k = B/2` (if `B` is even).
- **Pairs between segments (L-R, L-M, M-R)**: Calculating these counts for each `k` individually can be complex. A better way is to use a difference array (or prefix sums). For example, for L-M pairs, for each node `j` in M, its distance to the cycle entry point `x` is `d_j`. For any node `i` in L at distance `l` from `x`, the total distance is `l + d_j`. For a fixed `d_j`, as `l` varies from `1` to `x-1`, the distances form an arithmetic progression `1+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 of `d_j`, find how many nodes in M have this distance to `x`, 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.
### Algorithm
1. Ensure `x <= y` by swapping if needed.
2. Define segment lengths: `len_L = x - 1`, `len_M = y - x + 1`, `len_R = n - y`.
3. Initialize a `counts` array for unordered pairs and a `diff` array for prefix sum calculations, both of size `n+2`.
4. **Pairs within L, R, M**:
   - L-L: For `k` from `1` to `len_L-1`, add `len_L-k` to `counts[k]`.
   - R-R: For `k` from `1` to `len_R-1`, add `len_R-k` to `counts[k]`.
   - M-M: For `k` from `1` to `(len_M-1)/2`, add `len_M` to `counts[k]`. If `len_M` is even, add `len_M/2` to `counts[len_M/2]`.
5. **Pairs L-R**:
   - Calculate the number of pairs `(i, j)` for each possible sum of distances `S = (x-i) + (j-y)`. Add this to `counts[k]` where `k = S + min(y-x, 1)`.
6. **Pairs L-M and M-R (using difference array)**:
   - For each distance `d` from a cycle endpoint (`x` or `y`) to a node in M, find the number of nodes `c` at that distance `d`.
   - For L-M pairs, this contributes `c` pairs for each distance in `[1+d, len_L+d]`. Update `diff` array: `diff[1+d] += c`, `diff[len_L+d+1] -= c`.
   - Do symmetrically for M-R pairs with `len_R`.
7. **Finalize counts**:
   - Compute prefix sums on `diff` to get the total contribution for L-M and M-R pairs, and add to `counts`.
   - `current_sum = 0`. For `k` from `1` to `n`, `current_sum += diff[k]`, then `counts[k] += current_sum`.
8. Create the final `result` array. For each `k`, `result[k-1] = counts[k] * 2`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 res

```