LeetCode 3015 - Count the Number of Houses at a Certain Distance I

LeetCode Problem 3015

Difficulty: 🟡 Medium
Topics: Breadth-First Search, Graph Theory, Prefix Sum

Solution

Here is a complete technical solution guide for LeetCode 3015 - Count the Number of Houses at a Certain Distance I, formatted according to your specifications.

Problem Understanding

The problem describes a simple linear city with n houses numbered from 1 to n. Each consecutive house i and i + 1 are connected by streets, forming a linear path. Additionally, a special street directly connects two houses x and y. The task is to count, for each distance k from 1 to n, the number of ordered pairs of houses (house1, house2) such that the shortest path (minimum number of streets) between them is exactly k.

Inputs:

• n (number of houses, up to 100)
• x, y (special street endpoints, may be equal)

Output:

• A 1-indexed array result of length n where result[k] is the number of pairs of houses with minimum street distance k.

Important points:

• Distance is symmetric but ordered pairs are counted separately, i.e., (i, j) and (j, i) are distinct.
• x and y can be the same house; in that case, the additional street has no effect.
• Constraints are small (n <= 100), which allows O(n²) solutions.

Edge cases to note:

• When x == y, the special street does not change distances.
• Minimum or maximum n values.
• Distances at the extremes (1 and n-1) may have fewer or no pairs.

Approaches

Brute Force

The brute-force approach would construct an adjacency list for all n houses, perform a BFS starting from each house to compute distances to every other house, and then tally counts for each distance. This approach is correct but requires O(n³) time because for each house BFS explores up to n neighbors, repeated n times. Although feasible for n = 100, it is inefficient.

Optimal Approach

The key insight is that the city is almost linear, with only one shortcut street (x, y). For any pair of houses (i, j), the shortest distance is:

distance(i, j) = min(|i - j|, |i - x| + 1 + |y - j|, |i - y| + 1 + |x - j|)

Explanation:

• |i - j| is the direct linear distance.
• |i - x| + 1 + |y - j| is the distance using the special street from x to y.
• |i - y| + 1 + |x - j| is the distance using the special street in the opposite direction.

We can compute this directly for all i < j and double the count for ordered pairs (i, j) and (j, i). This results in a clear O(n²) solution, which is optimal given the constraints.

Comparison table:

Approach	Time Complexity	Space Complexity	Notes
Brute Force BFS	O(n³)	O(n²)	Build adjacency list and BFS from every node
Optimal Direct Formula	O(n²)	O(n)	Compute minimum distance using linear path + special street formula

Algorithm Walkthrough

1. Initialize an array result of length n with zeros. result[k] will store the count for distance k.
2. Iterate over all pairs of houses (i, j) with 1 <= i < j <= n.
3. For each pair, compute the distance using the formula:

dist = min(|i - j|, |i - x| + 1 + |y - j|, |i - y| + 1 + |x - j|)

Here, |i - j| is the linear distance, and the other two terms account for the shortcut street. 4. Increment result[dist] by 2 because we count both (i, j) and (j, i) as valid pairs. 5. After iterating all pairs, return result.

Why it works:

• The formula captures all possible shortest paths: linear distance and via the shortcut.
• By only iterating i < j and doubling, we avoid double-counting while correctly considering ordered pairs.
• The approach is efficient because n ≤ 100 ensures that n² operations are manageable.

Python Solution

from typing import List

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        result = [0] * n
        
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                dist = min(abs(i - j), abs(i - x) + 1 + abs(y - j), abs(i - y) + 1 + abs(x - j))
                result[dist] += 2  # count both (i, j) and (j, i)
        
        return result

Explanation:

• result is initialized with zeros to hold counts for each distance.
• We loop over all i < j to avoid redundant calculations.
• The distance formula checks linear and shortcut paths.
• We increment by 2 to account for ordered pairs.

Go Solution

func countOfPairs(n int, x int, y int) []int {
    result := make([]int, n)
    
    for i := 1; i <= n; i++ {
        for j := i + 1; j <= n; j++ {
            linear := abs(i - j)
            viaXY := abs(i - x) + 1 + abs(y - j)
            viaYX := abs(i - y) + 1 + abs(x - j)
            dist := min(linear, min(viaXY, viaYX))
            result[dist] += 2
        }
    }
    
    return result
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Go-specific notes:

• Slices are used for dynamic arrays.
• Helper functions abs and min are defined for readability.
• The logic mirrors Python closely; iteration uses 1-based indices to match house numbering.

Worked Examples

Example 1: n = 3, x = 1, y = 3

Pairs (i, j) with distances:

i	j	Linear	via XY	via YX	Min	Count Added
1	2	1	3	3	1	2
1	3	2	1	1	1	2
2	3	1	3	3	1	2

result = [6, 0, 0]

Example 2: n = 5, x = 2, y = 4

Pairs and distances:

i	j	Min Distance	Count Added
1	2	1	2
1	3	2	2
1	4	2	2
1	5	3	2
2	3	1	2
2	4	1	2
2	5	2	2
3	4	1	2
3	5	2	2
4	5	1	2

result = [10, 8, 2, 0, 0]

Example 3: n = 4, x = 1, y = 1

result = [6, 4, 2, 0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	We iterate over all pairs (i, j) with i < j, which is ~n²/2. Each distance computation is O(1).
Space	O(n)	We store counts in an array of length n. No additional data structures needed.

Since n ≤ 100, O(n²) operations (~10,000) are easily manageable.

Test Cases

# Provided examples
assert Solution().countOfPairs(3, 1, 3) == [6, 0, 0]  # linear with shortcut spanning ends
assert Solution().countOfPairs(5, 2, 4)