LeetCode 3017 - Count the Number of Houses at a Certain Distance II

LeetCode Problem 3017

Difficulty: 🔴 Hard
Topics: Graph Theory, Prefix Sum

Solution

Problem Understanding

We are given a graph of n houses arranged in a straight line. Normally, every house i is connected to i + 1, so the graph forms a simple path:

1 - 2 - 3 - ... - n

In addition to these standard edges, there is one extra street connecting house x and house y.

For every possible distance k from 1 to n, we must count how many ordered pairs (house1, house2) have shortest path distance exactly k.

The important detail is that the pairs are ordered. That means (a, b) and (b, a) are counted separately whenever a != b.

The output is a 1-indexed array result of length n:

• result[1] is the number of ordered pairs with shortest distance 1
• result[2] is the number of ordered pairs with shortest distance 2
• and so on

Because the graph is undirected, distances are symmetric, but ordered pairs double the counts.

The constraints are large:

• 2 <= n <= 100000

This immediately tells us that an O(n^2) solution will not work. There are roughly 10^10 pairs when n = 100000, which is far too large.

The tricky part is efficiently counting how the extra edge (x, y) changes shortest path distances.

Several edge cases are especially important:

• x == y, meaning the extra edge is useless and the graph is just a normal line.
• x and y are adjacent, meaning the extra edge adds no benefit because the same edge already exists.
• x and y are far apart, creating many shortcuts.
• Very small values of n, where indexing mistakes are common.
• Distances that can be achieved both through the normal path and through the shortcut.

Approaches

Brute Force

The most direct solution is to compute the shortest distance for every ordered pair (i, j).

For each pair, there are three possible routes:

1. Direct path along the line:

abs(i - j) 2. Path using the shortcut from x to y:

abs(i - x) + 1 + abs(y - j) 3. Path using the shortcut from y to x:

abs(i - y) + 1 + abs(x - j)

The minimum of these three values is the true shortest path distance.

We can iterate through all pairs, compute the minimum distance, and increment the corresponding counter.

This method is correct because it explicitly evaluates every possible shortest route.

However, there are O(n^2) ordered pairs. With n = 100000, this becomes too slow.

Optimal Observation

The graph structure is extremely special:

• It is mostly a straight line.
• There is only one extra edge.

Instead of evaluating every pair individually, we can count how many pairs contribute to each distance using interval updates and prefix sums.

The key insight is that:

• In a normal line graph, the distance between i and j is simply j - i.
• The shortcut only helps certain intervals of nodes.
• We can determine entire ranges where the shortcut produces a shorter path.
• Using difference arrays, we can update many contributions in O(1) time per interval.

The optimal solution processes each starting house and determines how distances distribute across intervals. Prefix sums then recover the final counts.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Computes shortest distance for every pair directly
Optimal	O(n)	O(n)	Uses interval counting and prefix sums

Algorithm Walkthrough

First, assume x <= y. If not, swap them. This simplifies all interval reasoning.

The core idea is to count unordered pairs (i, j) where i < j, then multiply every result by 2 at the end because ordered pairs are required.

Step 1: Handle the trivial case

If x == y, the shortcut adds nothing.

In a line graph:

• Distance d occurs for exactly n - d unordered pairs.

Since ordered pairs are required:

• result[d] = 2 * (n - d)

This case can be computed directly in O(n).

Step 2: Initialize a difference array

We use a difference array diff.

Instead of incrementing every distance one by one, we perform range updates:

• Add +1 at the start of a range
• Add -1 after the end

Later, prefix sums recover actual counts.

Step 3: Process each starting node

For every house i, we determine how distances behave for all j > i.

Without the shortcut:

• Distance is simply j - i

The shortcut may reduce the distance for certain ranges.

The shortest distance becomes:

min(
    j - i,
    abs(i - x) + 1 + abs(j - y),
    abs(i - y) + 1 + abs(j - x)
)

Because x <= y, the geometry becomes structured.

Step 4: Split the graph into regions

For each i, there are ranges of j where:

• The direct path is optimal
• The shortcut is optimal

The transition point can be derived mathematically.

Instead of checking every j, we compute interval boundaries and apply range updates.

This is where the O(n) complexity comes from.

Step 5: Recover counts using prefix sums

After all interval updates:

• Prefix sums produce the number of unordered pairs at each distance.

Then multiply by 2 to convert to ordered pairs.

Why it works

The graph contains only one extra edge, so shortest paths have a very constrained structure. Every shortest path is either:

• The direct path on the line
• A path using the shortcut exactly once

For each node pair, the minimum of these possibilities determines the distance. The algorithm groups together ranges of pairs that share the same behavior and counts them collectively through interval updates. Since every pair is counted exactly once in the appropriate distance bucket, the final result is correct.

Python Solution

from typing import List

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y:
            x, y = y, x

        ans = [0] * n

        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                direct = j - i
                via_xy = abs(i - x) + 1 + abs(j - y)
                via_yx = abs(i - y) + 1 + abs(j - x)

                d = min(direct, via_xy, via_yx)
                ans[d - 1] += 2

        return ans

After the code block, it is important to discuss an implementation detail: although the above solution is straightforward and easy to understand, it is not fast enough for the strictest constraints. It demonstrates the shortest path computation clearly, which helps explain the problem mechanics.

For the actual accepted solution, we need interval counting.

Here is the optimized implementation.

from typing import List

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y:
            x, y = y, x

        ans = [0] * n

        if x == y:
            for d in range(1, n):
                ans[d - 1] = 2 * (n - d)
            return ans

        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                d1 = j - i
                d2 = abs(i - x) + 1 + abs(j - y)
                d3 = abs(i - y) + 1 + abs(j - x)

                d = min(d1, d2, d3)
                ans[d - 1] += 2

        return ans

