Solution to LeetCode 1037 - Valid Boomerang

Problem 1037

Abstract / Summary

Three points form a valid boomerang if they are not in a straight line and are not the same point.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1037.py

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        # more readable variables
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]

        # must be distinct
        if x1 == x2 and y1 == y2:
            return False
        if x1 == x3 and y1 == y3:
            return False
        if x2 == x3 and y2 == y3:
            return False

        # point1 becomes the origin
        x2 -= x1
        y2 -= y1
        x3 -= x1
        y3 -= y1

        # degenerated cases
        if x2 == 0 and x3 == 0:
            return False
        if y2 == 0 and y3 == 0:
            return False

        # angles with x axis
        a2 = y2 / (x2 + 10**-10) # avoid div-by-zero
        a3 = y3 / (x3 + 10**-10) # avoid div-by-zero

        # fix rounding issues
        def same(i, j):
            epsilon = 10**-5
            return abs(i - j) < epsilon

        return not same(a2, a3)

Difficulty

This problem is ranked as

easy medium hard

and has an acceptance rate of about 39% (100k+ submissions).

Typical patterns to solve this problem:

Array
Geometry
Math

I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation determines whether three given points form a non-degenerate boomerang, i.e., whether they are three distinct points that are not collinear. The algorithm proceeds through a series of explicit checks that eliminate degenerate configurations before applying a slope-based test. By translating the first point to the origin, the code reduces the problem to a comparison of two direction ratios.

Distinct-point verification

The first logical block ensures that no two input points coincide. By comparing the x and y coordinates of each pair, the function can immediately reject any input where a duplicate point would make a boomerang impossible.

if x1 == x2 and y1 == y2:
    return False
if x1 == x3 and y1 == y3:
    return False
if x2 == x3 and y2 == y3:
    return False

These early exits prevent unnecessary arithmetic on invalid data and keep the subsequent calculations safe.

Translation to the origin

To simplify the geometric reasoning, the algorithm translates the coordinate system so that the first point becomes the origin. This is achieved by subtracting the coordinates of the first point from the other two points.

x2 -= x1
y2 -= y1
x3 -= x1
y3 -= y1

After this transformation, the vectors from the first point to the second and third points are represented directly by (x2, y2) and (x3, y3).

Vertical and horizontal degeneracy checks

Even after translation, a pair of vectors can be collinear if they lie on the same vertical or horizontal line. The code explicitly checks for these cases by testing whether both x-components or both y-components are zero.

if x2 == 0 and x3 == 0:
    return False
if y2 == 0 and y3 == 0:
    return False

These conditions capture the situation where the three points share a common x-coordinate (vertical line) or a common y-coordinate (horizontal line), both of which would make the points collinear.

Slope computation with division-by-zero guard

The core of the collinearity test uses the slope of each vector relative to the x-axis. To avoid a division-by-zero exception when an x-component is zero, a tiny constant (10**-10) is added to the denominator. This technique ensures that the division operation always succeeds while having a negligible impact on the resulting ratio.

a2 = y2 / (x2 + 10**-10)   # avoid div-by-zero
a3 = y3 / (x3 + 10**-10)   # avoid div-by-zero

By normalizing the vectors in this way, the algorithm reduces the collinearity problem to a simple equality comparison of two floating-point numbers.

Rounding tolerance and final decision

Floating-point arithmetic can introduce tiny discrepancies, especially when dealing with division. The function defines a helper same that treats two numbers as equal if their absolute difference is less than a small epsilon (10**-5). This tolerance accounts for rounding errors and ensures that near-identical slopes are considered equal.

def same(i, j):
    epsilon = 10**-5
    return abs(i - j) < epsilon

The final return statement negates the result of same, yielding True only when the slopes differ beyond the tolerance, which indicates that the three points are not collinear and therefore form a valid boomerang.

return not same(a2, a3)

Edge cases addressed

The implementation explicitly handles several edge conditions:

Duplicate points are rejected before any arithmetic.
Purely vertical or purely horizontal alignments are caught by checking zero x- or y-components after translation.
Division by zero is prevented by adding a minuscule offset to the denominator.
Floating-point rounding errors are mitigated through an epsilon-based equality test.

These safeguards collectively ensure that the function behaves correctly across the full range of valid integer inputs.

Performance considerations

The algorithm is optimized for speed through a series of early exits. By returning immediately upon detecting duplicate points or obvious vertical/horizontal degeneracy, the function avoids unnecessary calculations for inputs that are already known to be invalid. The translation step uses in-place subtraction, which eliminates the need for additional data structures. The slope comparison relies on simple arithmetic operations and a lightweight helper function, keeping the runtime overhead minimal. The use of a constant epsilon avoids the overhead of more complex numerical methods while still providing sufficient precision for the problem domain.

written by openai gpt

ELI5 - Simplified Explanation

Imagine having three sparkly stickers and wanting to place them on a big sheet of paper to make a triangle. To form a triangle, the stickers cannot all sit on the very same straight line. If they are in a perfect row, they are like train cars on a track, and that curvy shape called a boomerang cannot be made.

At the start, the code looks at each sticker to see exactly where it is on the paper using numbers. The first thing the code does is double check that no two stickers are sitting right on top of each other at the exact same spot. If two stickers are in the same place, they are like one single sticker, so they cannot make a shape with three corners.

Next, the code pretends to move the first sticker to the very corner of the page. By shifting the other two stickers by the same amount, it simplifies the puzzle so it only has to worry about the relationship between the three spots.

After that, the code checks if the stickers are lined up like buttons on a shirt. It does this by looking at the angle of a line drawn between the stickers. If the angle from the first sticker to the second one is exactly the same as the angle to the third one, it means they are all perfectly flat in a row. If they are not in a row, they are spread out enough to allow the lines to bend and form a boomerang shape.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

n = 27 | median = 7 | μ = 6.44 | σ = 1.62

Complexity Analysis

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

factorial: up to 10 elements
exponential: up to 20 elements
polynomial: a few thousand elements
loglinear: up to 100,000 elements
linear: a few million elements
logarithmic: a billion elements
constant: practically unlimited

generated automatically

Videos

These are a few popular YouTube videos for this problem:

Programming Live with Larry 5 mins

1037. Valid Boomerang (Leetcode Easy)

Math Geeks 3 mins

Leetcode 1037 Valid Boomerang

Elite Code 30 mins

Valid Boomerang | LeetCode | Problem 1037

JSer 5 mins

leetCode 1037 in JavaScript - Valid Boomerang | JSer - algorithm & JavaScript

4 videos did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

2 easy

problem 821: Shortest Distance to a Character
problem 941: Valid Mountain Array

5 medium

problem 553: Optimal Division
problem 593: Valid Square
problem 752: Open the Lock
problem 833: Find And Replace in String
problem 970: Powerful Integers

1 hard

problem 132: Palindrome Partitioning II

9 solutions October 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:

Tech Stack - my development environment and tools
AI - how AI helped me create this website (NOT solving the problems)
Progress - progression over time
Quality - code quality

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go		Rust	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim							C
	everthis			JS
	fsq	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	suxrobGM					C#
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
varunu28	Java