Count the Number of Houses at a Certain Distance I
Source: leetcode
Difficulty: Medium
Tags: breadth-first-search, graph, prefix-sum

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.leetcode.com/uploads/2023/12/20/example2.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.leetcode.com/uploads/2023/12/20/example3.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.leetcode.com/uploads/2023/12/20/example5.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`




C++ solution:
class Solution {
public:
    vector<int> countOfPairs(int n, int x, int y) 
    {
        vector<int> ans(n, 0);
        
        if(x>y)
            swap(x, y);
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                int ways = i-j;
                
                ways = min(ways, abs(j-x) + 1 + abs(y-i));
                

                    ans[ways-1]+=2;
            }
        }
        
        return ans;
    }
};

Go solution:
func countOfPairs(n int, x int, y int) []int {
    adjList := make([][]int, n+1)
    for i := 1; i < n; i++ {
        adjList[i] = append(adjList[i], i+1)
        adjList[i+1] = append(adjList[i+1], i)
    }
    adjList[x] = append(adjList[x], y)
    adjList[y] = append(adjList[y], x)

    ans := make([]int, n)
    
    for i := 1; i <= n; i++ {
        dist := make([]int, n+1)
        for i := range dist { dist[i] = math.MaxInt }
        queue := []int{i}
        dist[i] = 0
        for len(queue) > 0 {
            u := queue[0]  
            du := dist[u]          
            queue = queue[1:]

            for _, v := range adjList[u] {
                if dist[v] > du + 1 {
                    dist[v] = du+1                    
                    ans[dist[v]-1]++
                    queue = append(queue, v)
                }                
            }
        }
    }
    return ans
}

Java solution:
class Solution {
    public int[] countOfPairs(int n, int x, int y) {
         // Initialization of Distance Matrix (dist):
         int[][] dist = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][i] = 0; // The distance from a house to itself is zero.
            if (i < n) 
                dist[i][i + 1] = 1;  //there's a street connecting house i to house i + 1 with distance 1.
            if (i > 1) 
                dist[i][i-1] = 1; // there's a street connecting house i - 1 to house i with distance 1.
    
        }
        dist[x][y] = dist[y][x] = 1; // An additional street connects the house numbered x with the house numbered y.
        
        for (int k = 1; k <= n; k++) { // Floyd-Warshall algorithm to calculate all-pairs shortest paths
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        // Counts the number of pairs of houses for each distance and stores it in a map (countMap).
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] != Integer.MAX_VALUE && i!=j) {
                    countMap.put(dist[i][j], countMap.getOrDefault(dist[i][j], 0) + 1);
                }
            }
        }
        
        // Convert the map to the result array
        // result array where result[k - 1] stores the total number of pairs with minimum distance k.
        int[] result = new int[n];
        for (int k = 1; k <= n; k++) {
            result[k - 1] = countMap.getOrDefault(k, 0);
        }

        return result;
    }
}

JavaScript solution:
/**
 * @param {number} n
 * @param {number} x
 * @param {number} y
 * @return {number[]}
 */
var countOfPairs = function (n, x, y) {
    const result = new Array(n).fill(0);

    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            const distance = Math.min(
                Math.abs(i - j),
                Math.abs(i - x) + Math.abs(j - y) + 1,
                Math.abs(i - y) + Math.abs(j - x) + 1
            );
            result[distance - 1]++;
        }
    }

    return result.map((count, index) => count * 2);
};

Python solution:
class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        # . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . 
        #                 |_______________|
        # tL (tail left)   l (loop)              tR (tail right)

        # no effect (loop = 0)
        if x == y or abs(x - y) == 1:
            return [max(n - i - 1, 0) * 2 for i in range(n)]
        if not x < y:
            x, y = y, x
        ans = [0] * n
        l = y - x + 1
        # count pairs within the loop
        for i in range(l // 2):
            ans[i] += (l * 2) if (i + 1 < l // 2 or l % 2 == 1) else l
        tL = x - 1
        tR = n - y
        # print(ans)
        # count pairs in each tail
        for t in [tL, tR]:
            for i in range(max(t-1, 0)):
                ans[i] += (t - i - 1) * 2
        # print(ans)
        # count pairs that starts at a tail, and 
        # ends in the loop or the other tail 
        def process(t1, t2):
            # print(t1, t2)
            # print(ans)
            if t1 == 0:
                return

            base = [0] * n
            for i in range(2, t2 + 2):
                base[i] += 1
            base[0] = 2
            left = 2
            right = l
            cur = 1
            while left <= right:
                # print(left, right, "lr")
                if left != right:
                    base[cur] += 2 * 2
                else:
                    base[cur] += 1 * 2
                left += 1
                right -= 1
                cur += 1
            # print(base, "base")
            cumsum = 0
            for i in range(n):
                cumsum += base[i]
                if i >= t1:
                    cumsum -= base[i - t1]
                ans[i] += cumsum

        process(tL, tR)
        process(tR, tL)
        return ans

Ruby solution:
def count_of_pairs(n, x, y)
  ans = Array.new(n, 0)
  x, y = [x, y].sort
  (1..n).each do |i|
    (1...i).each do |j|
      d1 = i - j
      d2 = (j - x).abs + 1 + (i - y).abs
      d3 = (j - y).abs + 1 + (i - x).abs
      min_dist = [d1, d2, d3].min
      ans[min_dist - 1] += 2 if min_dist <= n
    end
  end
  ans
end