Count The Number Of Houses At A Certain Distance 1
✨ IntuitionTo solve this problem, we are essentially asked to compute the shortest path between all pairs of nodes in a graph. The graph is represented by n nod
# ✨ Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To solve this problem, we are essentially asked to compute the shortest path between all pairs of nodes in a graph. The graph is represented by n nodes, where:

Each node is connected to its next node, creating a simple chain structure.
A special connection between nodes x and y is added (with weight 1).
Our goal is to compute how many pairs of nodes have each possible shortest path distance.
We can think of this problem as an all-pairs shortest path problem, which can be efficiently solved using the Floyd-Warshall algorithm.
# 🚀 Approach
<!-- Describe your approach to solving the problem. -->
Graph Representation:

We use an adjacency matrix adj[][] to represent the graph where each adj[i][j] stores the shortest distance from node i to node j.
Initially, all distances are set to Integer.MAX_VALUE (i.e., infinity) to represent the absence of a path, except for the diagonal (adj[i][i] = 0) which represents self-loops with zero distance.
We then populate the adjacency matrix with direct connections between consecutive nodes and the special connection between x and y.

Floyd-Warshall Algorithm:

This algorithm computes the shortest paths between all pairs of nodes by iteratively trying to improve the path between two nodes through any intermediate node (via).
It updates the adjacency matrix to reflect the shortest path found.

Count Pairwise Distances:

After computing the shortest paths between all pairs, we iterate over the matrix to count how many pairs have each possible distance k (from 1 to the maximum possible distance).
The result array holds the counts for each path length.


# 📊 Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Floyd-Warshall Algorithm: O(n^3), where n is the number of nodes. The algorithm iterates over all pairs of nodes and for each pair, it considers all possible intermediate nodes.
Counting Pairs: O(n^2), as we iterate over all pairs to count how many have each distance.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n^2) for the adjacency matrix to store distances between every pair of nodes.
# Code
```java []
class Solution {
    public int[] countOfPairs(int n, int x, int y) {
        // Initialize result array to store the count of pairs for each distance
        int[] result = new int[n];

        // Initialize adjacency matrix with maximum values (representing no direct path)
        int[][] adj = new int[n + 1][n + 1];  // Matrix to store shortest paths between all pairs
        for (int[] row : adj) {
            Arrays.fill(row, Integer.MAX_VALUE);  // Set all distances to infinity initially
        }

        // Distance to itself is 0
        for (int i = 1; i <= n; i++) {
            adj[i][i] = 0;
        }

        // Create initial connections (direct edges between consecutive nodes)
        // For every pair of adjacent nodes, set the distance as 1 (since they are connected directly)
        for (int i = 1; i < n; i++) {
            adj[i][i + 1] = 1;  // Distance between i and i+1 is 1
            adj[i + 1][i] = 1;  // Graph is undirected, so set the reverse as well
        }

        // Add special edge between nodes x and y with weight 1
        adj[x][y] = 1;
        adj[y][x] = 1;

        // 🚀 **Floyd-Warshall Algorithm** to compute shortest paths between all pairs of nodes
        for (int via = 1; via <= n; via++) {  // Iterate over each node as an intermediate node
            for (int i = 1; i <= n; i++) {  // Iterate over every source node
                for (int j = 1; j <= n; j++) {  // Iterate over every target node
                    // If there's a shorter path through the intermediate node 'via', update the distance
                    if (adj[i][via] != Integer.MAX_VALUE && adj[via][j] != Integer.MAX_VALUE) {
                        adj[i][j] = Math.min(adj[i][j], adj[i][via] + adj[via][j]);
                    }
                }
            }
        }

        // 🎯 **Counting the Pairs** with distances for each possible value from 1 to n-1
        for (int i = 1; i <= n; i++) {  // Iterate over all source nodes
            for (int j = 1; j <= n; j++) {  // Iterate over all target nodes
                if (i != j) {  // Ignore self-pairs (i != j)
                    int val = adj[i][j];  // Get the shortest distance between nodes i and j
                    if (val != Integer.MAX_VALUE) {  // If there's a valid path
                        result[val - 1]++;  // Increment the count for the corresponding distance
                    }
                }
            }
        }

        // Return the result array containing the counts for each distance (1 to n-1)
        return result;
    }
}

```
['Java']