LeetCode 447 · Hashing

Number of Boomerangs, explained with a picture

Throwers standing equally far apart.

Hashing
▶ Watch it step by step

The problem

Count boomerangs: ordered triples (i, j, k) where j and k are the same distance from i.

Input:  points (0,0) (1,0) (2,0) (1,1)
Output: 8

Picture it

Picture a thrower standing at each point. Group everyone else by their distance to the thrower. Any two people in the same group form 2 ordered boomerangs, so a group of m people contributes m × (m − 1).

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

For each point, count distances in a dictionary. O(n²).

Python solution

def boomerangs(points):
    total = 0
    for p in points:
        dist = Counter()
        for q in points:
            dist[(p[0]-q[0])**2 + (p[1]-q[1])**2] += 1
        for d, m in dist.items():
            total += m * (m - 1)
    return total

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.