AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Geometry coding problems

Geometry problems put points, lines and shapes on a plane, usually with integer coordinates: are these points on one line, which are closest to the origin, how many lie on the best line, what is the smallest rectangle their corners make.

22 problems · 7 easy · 10 medium · 5 hard · judged by hidden tests in 13 languages

22problems

7 easy

10 medium

5 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Check If It Is a Straight Line

How it works

Geometry, step by step

Convex hull of a point set, with Andrew's monotone chain

points = (3, 0), (0, 2), (5, 3), (2, 4), (6, 1), (1, 0), (4, 3)

ABCDEFGcross(o, a, b) = (a − o) × (b − o)> 0: left turn, keep · ≤ 0: right turn, poplowerupperAB

Sort the points by x and name them A to G in that order. Andrew's monotone chain builds the lower hull left to right and the upper hull right to left, keeping only left turns; the sign of a cross product tells which way a turn goes.

0:01 / 0:42Step 1 of 12
Transcript · 12 steps

Study plan

Learn geometry in 8 days

14 of the 22 Geometry problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 8 in the full list below are practice at your own pace. Then move on to Brainteaser.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Brainteaser

Geometry Coding Problems: 22 Questions with Solutions

22 geometry coding problems — 7 easy · 10 medium · 5 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 22
  • By difficulty: 7 easy · 10 medium · 5 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Geometry problems put points, lines and shapes on a plane, usually with integer coordinates: are these points on one line, which are closest to the origin, how many lie on the best line, what is the smallest rectangle their corners make. The ideas are short — slopes, cross products, squared distances, the diagonal moves of a king — and the difficulty is exactness. The problems here practise keeping every comparison in integers, so that no rounding decides what the coordinates settle exactly.

How geometry works, step by step

ABCDEFGhull: A B D G F CO(n log n) for the sort, O(n) for the chainslowerupperABDGGFCA
Convex hull of a point set, with Andrew's monotone chain. Example: points = (3, 0), (0, 2), (5, 3), (2, 4), (6, 1), (1, 0), (4, 3)
  1. Sort the points by x and name them A to G in that order. Andrew's monotone chain builds the lower hull left to right and the upper hull right to left, keeping only left turns; the sign of a cross product tells which way a turn goes.
  2. Adding C: A → B → C turns counter-clockwise (cross = 6), so B stays and C joins. A counter-clockwise turn keeps the chain bending one way, which is what convex means.
  3. Adding D: B → C → D turns clockwise (cross = −8), so C is popped; A → B → D turns counter-clockwise (cross = 4), so B stays and D joins. A clockwise turn means C lies on the inner side of the segment BD, so it cannot be a corner of the hull.
  4. Adding E: B → D → E turns counter-clockwise (cross = 6), so D stays and E joins.
  5. Adding F: D → E → F turns clockwise (cross = −3), so E is popped; B → D → F turns counter-clockwise (cross = 6), so D stays and F joins.
  6. Adding G: D → F → G turns clockwise (cross = −7), so F is popped; B → D → G turns counter-clockwise (cross = 2), so D stays and G joins.
  7. The lower hull A → B → D → G is done; the upper pass restarts from G and F. Adding E: G → F → E turns counter-clockwise (cross = 2), so F stays and E joins.
  8. Adding D: F → E → D turns counter-clockwise (cross = 3), so E stays and D joins.
  9. Adding C: E → D → C turns clockwise (cross = −7), so D is popped; F → E → C turns clockwise (cross = −1), so E is popped; G → F → C turns counter-clockwise (cross = 5), so F stays and C joins.
  10. Adding B: F → C → B turns counter-clockwise (cross = 13), so C stays and B joins.
  11. Adding A: C → B → A turns clockwise (cross = −6), so B is popped; F → C → A turns counter-clockwise (cross = 8), so C stays and A joins.
  12. The hull is A → B → D → G → F → C: the lower chain plus the upper one, which share the end points. E lies inside. Sorting costs O(n log n); each point is pushed and popped at most once per chain, so the scan itself is O(n).

Geometry study plan

14 of the 22 Geometry problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 8 in the full list below are practice at your own pace. Then move on to Brainteaser.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Brainteaser

Geometry: the essentials

When to reach for it

Points as [x, y], circles as [x, y, r], rectangles or heights on a grid, with a question about collinearity, distance, area or containment. Integer coordinates, up to 10⁴ or 10⁹, say that the exact answer needs no floating point.

The pattern

Replace division and square roots with multiplication. Three points are collinear when the cross product of b - a and c - a is zero — no slope, no vertical special case — and its sign tells a left turn from a right. Compare distances by their squares: dx² + dy² ranks points as the distance does, and a point is inside or on a circle when dx² + dy² ≤ r². To group points by slope, reduce the direction by its gcd, fix its sign and use it as a Hash Table key.

from math import gcd

def cross(o, a, b):                 # > 0 left turn, < 0 right turn, 0 collinear
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def direction(p, q):                # slope from p to q as an exact key, p != q
    dx, dy = q[0] - p[0], q[1] - p[1]
    g = gcd(dx, dy)
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):
        dx, dy = -dx, -dy           # one sign, so p→q and q→p agree
    return dx, dy

Cost

Every pair of points is O(n²); with a map of directions per anchor point, Max Points on a Line is O(n²) time and O(n) space.

Common mistakes

  • Floating-point slopes: dy / dx fails on vertical lines, close slopes can round alike, and Java's Double keys tell 0.0 from −0.0.
  • Overflow: with coordinates up to 10⁹, a cross product or squared distance reaches about 10¹⁸; use 64-bit integers.
  • Duplicate points have no direction between them; count them apart and add them to every line through that point.
  • Reading "inside or on" as <: a point on the boundary satisfies <=.

Start with

All geometry problems

Easy (7)

Medium (10)

Hard (5)

Companies that ask geometry problems

Next topic: Brainteaser