Search
⌘K
Get Premium
Leetcode 3017. Count the Number of Houses at a Certain Distance II
Count, for each k, the number of ordered pairs of nodes in a path graph of n houses with one extra shortcut edge (x,y) whose shortest-path distance equals k. The challenge is to efficiently tally pairs for every k by comparing the direct distance |i−j| with distances that go through the shortcut, avoiding O(n^2) pairwise checks.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
All Regions
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.