LeetCode 447: Number of Boomerangs Solution in Python – A Step-by-Step Guide

What Is LeetCode 447: Number of Boomerangs?

In LeetCode 447: Number of Boomerangs, you’re given a list of points points in a 2D plane, where each point is a pair [x, y]. Your task is to count the number of boomerang triplets (i, j, k) where the distance from i to j equals the distance from i to k (j ≠ k). A boomerang is an ordered triplet, so (i, j, k) and (i, k, j) are distinct if j ≠ k. For example, in [(0,0), (1,0), (2,0)], there are 2 boomerangs: (1,0) as the pivot with (0,0) and (2,0) as arms. It’s like finding all the V-shaped patterns where the pivot sees two points at the same range.

Problem Statement

• Input: points (List[List[int]])—list of [x, y] coordinates.
• Output: int—number of boomerang triplets.
• Rules:
• Distance between points (x1, y1) and (x2, y2) is √((x1-x2)² + (y1-y2)²).
• Triplet (i, j, k) is a boomerang if dist(i, j) = dist(i, k), j ≠ k.
• Order matters: (i, j, k) ≠ (i, k, j).

Constraints

• n == points.length.
• 1 <= n <= 500.
• -10^4 <= x, y <= 10^4.

Examples to Get Us Started

• Input: points = [[0,0],[1,0],[2,0]]
• Output: 2 (Boomerangs: [1,0,0], [1,2,0]).
• Input: points = [[1,1],[2,2],[3,3]]
• Output: 2 (Boomerangs: [1,0,2], [1,2,0]).
• Input: points = [[1,1]]
• Output: 0 (Need at least 3 points).

Understanding the Problem: Spotting the V-Shapes

To solve LeetCode 447: Number of Boomerangs in Python, we need to count triplets where one point (the pivot) is equidistant from two others (the arms). Distance is Euclidean, but we can use squared distance to avoid floating-point issues. A naive approach—checking all triplets—would be O(n³), too slow for n = 500. Instead, we can optimize by grouping points by distance from each pivot. We’ll explore:

• Best Solution (Hash Map with Distance Counting): O(n²) time, O(n) space—fast and elegant.
• Alternative Solution (Brute Force Triplets): O(n³) time, O(1) space—simple but inefficient.

Let’s dive into the hash map solution—it’s the boomerang spotter we need.

Best Solution: Hash Map with Distance Counting

Why This Is the Best Solution

The hash map with distance counting is the top pick because it’s O(n²) time and O(n) space, efficiently counting boomerangs by leveraging combinatorics. For each point as a pivot, it maps distances to other points and calculates pairs forming boomerangs in one pass per pivot. It’s like drawing range circles around each point and counting how many pairs land on the same circle—smart and quick!

How It Works

Here’s the strategy:

• Step 1: For each point i as pivot:
• Compute squared distance to all other points j.
• Step 2: Use a hash map to count points at each distance from i.
• Step 3: For each distance with count k ≥ 2:
• Number of boomerangs = k * (k-1) (choose 2 points, order matters).
• Step 4: Sum all boomerangs and return.
• Why It Works:
• k * (k-1) gives permutations of 2 from k (e.g., 3 points → 6 boomerangs).
• One pass per pivot optimizes time.

Step-by-Step Example

Example: points = [[0,0],[1,0],[2,0]]

• Pivot i=0 (0,0):
• Dist to (1,0): (1-0)² + (0-0)² = 1, map = {1:1}.
• Dist to (2,0): (2-0)² = 4, map = {1:1, 4:1}.
• No boomerangs (no counts ≥ 2).
• Pivot i=1 (1,0):
• Dist to (0,0): 1, map = {1:1}.
• Dist to (2,0): 1, map = {1:2}.
• Count = 2: 2 * (2-1) = 2 boomerangs ([1,0,0], [1,2,0]).
• Pivot i=2 (2,0):
• Dist to (0,0): 4, map = {4:1}.
• Dist to (1,0): 1, map = {4:1, 1:1}.
• No boomerangs.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        total = 0

        # For each point as pivot
        for i in range(len(points)):
            distance_map = {}
            x1, y1 = points[i]

            # Compute distances to all other points
            for j in range(len(points)):
                if i != j:
                    x2, y2 = points[j]
                    dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
                    distance_map[dist] = distance_map.get(dist, 0) + 1

            # Count boomerangs for this pivot
            for count in distance_map.values():
                if count >= 2:
                    total += count * (count - 1)

        return total

• Line 3: Initialize total count.
• Line 6-7: For each pivot i, reset map, get coords.
• Line 10-13: Compute squared distance to each j ≠ i, update map.
• Line 16-18: For each distance count ≥ 2, add k * (k-1) boomerangs.
• Line 20: Return total.
• Time Complexity: O(n²)—n pivots, n distances each.
• Space Complexity: O(n)—hash map size.

It’s like a distance radar sweeping the plane!

Alternative Solution: Brute Force Triplet Checking

Why an Alternative Approach?

The brute force triplet method checks all possible triplets—O(n³) time, O(1) space—verifying if each forms a boomerang. It’s slow but intuitive, like manually measuring every V-shape on the map. Good for small n or understanding the basics!

How It Works

• Step 1: Iterate over all triplets (i, j, k).
• Step 2: For each, check if dist(i, j) = dist(i, k) and j ≠ k.
• Step 3: Count valid boomerangs.
• Step 4: Return total.

Step-by-Step Example

Example: points = [[0,0],[1,0],[2,0]]

• Triplets:
• (0,1,2): dist(0,1) = 1, dist(0,2) = 2, no.
• (1,0,2): dist(1,0) = 1, dist(1,2) = 1, yes (1 boomerang).
• (1,2,0): dist(1,2) = 1, dist(1,0) = 1, yes (1 boomerang).
• Others: no matches.
• Result: 2.

Code for Brute Force

Copy codeclass Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def squared_distance(p1, p2):
            return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

        total = 0
        n = len(points)

        # Check all triplets
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i != j and i != k and j != k:
                        if squared_distance(points[i], points[j]) == squared_distance(points[i], points[k]):
                            total += 1

        return total

• Line 3-4: Helper for squared distance.
• Line 7-14: Triple loop, check distances, count matches.
• Time Complexity: O(n³)—all triplets.
• Space Complexity: O(1)—no extra space.

It’s a meticulous map measurer!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n²), efficient, scalable.
• Cons: O(n) space.
• Brute Force (Alternative):
• Pros: O(n³), simple, O(1) space.
• Cons: Slow for n > 100.

Hash map wins for speed.

Edge Cases and More Examples

• Input: [[1,1]] → 0.
• Input: [[0,0],[0,1]] → 0.
• Input: [[0,0],[1,0],[0,1]] → 0 (no equal distances).

Hash map handles all.

Complexity Recap

• Hash Map: Time O(n²), Space O(n).
• Brute Force: Time O(n³), Space O(1).

Hash map is the champ.

Key Takeaways

• Hash Map: Count distances smartly.
• Brute Force: Check every triplet.
• Python Tip: Maps simplify counting—see [Python Basics](/python/basics).

Final Thoughts: Catch Those Boomerangs

LeetCode 447: Number of Boomerangs in Python is a geometric counting puzzle. The hash map solution is your swift boomerang detector, while brute force is a slow surveyor. Want more geometry? Try LeetCode 149: Max Points on a Line or LeetCode 561: Array Partition I. Ready to spot some boomerangs? Head to Solve LeetCode 447 on LeetCode and map it out today—your coding skills are on point!