[Python] O(N) counting for the ring, linear stems and linear-ring interactions
Intuition\nWe cannot use all-pair shortest paths for this problem due to the input size. Consider the added x-y edge, it creates a ring for the nodes [x ... y].
# Intuition\nWe cannot use all-pair shortest paths for this problem due to the input size. Consider the added x-y edge, it creates a ring for the nodes `[x ... y]`. The remaining items `[1 .. x]` and `[y ... n]` each forms a linear stem. \n\nHere are the cases we need to consider\n- Pairs of nodes within the ring. \n- Pairs of nodes within the linear structure formed by `[1 ... x, y ... n]`\n- Pairs of nodes where one is in a linear stem and the other in the ring\n\nCare must be taken to consider duplicate cases where `x, y` are involved. \n\n# Complexity\n- Time complexity: O(N)\n\n- Space complexity: O(N)\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        if x > y:\n            x, y = y, x\n        # If the whole thing is a linear structure, the result is simple.\n        if x == y or x + 1 == y:\n            return [2 * (n - dist) for dist in range(1, n + 1)]\n\n        lhs_linear_size = x\n        rhs_linear_size = n - y + 1\n        # Number of items in the ring formed by the new x-y edge.\n        ring_size = y - x + 1\n        fan_size = (ring_size - 1) // 2\n\n        num_pairs = [0] * (n + 1)\n\n        # First compute the results for the ring.\n        for dist in range(1, fan_size + 1):\n            num_pairs[dist] += 2 * ring_size\n        if fan_size * 2 + 1 < ring_size:\n            num_pairs[fan_size + 1] += ring_size\n        # If the whole thing is a ring, no need to move further. \n        if ring_size == n:\n            return num_pairs[1:]\n            \n        num_nodes = min(lhs_linear_size + rhs_linear_size, n)\n        for dist in range(1, num_nodes):\n            num_pairs[dist] += 2 * (num_nodes - dist)\n        # Compute x-y counts in the ring. \n        num_pairs[1] += 2\n        for num_nodes in [lhs_linear_size, rhs_linear_size]:\n            for dist in range(1, num_nodes + 1):\n                num_pairs[dist] -= 2\n            \n        if fan_size * 2 + 1 < ring_size:\n            for num_nodes in [lhs_linear_size, rhs_linear_size]:\n                for dist in range(1, num_nodes):\n                    num_pairs[dist + fan_size + 1] += 2\n\n        if fan_size > 0:\n            for num_nodes in [lhs_linear_size, rhs_linear_size]:\n                if num_nodes < 2:\n                    continue\n                # Only consider the nodes that are neither x nor y.\n                # Hence the linear stem only contains `num_nodes - 1` items.\n                min_dist = 1 + 1\n                max_dist = (num_nodes - 1) + fan_size\n                num_fans = 2\n                for dist in range(min_dist, max_dist + 1):\n                    mult = min(1 + min(dist - min_dist, max_dist - dist), fan_size, num_nodes - 1)\n                    num_pairs[dist] += mult * num_fans * 2               \n\n        return num_pairs[1:]       \n```
['Python3']