Count the Number of Houses at a Certain Distance II

HARD

Description

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 (house₁, house₂) such that the minimum number of streets that need to be traveled to reach house₂ from house₁ 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⁵
1 <= x, y <= n

Approaches

Checkout 3 different approaches to solve Count the Number of Houses at a Certain Distance II. Click on different approaches to view the approach and algorithm in detail.

Brute-force with Breadth-First Search (BFS)

The most straightforward approach is to model the city and streets as a graph. We can then find the shortest distance between all pairs of houses. A standard algorithm for finding shortest paths in an unweighted graph is Breadth-First Search (BFS).

Algorithm

Create an adjacency list to represent the n houses and their connections.
Add edges for the streets: (i, i+1) for i from 1 to n-1, and the special street (x, y).
Initialize a result array ans of size n with zeros.
For each house start_node from 1 to n: a. Perform a BFS starting from start_node to calculate the shortest distance to all other houses. b. Use a queue and a distance array, initialized to infinity, for the BFS. Set distance[start_node] = 0. c. While the queue is not empty, dequeue a house u, and for each neighbor v, if v is unvisited, update its distance and enqueue it. d. After the BFS from start_node is complete, iterate through all houses j from 1 to n. e. If j != start_node, get the distance d = distance[j]. Increment ans[d-1].
The problem asks for pairs, and our process counts ordered pairs (i, j). The final ans array contains the required counts. Return ans.

First, we construct an explicit graph representation, like an adjacency list, from the input n, x, and y. The graph has n nodes. There are edges (i, i+1) for 1 <= i < n, and an additional edge (x, y).

Then, we iterate through each house i from 1 to n and use it as the starting source for a BFS traversal. The BFS algorithm will find the shortest distance from house i to all other houses j. During the BFS from i, we maintain a distance array. After the BFS is complete, for each house j, we increment the count for the calculated distance dist(i, j) in our result array.

Since the problem asks for the number of pairs (house1, house2), and distance is symmetric (dist(i, j) = dist(j, i)), running BFS from every node i and summing up the distances to all other nodes j correctly counts every ordered pair (i, j).

Complexity Analysis

Time Complexity: O(N^2). We run a BFS from each of the N nodes. Each BFS takes O(N + E) time, where E is the number of edges. In our graph, E is approximately N. So, one BFS is O(N). Repeating this for all N nodes gives a total time complexity of O(N^2). With N up to 10^5, this is not feasible.Space Complexity: O(N). The adjacency list requires O(N) space. The distance array and queue used in each BFS also require O(N) space.

Pros and Cons

Pros:

Simple to understand and implement.
It's a general solution for any graph structure, not just this specific one.

Cons:

Very inefficient for the given constraints. The time complexity is too high.

Code Solutions

Checking out 3 solutions in different languages for Count the Number of Houses at a Certain Distance II. Click on different languages to view the code.

class Solution {
public
  long[] countOfPairs(int n, int x, int y) {
    --x;
    --y;
    if (x > y) {
      int temp = x;
      x = y;
      y = temp;
    }
    long[] diff = new long[n];
    for (int i = 0; i < n; ++i) {
      diff[0] += 1 + 1;
      ++diff[Math.min(Math.abs(i - x), Math.abs(i - y) + 1)];
      ++diff[Math.min(Math.abs(i - y), Math.abs(i - x) + 1)];
      --diff[Math.min(Math.abs(i - 0), Math.abs(i - y) + 1 + Math.abs(x - 0))];
      --diff[Math.min(Math.abs(i - (n - 1)),
                      Math.abs(i - x) + 1 + Math.abs(y - (n - 1)))];
      --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 0) / 2];
      --diff[Math.max(x - i, 0) + Math.max(i - y, 0) + ((y - x) + 1) / 2];
    }
    for (int i = 0; i + 1 < n; ++i) {
      diff[i + 1] += diff[i];
    }
    return diff;
  }
}

Video Solution

Watch the video walkthrough for Count the Number of Houses at a Certain Distance II

Patterns:

Prefix Sum

Data Structures:

Graph