Problem
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
xwith 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 _a1-indexed array _result
of lengthn
whereresult[k]
_represents thetotal 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.
Examples
Example 1
|
|
Example 2
|
|
Example 3
|
|
Constraints
2 <= n <= 10^5
1 <= x, y <= n
Solution
Method 1 – Shortest Path Enumeration (Math)
Intuition
For each pair of houses (i, j), the shortest path is either the direct path (|i-j|) or the path using the extra street (|i-x| + 1 + |j-y| or |i-y| + 1 + |j-x|). We count the number of pairs for each possible distance.
Approach
- For each pair (i, j) with i < j, compute the shortest distance:
- Direct: |i-j|
- Via extra street: min(|i-x| + 1 + |j-y|, |i-y| + 1 + |j-x|)
- The minimum of the two is the shortest path.
- For each distance k, count the number of pairs with that distance.
- Since the graph is undirected, count both (i, j) and (j, i) (multiply by 2).
- Return the result array.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
, since we check all pairs of houses. - 🧺 Space complexity:
O(n)
, for the result array.