Count the Number of Houses at a Certain Distance II
Source: leetcode
Difficulty: Hard
Tags: graph, prefix-sum

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:**


![](https://assets.leetcode.com/uploads/2023/12/20/example2.png)

```

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:**


![](https://assets.leetcode.com/uploads/2023/12/20/example3.png)

```

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:**


![](https://assets.leetcode.com/uploads/2023/12/20/example5.png)

```

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 <= 105`
- `1 <= x, y <= n`




C++ solution:
class Solution {
public:
    vector<long long> countOfPairs(int n, int x, int y) {
        vector<long long> ans(n+2);
        if(x > y)swap(x,y);
        if(y-x <= 1)x=y=n;

        for(int i=1;i<=x;i++){
            ans[1]+=1;
            ans[i]-=1;
        }
        int ptr = x+1;
        int temp = ptr;
        while((ptr-x+1) < (y-ptr)) ptr++;
        temp=ptr;
        for(int i = y ;i > x; i--){
            int d1 = min(y-i+1,i-x);
            ans[d1]+=1;
            ans[d1+x]-=1;
            d1 = y-i+1;
            // 1 2 3 4
            while(ptr-x+d1 >= i-ptr && ptr > x)ptr--;
            
             
            ans[1]+=1;
            ans[i-ptr]-=1;
            if(ptr > x){
                ans[d1 + 1]+=1;
                ans[d1 + (ptr-x+1)]-=1;
            }    
            
               
        } 
        
        ptr=temp;
        for(int i = y+1;i<=n;i++){
            int d1 = i-y+1;
            ans[1]+=1;
            ans[i-ptr+1]-=1;
            ans[d1+x]-=1;
            ans[d1]+=1; 
            if(ptr-x > 1){
                ans[d1+1]+=1;
                ans[d1+ptr-x]-=1;
            }

        }
        
        
        for(int i =1;i<=n;i++)ans[i]+=ans[i-1];
        vector<long long> ans1(n) ;
        for(int i =1 ;i<=n;i++)ans1[i-1] = 2*ans[i];
        return ans1;
    }
};

Go solution:
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type it struct {
	l, r int
}

func countOfPairs(n int, x int, y int) []int64 {
	if x > y {
		x, y = y, x
	}
    // generate intervals
	ret := []int64{}
	intervals := []it{}
	for i := 1; i < n; i++ {
		short := 1 + abs(i-x)
		if y-i > short { // shortcut
			if y<n{ // y to n
				intervals = append(intervals, it{short+1, short + n - y})
			}	
            t := y - i - short
			step := t / 2
			if t&1 == 1 {
				step++
			}
			intervals = append(intervals, it{short, short + step - 1}) // right half of house1 to y
			intervals = append(intervals, it{1, y - step - i}) // left half of house1 to y
		} else { // x y is not a shortcut
			intervals = append(intervals, it{1, n - i})
		}
	}
    // sweep line
	arr := make([]int64, n+1)
	for _, i := range intervals {
		arr[i.l]++
		arr[i.r+1]--
	}
	cur := int64(0)
	for k := 1; k <= n; k++ {
		cur += arr[k]
		ret = append(ret, 2*cur)
	}

	return ret
}

Java solution:
class Solution {
    public long[] countOfPairs(int n, int x, int y) {
        if (x > y) {
            return countOfPairs(n, y, x);
        }

        if (x + 1 == y) {
            return countOfPairs(n, x, x);
        }

        int line = n - (y - x) + 1;
        int ring = y - x + 1;
        long[] result = new long[n];
        for (int k = 1; k < n; k++) {
            if (x == y) {
                result[k - 1] = n - k;
            } else {
                // Case 1: In ring pairs
                if (k <= ring / 2) {
                    result[k - 1] += k * 2 == ring ? ring / 2 : ring;
                }

                // Case 2: House pairs that is on the line without going into the ring
                result[k - 1] += Math.max(0, k == 1 ? line - k - 1 : line - k);

                // Case 3: One house out of the ring, the other house in the ring
                if (k != 1) {
                    int maxInRingLen = Math.min(k - 1, ring / 2);

                    int leftMinInRingLen = Math.max(1, k - (x - 1));
                    if (leftMinInRingLen <= maxInRingLen) {
                        result[k - 1] += 2 * (maxInRingLen - leftMinInRingLen + 1);
                        // Special case, in ring len is 1, which is overlapped with case 2
                        if (leftMinInRingLen == 1) {
                            result[k - 1]--;
                        }
                        // Special case, in ring len is ring/2 and ring is even, in this case there will be one less pair
                        if (maxInRingLen * 2 == ring) {
                            result[k - 1]--;
                        }
                    }

                    int rightMinInRingLen = Math.max(1, k - (n - y));
                    if (rightMinInRingLen <= maxInRingLen) {
                        result[k - 1] += 2 * (maxInRingLen - rightMinInRingLen + 1);
                        if (rightMinInRingLen == 1) {
                            result[k - 1]--;
                        }
                        if (maxInRingLen * 2 == ring) {
                            result[k - 1]--;
                        }
                    }
                }
            }

            result[k - 1] *= 2;
        }

        return result;
    }
}

JavaScript solution:
let acc = Array(100001).fill(0);

/**
 * @param {number} n
 * @param {number} x
 * @param {number} y
 * @return {number[]}
 */
var countOfPairs = function (n, x, y) {
  let res = new Uint32Array(n);

  // Just a line
  if (Math.abs(x - y) <= 1) {
    for (let i = 0; i < n; ++i) res[i] = (n - i - 1) * 2;
    return res;
  }

  acc.fill(0, 0, n + 1);
  if (x > y) {
    let t = x;
    x = y;
    y = t;
  }
  if (x - 1 > n - y) {
    let t = n - y + 1;
    y = n - x + 1;
    x = t;
  }

  // Both on the loop
  let c = y - x + 1;
  let h = (y - x) >> 1;
  acc[1] += 2 * c;
  acc[h + 1] -= 2 * c;

  if ((c & 1) == 0) {
    acc[c >> 1] += c
    acc[(c >> 1) + 1] -= c
  }

  // Both on the arms
  let la = x - 1;
  let ra = n - y;
  if (la) {
    acc[1] += (la - 1) << 1;
    for (let i = 2; i <= la; ++i) {
      acc[i] -= 2;
    }
  }
  if (ra) {
    acc[1] += (ra - 1) << 1;
    for (let i = 2; i <= ra; ++i) {
      acc[i] -= 2;
    }
  }
  for (let i = 1; i <= la; ++i) {
    acc[i + 2] += 2;
    acc[i + 2 + ra] -= 2;
  }

  // One on the loop and one on the arm
  for (let i = 1; i <= la; ++i) {
    acc[i] += 2;
    acc[i + h + 1] -= 2;
    acc[i + 1] += 2;
    acc[i + h + 1 + ((c & 1) ^ 1)] -= 2;
  }
  for (let i = 1; i <= ra; ++i) {
    acc[i] += 2;
    acc[i + h + 1] -= 2;
    acc[i + 1] += 2;
    acc[i + h + 1 + ((c & 1) ^ 1)] -= 2;
  }

  res[0] = acc[1];
  for (let i = 1; i < n; ++i) {
    res[i] = res[i - 1] + acc[i + 1];
  }
  return res;
};

Python solution:
class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if abs(x - y) <= 1:
            return [2 * x for x in reversed(range(n))]
        cycle_len = abs(x - y) + 1
        n2 = n - cycle_len + 2
        res = [2 * x for x in reversed(range(n2))]
        while len(res) < n:
            res.append(0)
        res2 = [cycle_len * 2] * (cycle_len >> 1)
        if not cycle_len & 1:
            res2[-1] = cycle_len
        res2[0] -= 2
        for i in range(len(res2)):
            res[i] += res2[i]
        if x > y:
            x, y = y, x
        tail1 = x - 1
        tail2 = n - y
        for tail in (tail1, tail2):
            if not tail:
                continue
            i_mx = tail + (cycle_len >> 1)
            val_mx = 4 * min((cycle_len - 3) >> 1, tail)
            i_mx2 = i_mx - (1 - (cycle_len & 1))
            res3 = [val_mx] * i_mx
            res3[0] = 0
            res3[1] = 0
            if not cycle_len & 1:
                res3[-1] = 0
            for i, j in enumerate(range(4, val_mx, 4)):
                res3[i + 2] = j
                res3[i_mx2 - i - 1] = j
            for i in range(1, tail + 1):
                res3[i] += 2
            if not cycle_len & 1:
                mn = cycle_len >> 1
                for i in range(mn, mn + tail):
                    res3[i] += 2
            for i in range(len(res3)):
                res[i] += res3[i]
        return res

Ruby solution:
def count_of_pairs(n, x, y)
  x, y = [x, y].sort
  if (y - x) <= 1
    return (0...n).map { |k| 2 * (n - k - 1) }
  end

  cycle_len = y - x + 1
  n2 = n - cycle_len + 2
  res = (0...n2).to_a.reverse.map { |v| 2 * v }
  res += [0] * (n - res.size)

  res2 = Array.new(cycle_len / 2, cycle_len * 2)
  if cycle_len.even?
    res2[-1] = cycle_len
  end
  res2[0] -= 2

  res2.each_with_index do |val, i|
    res[i] += val
  end

  tail1 = x - 1
  tail2 = n - y

  [tail1, tail2].each do |tail|
    next if tail == 0

    i_mx = tail + (cycle_len / 2)
    val_mx = 4 * [(cycle_len - 3) / 2, tail].min
    i_mx2 = i_mx - (1 - (cycle_len % 2))

    res3 = Array.new(i_mx, val_mx)
    res3[0] = 0
    res3[1] = 0

    if cycle_len.even?
      res3[-1] = 0
    end

    (4...val_mx).step(4).each_with_index do |j, idx|
      res3[idx + 2] = j
      res3[i_mx2 - idx - 1] = j
    end

    (1..tail).each do |i|
      res3[i] += 2
    end

    if cycle_len.even?
      mn = cycle_len / 2
      (mn...mn + tail).each do |i|
        res3[i] += 2
      end
    end

    res3.each_with_index do |val, i|
      res[i] += val if i < res.size
    end
  end

  res[0...n]
end