DP - Java Solution | 2D Array - Tabulation| Easy trick of using Floyd Warshall | Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nBy the time you complete reading and understanding the question, you may have gotten id
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBy the time you complete reading and understanding the question, you may have gotten idea of doing it like a graph application, with houses as Nodes and paths b/w them as undirected edges.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPopulate the 2d array with known minimum values between the houses. In the floyd Warshall Algorithm, instead of the K(intermediate vertex), here it is fixed minimum intermediate path i:e k = (x,y) => example: i -> j = i -> x, x -> y, y -> j. (Where x->y is always 1).\n# Complexity\n- Time complexity: **O(N^2)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    \n\n# Code\n```\nclass Solution {\n    public int[] countOfPairs(int n, int x, int y) {\n        int[][] arr = new int[n+1][n+1];\n        int[] res = new int[n];\n        \n        for(int i = 1; i < n + 1; i++){\n            for(int j = 1; j < n + 1; j++){\n                arr[i][j] = Math.abs(i-j);\n            }\n        }\n        \n        if(x != y){\n            arr[x][y] = arr[y][x] = 1;\n        }\n        \n        for(int i = 1; i < n + 1; i++){\n            for(int j = 1; j < n + 1; j++){\n                arr[i][j] = Math.min(arr[i][j],\n                            Math.min(arr[i][x] + arr[x][y] + arr[y][j],\n                                    arr[i][y] + arr[y][x] + arr[x][j]));\n                if(arr[i][j] != 0){\n                    res[arr[i][j] - 1]++;\n                }\n            }\n        }\n        \n        return res;\n    }\n}\n```
['Dynamic Programming', 'Java']