Descriptive & Easy Java Solution,  Complete explanation about Intuition, Approach & Analysis(TC, SC)
Intuition
Here the question is to find all possible combinations pairs(from, to) for a path K.
So, We can think of just doing reverse that from each home find s
# Intuition
- Here the question is to find all possible combinations pairs(from, to) for a path K. 
- So, We can think of just doing reverse that from each home find shortest path to all other homes
- Then group all the pairs w.r.t shortest paths

# Approach
<!-- Describe your approach to solving the problem. -->
- Create a adjcency list graph for all the vertex 1 to n
- Initialize a TreeMap<Integer, List<Pair>> as it uses strict BST in order to sort the in natural sorting order. 
    -  **Key** represents the shortest Path
    - **List<Pair>** represents all the pair w.r.t shortest Path
- Iteratete over each home and calculate shortest path using BFS and return the distance Array 
- Iterate over the all distance array and store it in the Map
- Finally iterate over map and create a result array that contains count of all the possible shortest path for each **K** 


# Complexity
# **- Time complexity:**
1. Graph Construction
* Creating an adjacency list for n+1 nodes:
    * O(n) for initializing the list of lists.
* Adding edges for a linear path of n-1 nodes:
    * O(n-1) for the loop.
* Adding the edge between nodes x and y:
    * O(1) for two insertions.
* Total: O(n).
2. Outer Loop for Shortest Path Calculation
* Iterates through all nodes i from 1 to n:
    * O(n) iterations.
3. Shortest Path Calculation
* Breadth-First Search (BFS) for shortest path (shortestPath function):
    * Each BFS traversal takes O(V + E), where:
        * V=n+1 V=n+1 (number of nodes in the graph).
        * E=n+1 (number of edges: n n−1 from linear path + 1 additional edge from x to y).
    * For this graph, BFS takes O(n).
* As the outer loop calls BFS n times:
    * Total: O(n \times n) = O(n^2).
4. Updating the Map
* Inner loop for each node j in the shortest path computation:
    * Runs for all nodes: O(n) iterations.
* Map update using computeIfAbsent:
    * Amortized O(1) for map insertion or update.
* Total per BFS traversal: O(n).
* Total for all n BFS traversals: O(n^2).
5. Final Processing of the Map
* Iterating over the map entries:
    * For a sparse graph, the map will have at most O(n) O(n) keys (one for each shortest path length).
    * For each key, processing the list of pairs costs  O(1).
* Total: O(n).
* 

# **- Space complexity:**
1. Graph Representation
* Adjacency list for n+1 nodes:
    * O(n) for the list of lists.
* Each node stores O(1) neighbors (sparse graph):
    * O(n) for all edges.
* Total: O(n).
2. Map to Store Shortest Path Pairs
* The map's keys represent distances  O(n)), and each value is a list of all pairs:
    * Worst case: all O(n2) pairs stored in the map.
* Total: O(n^2).
3. Distance Array
* Stores distances for n+1 nodes during BFS:
    * O(n).
4. Queue for BFS
* Stores nodes during BFS traversal:
    * At most O(n) elements in the queue at any time.
* Total: O(n).

# Code
```java []
class Solution {
  public int[] countOfPairs(int n, int x, int y) {
        //create a graph
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0; i<n+1; i++){
            graph.add(new ArrayList<>());
        }
        //create a map with all shortest path as key
        Map<Integer, List<Pair>> map = new TreeMap<>();
        for(int i=1; i<n; i++){
            graph.get(i).add(i+1);
            graph.get(i+1).add(i);

        }
        //add the path from x to y
        graph.get(x).add(y);
        graph.get(y).add(x);


        //iterate through n and fetch shortest path from each house to all other homes
        for(int i=1; i<=n; i++){
            int[] distance = shortestPath(graph, i, n);
            //update map
            for(int j=1; j<=n; j++){
                if(i!=j)
                    map.computeIfAbsent(distance[j] ,k -> new ArrayList<>()).add(new Pair(i, j));
            }
        }

        int[] res = new int[n];
        for (Map.Entry<Integer, List<Pair>> e : map.entrySet()) {
            res[e.getKey() - 1] = e.getValue().size();
        }
        //add the pairs to the map list such to track the no of pairs for each shortest path
     return res;

    }


    public int[] shortestPath(List<List<Integer>> graph, int start, int n){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        int[] distance = new int[n+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        while(!queue.isEmpty()){
            var curr = queue.poll();

            for(int next: graph.get(curr)){
                var currDist = distance[next];
                var newDist = distance[curr]+1;
                if(currDist > newDist){
                    distance[next] = newDist;
                    queue.add(next);
                }
            }
        }
        return distance;
    }

    class Pair{
        int from;
        int to;
        Pair(int from, int to){
            this.from = from;
            this.to = to;
        }
    }


}
```
['Breadth-First Search', 'Graph', 'Shortest Path', 'Java']