Leetcode 3017: Count the Number of House at a Certain Distance II

You are given three positive integers n, x, and y.

In a city, there exist houses numbered 1 to n connected by n streets. There is a street connecting the house numbered i with the house numbered i + 1 for all 1 <= i <= n - 1 . An additional street connects the house numbered x with the house numbered y.

For each k, such that 1 <= k <= n, you need to find the number of pairs of houses (house1, house2) such that the minimum number of streets that need to be traveled to reach house2 from house1 is k.

Return a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k.

Note that x and y can be equal.

Example 1:

Input: n = 3, x = 1, y = 3
Output: [6,0,0]
Explanation: Let's look at each pair of houses:
- For the pair (1, 2), we can go from house 1 to house 2 directly.
- For the pair (2, 1), we can go from house 2 to house 1 directly.
- For the pair (1, 3), we can go from house 1 to house 3 directly.
- For the pair (3, 1), we can go from house 3 to house 1 directly.
- For the pair (2, 3), we can go from house 2 to house 3 directly.
- For the pair (3, 2), we can go from house 3 to house 2 directly.

Example 2:

Input: n = 5, x = 2, y = 4
Output: [10,8,2,0,0]
Explanation: For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
- For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
- For k == 3, the pairs are (1, 5), and (5, 1).
- For k == 4 and k == 5, there are no pairs.

Example 3:

Input: n = 4, x = 1, y = 1
Output: [6,4,2,0]
Explanation: For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
- For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
- For k == 3, the pairs are (1, 4), and (4, 1).
- For k == 4, there are no pairs.

Constraints:

• 2 <= n <= 10^5
• 1 <= x, y <= n

Problem Analysis:

We can image that we turn a fire. For each start point i where 1 < i < n, we have two direction to burn.

So assume times[t] means at time = t, the number of different change of burning point. And at time = t + 1, it can continue to burn.

At first, at start point i, we can burn to left and right. It continue burn, untile it reach 1, then stop. And reach n, stop too.

When it reach x, it split one more direction to y. So when reach y, it also split one more direction to x.

When it goes from x to y, it will go to the middle and stop. And when it goes from y to x, it will go to the middle and stop.

At last, we get all times, as we assumed previously, times[t] means it can continue to burn, so time[t] need to add time[t-1].

Solution

class Solution {
public:
    vector<long long> countOfPairs(int n, int x, int y) {
        vector<long long> res(n);
        if (x > y) swap(x, y);
        for (int i = 1; i <= n; ++i) {
            res[0] += 2;
            --res[min(i - 1, abs(i - y) + x)];
            --res[min(n - i, abs(i - x) + 1 + n - y)];
            ++res[min(abs(i - x), abs(y - i) + 1)];
            ++res[min(abs(i - x) + 1, abs(y - i))];
            int r = max(x - i, 0) + max(i - y, 0);
            --res[r + (y - x) / 2];
            --res[r + (y - x + 1) / 2];
        }

        for (int i = 1; i < n; ++i) res[i] += res[i - 1];
        
        return res;
    }
};

Time complexity is O(n)

Space complexity is O(n)