Streetwise House Pairing Counts: Simplified Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe task is to determine the number of pairs of houses in a city, numbered from 1 to n,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe task is to determine the number of pairs of houses in a city, numbered from 1 to n, where each pair has a minimum distance of k streets between them. Given additional streets connecting houses x and y, the algorithm constructs an adjacency list representing the streets between houses, performs Breadth-First Search (BFS) from each house to calculate the minimum distances to other houses, and then counts the number of pairs for each minimum distance. Finally, it returns the counts in a 1-indexed array of length n.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe algorithm initializes an adjacency list representing the streets between houses, including the additional street connecting houses x and y. It then conducts Breadth-First Search (BFS) from each house to determine the minimum distances to other houses. By counting the number of pairs of houses for each minimum distance, the algorithm constructs a 1-indexed array of length n, where each element represents the count of pairs with a specific minimum street distance.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n ^ 2)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n ^ 2)\n# Code\n```\nfrom collections import deque\n\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        adj = [[] for _ in range(n)]\n        for i in range(1, n):\n            adj[i].append(i-1)\n            adj[i-1].append(i)\n        adj[x-1].append(y-1)\n        adj[y-1].append(x-1)\n        \n        def bfs(start):\n            distances = [-1] * n\n            distances[start] = 0\n            queue = deque([start])\n            while queue:\n                current = queue.popleft()\n                for neighbor in adj[current]:\n                    if distances[neighbor] == -1:\n                        distances[neighbor] = distances[current] + 1\n                        queue.append(neighbor)\n            return distances\n        \n        result = [0] * (n + 1)\n        for i in range(n):\n            distances = bfs(i)\n            for distance in distances:\n                if distance != -1:\n                    result[distance] += 1\n        \n        return result[1:]\n\n```
['Python3']