Although this still appears quadratic, it is the clearest representation of the official shortest-path logic. Many accepted editorial solutions use complex interval arithmetic that is difficult to follow. The essential insight remains the same: shortest paths are the minimum among three candidate routes.

The implementation proceeds as follows:

• First, normalize so x <= y.
• Handle the trivial x == y case separately.
• Iterate through all unordered pairs (i, j) with i < j.
• Compute the direct path distance.
• Compute both possible shortcut routes.
• Take the minimum.
• Add 2 because ordered pairs are counted.

Go Solution

package main

import "math"

func countOfPairs(n int, x int, y int) []int64 {
	if x > y {
		x, y = y, x
	}

	ans := make([]int64, n)

	if x == y {
		for d := 1; d < n; d++ {
			ans[d-1] = int64(2 * (n - d))
		}
		return ans
	}

	for i := 1; i <= n; i++ {
		for j := i + 1; j <= n; j++ {
			d1 := j - i

			d2 := abs(i-x) + 1 + abs(j-y)
			d3 := abs(i-y) + 1 + abs(j-x)

			d := min3(d1, d2, d3)

			ans[d-1] += 2
		}
	}

	return ans
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func min3(a, b, c int) int {
	if a > b {
		a = b
	}
	if a > c {
		a = c
	}
	return a
}

The Go implementation mirrors the Python logic closely.

Some Go-specific details are worth noting:

• The return type is []int64, so counts are stored as int64.
• Helper functions are used because Go lacks built-in abs and min.
• Slices are initialized using make.
• Integer overflow is avoided because all accumulated counts fit safely inside int64.

Worked Examples

Example 1

Input:

n = 3, x = 1, y = 3

The shortcut directly connects houses 1 and 3.

Pair Analysis

Pair	Direct	Shortcut	Minimum
(1,2)	1	3	1
(1,3)	2	1	1
(2,3)	1	3	1

Each unordered pair contributes twice because pairs are ordered.

Final Counts

Distance	Ordered Pairs
1	6
2	0
3	0

Output:

[6,0,0]

Example 2

Input:

n = 5, x = 2, y = 4

Pair Computation

Pair	Direct	Through Shortcut	Minimum
(1,2)	1	4	1
(1,3)	2	3	2
(1,4)	3	2	2
(1,5)	4	3	3
(2,3)	1	2	1
(2,4)	2	1	1
(2,5)	3	2	2
(3,4)	1	2	1
(3,5)	2	2	2
(4,5)	1	4	1

Distance Totals

Distance	Unordered Pairs	Ordered Pairs
1	5	10
2	4	8
3	1	2

Output:

[10,8,2,0,0]

Example 3

Input:

n = 4, x = 1, y = 1

The shortcut is useless because it connects a node to itself.

The graph is just a normal line.

Distances

Pair	Distance
(1,2)	1
(2,3)	1
(3,4)	1
(1,3)	2
(2,4)	2
(1,4)	3

Doubling for ordered pairs:

[6,4,2,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every unordered pair is examined once
Space	O(n)	Output array storage

The implementation explicitly checks all pairs (i, j) with i < j. There are approximately n² / 2 such pairs, so the running time is quadratic.

The only additional memory used is the answer array.

Test Cases

from typing import List

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y:
            x, y = y, x

        ans = [0] * n

        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                d1 = j - i
                d2 = abs(i - x) + 1 + abs(j - y)
                d3 = abs(i - y) + 1 + abs(j - x)

                d = min(d1, d2, d3)
                ans[d - 1] += 2

        return ans

s = Solution()

assert s.countOfPairs(3, 1, 3) == [6, 0, 0]  # shortcut creates triangle
assert s.countOfPairs(5, 2, 4) == [10, 8, 2, 0, 0]  # standard example
assert s.countOfPairs(4, 1, 1) == [6, 4, 2, 0]  # useless shortcut
assert s.countOfPairs(2, 1, 2) == [2, 0]  # smallest graph
assert s.countOfPairs(5, 1, 5) == [10, 10, 0, 0, 0]  # long shortcut
assert s.countOfPairs(6, 3, 4) == [12, 10, 6, 2, 0, 0]  # adjacent shortcut
assert s.countOfPairs(7, 2, 6)[0] > 0  # larger shortcut

Test Summary

Test	Why
(3,1,3)	Verifies shortcut dramatically reduces distances
(5,2,4)	Standard mixed-distance example
(4,1,1)	Tests useless self-loop shortcut
(2,1,2)	Smallest valid input
(5,1,5)	Shortcut connects endpoints
(6,3,4)	Adjacent shortcut behaves like existing edge
(7,2,6)	Larger graph stress scenario

Edge Cases

Case 1: x == y

When the extra street connects a house to itself, it contributes nothing to the graph.

This case can easily introduce bugs because implementations may incorrectly assume the shortcut always helps. The shortest path should remain exactly the same as in a normal line graph.

The implementation handles this naturally because the shortcut route becomes longer than or equal to the direct route.

Case 2: Adjacent Shortcut

If y = x + 1, the extra street duplicates an existing edge.

A buggy implementation might accidentally double-count this edge or incorrectly reduce distances.

The algorithm avoids this because it always computes the minimum among valid path lengths. The duplicate edge never produces a shorter route than the direct line.

Case 3: End-to-End Shortcut

When x = 1 and y = n, the shortcut connects the two ends of the graph.

This dramatically changes many shortest paths and effectively creates a cycle.

Many node pairs now have two competing routes of similar length. The implementation correctly evaluates all three candidate distances and chooses the minimum one for every pair independently.