# Count the Number of Houses at a Certain Distance I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-i)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-houses-at-a-certain-distance-i
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**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-i/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-i/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-i/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 <= 100`
* `1 <= x, y <= n`

# Approaches
## All-Pairs Shortest Path using Floyd-Warshall
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.
**Time:** O(n^3), due to the three nested loops in the Floyd-Warshall algorithm. · **Space:** O(n^2), for storing the adjacency matrix.
**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 `n` is large.; High space complexity of O(n^2).
### Explanation
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; } } ```
### Algorithm
- Initialize an `(n+1)x(n+1)` distance matrix `dist` with infinity, and `dist[i][i] = 0` for all `i`. - Populate `dist` with initial street lengths: `dist[i][i+1] = 1`, `dist[i+1][i] = 1` for `i` in `1..n-1`. - Set `dist[x][y] = 1` and `dist[y][x] = 1` if `x != y`. - Run the Floyd-Warshall algorithm by iterating through all intermediate nodes `k` from 1 to `n` and updating `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`. - Initialize a result array `ans` of size `n` with zeros. - Iterate through all pairs `(i, j)` with `1 <= i < j <= n`. - For each pair, get the distance `d = dist[i][j]` and increment `ans[d-1]` by 2. - Return `ans`.

## Single-Source Shortest Path from Each Node using BFS
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.
**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.
**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.
### Explanation
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]++; } } } } } ```
### Algorithm
- Build an adjacency list `adj` for the graph. - Add edges for the linear streets `(i, i+1)` and the special street `(x, y)`. - Initialize a result array `ans` of size `n` to all zeros. - For each house `startNode` from 1 to `n`: - Perform a BFS starting from `startNode`. - Use a queue for the traversal and a `dist` array to store distances from `startNode`. - When a new node `v` is reached from `u`, set `dist[v] = dist[u] + 1` and increment `ans[dist[v]-1]` by 1. - Return `ans`.

## Direct Calculation via Shortest Path Formula
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.
**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).
**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.
### Explanation
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; } } ```
### Algorithm
- Initialize a result array `ans` of size `n` with zeros. - Iterate through all pairs of houses `(i, j)` where `1 <= 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 distance `d = min(d1, d2, d3)`. - Increment `ans[d-1]` by 2 to account for both `(i, j)` and `(j, i)`. - Return `ans`.

# Solutions
### Java

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

```

### Python

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

```

### CPP

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

```