Problem Description
Given n houses numbered 1 through n connected in a line (with a street between house i and i+1) and an extra street connecting house x and house y (which may be the same house), we must—for each k from 1 to n—count the total number (ordered) of pairs of houses (house₁, house₂) whose minimum‑number of streets traveled equals k. In other words, for any two distinct houses i and j (order matters), the effective distance is given by the minimum between the direct (|i − j|) and the “shortcut” distance computed using the extra edge. We return a 1-indexed array result of length n where result[k] is the total count of such pairs that have distance exactly k.
Key Insights
- The natural distance between houses i and j is |i − j| (with 1–step increments along the line) and initially, there are 2*(n − k) ordered pairs with direct distance k.
- When using the extra street, one may “shortcut” the route by going from house i to x (or y), taking the extra edge (which counts as 1) and then going from y (or x) to house j.
- Let dx = min(x,y) and dy = max(x,y). For any pair with i < j in the “rectangle region” (i from 1 to dx and j from dy to n) the shortcut distance becomes: (dx+1 − i) + (j − dy) (i.e. going from i to dx, taking the edge, then from dy to j).
- Notice that for these rectangle pairs the direct distance is j − i whereas the shortcut distance is exactly (j − i) minus a constant gap = (dy − dx − 1). (This gap is positive only when dy > dx+1; otherwise the extra edge does not shorten the distance.)
- Thus, for each pair in the rectangle the effective distance “shifts” from d = (j − i) to d - gap.
- Instead of explicitly iterating over every pair (which would be too slow when n is large), we can count the number of rectangle pairs that have a given direct distance d. For a fixed d, the number of pairs with i in [1,dx] and j = i+d with j in [dy, n] is: f(d) = max(0, min(dx, n − d) − max(1, dy − d) + 1).
- We then “move” these counts: subtract 2f(d) from the answer at index d (since we originally assumed the pair uses the direct path) and add 2f(d) at index d - gap (their true effective distance), for every possible d.
- Finally, note that all counts are for ordered pairs so every unordered pair contributes twice.
Space and Time Complexity
Time Complexity: O(n), since we loop over distances from 1 to n‑1 and perform O(1) work per distance. Space Complexity: O(n), due to the result array.
Solution
The strategy is to first assume every pair of houses is connected by the direct path only. For a given k (1 ≤ k ≤ n−1) there are 2*(n−k) ordered pairs with distance k. Then, we “correct” the counts for those pairs that can instead use the extra street to reduce the travel distance. Using dx = min(x,y) and dy = max(x,y), all pairs with i from 1 to dx and j from dy to n have an alternative “shortcut” distance equal to (j − i − (dy − dx − 1)). We count for every possible direct distance d the number of such pairs (call that count f(d)) and adjust our answer array accordingly by subtracting 2f(d) from index d and adding 2f(d) to index (d − gap), where gap = (dy − dx − 1).
This conversion is done in constant time per possible difference, and all indices are carefully bounded between 1 and n−1. Finally, we output an array (of length n) where index n is always zero.