Count the Number of Houses at a Certain Distance I - Solution & Explanation

Problem Overview: You are given n houses arranged in a line with roads between consecutive houses, plus one additional road connecting houses x and y. For every distance d from 1 to n-1, count how many ordered pairs of houses have the shortest path distance exactly equal to d. The challenge is computing shortest paths efficiently for all house pairs.

Approach 1: Dynamic Programming / Distance Enumeration (O(n^2) time, O(n) space)

Treat the houses as a graph with edges between i and i+1, plus the shortcut edge (x, y). For every pair of houses (i, j), compute the shortest distance by comparing three possibilities: the direct linear path |i-j|, a path that goes through x → y, and another through y → x. The key insight is that the extra edge may shorten paths that cross the x-y region. Once the minimum distance is determined, increment the frequency for that distance. This behaves like a dynamic programming style enumeration because each pair reuses the same distance formulas. Time complexity is O(n^2) for evaluating all pairs, and space complexity is O(n) for the result array.

Approach 2: Recursive Approach with Memoization (O(n^2) time, O(n^2) space)

Model the houses as an adjacency list and recursively compute shortest distances between nodes while caching results. Each recursive call explores neighbors and returns the minimum distance to the target. Memoization prevents recomputing distances for the same pair of houses. This mirrors a depth‑first exploration of the breadth-first search distance logic but stores intermediate results in a cache table. After computing the shortest path for each pair, update the distance frequency array. The recursion with memoization ensures each pair is evaluated once, leading to O(n^2) time with O(n^2) space for the memo table.

Optimization Insight: Prefix Counting

Instead of running a full shortest-path search for every pair, the formula-based distance calculation effectively collapses the graph structure into simple arithmetic comparisons. Some implementations further optimize counting using prefix sum style accumulation to update distance ranges efficiently, avoiding repeated pair updates.

Recommended for interviews: The pairwise distance formula (DP-style enumeration) is typically expected. It shows that you recognized the graph structure but avoided expensive BFS from every node. Explaining the brute-force pair check first demonstrates understanding, while the optimized counting approach shows algorithmic maturity.