Math, Case Handling | C++
Intuition\nCalculating the distance for each pair individually would be inefficient due to its time complexity, so a more optimized approach is required. A comb
# Intuition\nCalculating the distance for each pair individually would be inefficient due to its time complexity, so a more optimized approach is required. A combinatorial method, considering various cases based on the distance between houses and the connection points x and y, can provide a faster solution.\n\n# Approach\nWe break down the problem into three cases:\n\n**Case 1**: Ignoring houses within the range (x, y) exclusively. The new graph forms a chain, and its contribution to the answer is easily computed as `len - k`.\n\n![image.png](https://assets.leetcode.com/users/images/07092485-6ef5-4c1a-8aa4-0af4ad490569_1705809817.201522.png)\n\n**Case 2**: Considering only houses within the range [x, y] inclusively. The new graph forms a circle, and its contribution to the answer is determined by size:\n- It is `size` if `2 * k < size`, \n- `size / 2` if `2 * k = size`, \n- and `0` otherwise. \n\nNote that there is an overlapping pair for Case 1 and Case 2 if k = 1, which is subtracted from answer[k = 1].\n\n![image.png](https://assets.leetcode.com/users/images/ce0e410c-3ca3-4706-9aec-6787767decac_1705809829.2928915.png)\n\n**Case 3**: One endpoint is in (x, y), while the other is in [1, x) U (y, n]. To achieve this, we precompute the distance of each house in (x, y) to x and y in $$O(1)$$ time using a simple mathematical formula. We store the frequency of these distances. \nThe contribution can be calculated by summing frequencies for each distance. For instance, the contribution when considering houses from [1, x) going to (x, y) via house x would be $$\\sum_{i = k - x + 1}^{k - 1 }freq_x[i]$$, and a similar computation applies for houses from (y, n] going to (x, y) via house y.\n\n![image.png](https://assets.leetcode.com/users/images/fcc23ad1-ef4a-4604-aa09-0756db7097d3_1705809840.1417177.png)\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    // Arrays to store the frequency of distances from each house in the range (x, y) to x and y\n    int disL[100001] = {};\n    int disR[100001] = {};\n\npublic:\n    vector<long long> countOfPairs(int n, int x, int y) {\n        // Ensure x is smaller than y\n        if (x > y) swap(x, y);\n\n        // Precompute distances and their frequencies for houses in the range (x, y)\n        for (int i = x + 1; i < y; i++) {\n            int tmpL = min(i - x, y - i + 1);\n            int tmpR = min(i - x + 1, y - i);\n            disL[tmpL]++, disR[tmpR]++;\n        }\n\n        // Initialize the result array\n        vector<long long> ans(n, 0);\n\n        // Calculate parameters for three cases\n        int line = n - max(y - x - 1, 0);\n        int circ = y - x + 1;\n        int l1 = -(x - 2), r1 = 0, l2 = -(n - y - 1), r2 = 0;\n        int sumL = 0, sumR = 0;\n\n        // Iterate through each k and calculate the number of pairs\n        for (int k = 1; k <= n; k++) {\n            // Case 1: Ignoring houses within the range (x, y) exclusively\n            ans[k - 1] += max(0, line - k);\n\n            // Case 2: Considering only houses within the range [x, y] inclusively\n            if (2 * k < circ) ans[k - 1] += circ;\n            else if (2 * k == circ) ans[k - 1] += circ / 2;\n\n            // Case 3: One endpoint is in (x, y), while the other is in [1, x) U (y, n]\n            ans[k - 1] += sumL + sumR;\n\n            // Update sumL and sumR by removing outdated distances\n            if (l1 >= 0) sumL -= disL[l1];\n            if (l2 >= 0) sumR -= disR[l2];\n\n            // Update indices for distances\n            l1++, r1++, l2++, r2++;\n\n            // Add new distances to sumL and sumR\n            if (r1 <= n) sumL += disL[r1];\n            if (r2 <= n) sumR += disR[r2];\n        }\n\n        // Subtract 1 from the result for overlapping pair when x != y\n        if (x != y) ans[0]--;\n\n        // Multiply all elements by 2 as each pair is counted twice\n        for (auto &i : ans) i *= 2;\n\n        // Return the final result\n        return ans;\n    }\n};\n```
['Math', 'Sliding Window', 'C++']