[Java] ✅ ⬆️ Easy | Optimized ✅ | O(n^2)  | Floyd Warshal Standard |  Step By Step |. Clean | Simple
Complexity\nFloyd Warshal\nTime complexity: O(n^3)\nSpace complexity: O(n^2)\n\nclass Solution {\n    public int[] countOfPairs(int n, int x, int y) {\n        
**Complexity**\n**Floyd Warshal**\nTime complexity: O(n^3)\nSpace complexity: O(n^2)\n```\nclass Solution {\n    public int[] countOfPairs(int n, int x, int y) {\n         // Initialization of Distance Matrix (dist):\n         int[][] dist = new int[n + 1][n + 1];\n\n        for (int i = 1; i <= n; i++) {\n            Arrays.fill(dist[i], Integer.MAX_VALUE);\n            dist[i][i] = 0; // The distance from a house to itself is zero.\n            if (i < n) \n                dist[i][i + 1] = 1;  //there\'s a street connecting house i to house i + 1 with distance 1.\n            if (i > 1) \n                dist[i][i-1] = 1; // there\'s a street connecting house i - 1 to house i with distance 1.\n    \n        }\n        dist[x][y] = dist[y][x] = 1; // An additional street connects the house numbered x with the house numbered y.\n        \n        for (int k = 1; k <= n; k++) { // Floyd-Warshall algorithm to calculate all-pairs shortest paths\n            for (int i = 1; i <= n; i++) {\n                for (int j = 1; j <= n; j++) {\n                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {\n                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);\n                    }\n                }\n            }\n        }\n        \n        // Counts the number of pairs of houses for each distance and stores it in a map (countMap).\n        Map<Integer, Integer> countMap = new HashMap<>();\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (dist[i][j] != Integer.MAX_VALUE && i!=j) {\n                    countMap.put(dist[i][j], countMap.getOrDefault(dist[i][j], 0) + 1);\n                }\n            }\n        }\n        \n        // Convert the map to the result array\n        // result array where result[k - 1] stores the total number of pairs with minimum distance k.\n        int[] result = new int[n];\n        for (int k = 1; k <= n; k++) {\n            result[k - 1] = countMap.getOrDefault(k, 0);\n        }\n\n        return result;\n    }\n}\n```\n\n**Optimized Solution:**\nTime complexity: O(n^2)\nSpace complexity: O(1)\n```\nclass Solution {\n    public int[] countOfPairs(int n, int x, int y) {\n        // Initialize an array to store the result (result):\n        int[] result = new int[n];\n\n        // Iterate over all pairs of houses:\n        for (int i = 1; i <= n; i++) {\n            for (int j = i + 1; j <= n; j++) {\n                // Calculate the minimum distance using a different approaches\n                int val = Math.min(\n                    Math.abs(i - j),  // Direct distance between houses i and j, i->j \n                    Math.min(\n                        Math.abs(i - x) + 1 + Math.abs(y - j),  // Distance through x and y,  i->x->y->j \n                        Math.abs(i - y) + 1 + Math.abs(x - j)  // Distance through y and x, i->y->x->j \n                    )\n                );\n                // Update the result array based on the minimum distance \n                result[val - 1] += 2; // from i to j and j to i\n            }\n        }\n        return result;\n    }\n}\n```\n**Please Upvote**\n
['Java']