Task · algorithms hard Python ·
Closest pair of points
Return the smallest squared Euclidean distance between two of the points (two different list entries; equal points give 0). There are at least 2 points, with integer coordinates of absolute value up to 10**9. Up to 100,000 points.
Signature
def closest_pair(points: list[list[int]]) -> int:Examples
closest_pair([[0, 0], [3, 4], [1, 1]]) # -> 2
closest_pair([[2, 2], [2, 2]]) # -> 0Plus 7 hidden tests and 2 large-input tests under a time limit; their inputs are not shown. Tasks are given to the models in English.
#1OpenAI GPT-6 Lunasolved · 11 of 11 testsanswer in 5.7 s · runtime 2.2 s · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2 11 ms ✓ closest_pair([[2, 2], [2, 2]])expected 0 1 ms ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.1 s⏱ 1.0 sCode
def closest_pair(points: list[list[int]]) -> int: import random n = len(points) if n < 2: return 0 # Randomized grid: expected linear time, with cell width equal to the # current closest distance. Each cell then has only a small neighborhood # worth checking. pts = [(p[0], p[1]) for p in points] random.shuffle(pts) x0, y0 = pts[0] best = None cells = {} for x, y in pts: if best is None: # A finite initial bound from the first two points. continue if best == 0: return 0 width = max(1, int(best ** 0.5)) cx, cy = x // width, y // width for dx in (-1, 0, 1): for dy in (-1, 0, 1): for px, py in cells.get((cx + dx, cy + dy), ()): d = (x - px) ** 2 + (y - py) ** 2 if d < best: best = d cells.setdefault((cx, cy), []).append((x, y)) if best is None: best = 0 # The loop above needs a starting pair and a grid rebuild whenever the # bound changes; use the divide-and-conquer algorithm for exact robustness. pts.sort() def solve(lo, hi): length = hi - lo if length <= 3: best_d = float("inf") for i in range(lo, hi): for j in range(i + 1, hi): dx = pts[i][0] - pts[j][0] dy = pts[i][1] - pts[j][1] d = dx * dx + dy * dy if d < best_d: best_d = d pts[lo:hi] = sorted(pts[lo:hi], key=lambda p: p[1]) return best_d mid = (lo + hi) // 2 mid_x = pts[mid][0] d = min(solve(lo, mid), solve(mid, hi)) merged = [] i, j = lo, mid while i < mid and j < hi: if pts[i][1] <= pts[j][1]: merged.append(pts[i]) i += 1 else: merged.append(pts[j]) j += 1 merged.extend(pts[i:mid]) merged.extend(pts[j:hi]) pts[lo:hi] = merged strip = [p for p in pts[lo:hi] if (p[0] - mid_x) ** 2 < d] for i in range(len(strip)): j = i + 1 while j < len(strip) and (strip[j][1] - strip[i][1]) ** 2 < d: dx = strip[j][0] - strip[i][0] dy = strip[j][1] - strip[i][1] dd = dx * dx + dy * dy if dd < d: d = dd j += 1 return d return int(solve(0, n))#1Google Gemini 3.8 Flashsolved · 11 of 11 testsanswer in 4.5 s · runtime 2.6 s · $0.0027 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])expected 0 1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.3 s⏱ 1.3 sCode
import math def closest_pair(points: list[list[int]]) -> int: # Sort points by x-coordinate pts = sorted(points, key=lambda p: (p[0], p[1])) n = len(pts) # Check for duplicates easily after sorting for i in range(n - 1): if pts[i][0] == pts[i + 1][0] and pts[i][1] == pts[i + 1][1]: return 0 def solve(l: int, r: int) -> int: if r - l <= 3: min_d = float('inf') for i in range(l, r): p1 = pts[i] for j in range(i + 1, r): p2 = pts[j] d = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 if d < min_d: min_d = d pts[l:r] = sorted(pts[l:r], key=lambda p: p[1]) return min_d mid = (l + r) // 2 mid_x = pts[mid][0] d1 = solve(l, mid) d2 = solve(mid, r) d = min(d1, d2) # Merge step for y-sorting merged = [] i, j = l, mid while i < mid and j < r: if pts[i][1] <= pts[j][1]: merged.append(pts[i]) i += 1 else: merged.append(pts[j]) j += 1 while i < mid: merged.append(pts[i]) i += 1 while j < r: merged.append(pts[j]) j += 1 pts[l:r] = merged strip = [p for p in pts[l:r] if (p[0] - mid_x) ** 2 < d] strip_len = len(strip) for i in range(strip_len): p1 = strip[i] for j in range(i + 1, strip_len): p2 = strip[j] if (p2[1] - p1[1]) ** 2 >= d: break dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 if dist < d: d = dist return d return solve(0, n)#3Qwen3 Coder Nextnot solved · 10 of 11 testsanswer in 5.8 s · runtime 4.3 s · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2 2 ms ✓ closest_pair([[2, 2], [2, 2]])expected 0 2 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ 2.3 sCode
import math import sys from typing import List def closest_pair(points: List[List[int]]) -> int: n = len(points) if n < 2: return 0 # Sort points by x-coordinate points_sorted = sorted(points, key=lambda p: p[0]) # Precompute squared distance to avoid overflow issues and for efficiency def dist_sq(p1, p2): dx = p1[0] - p2[0] dy = p1[1] - p2[1] return dx * dx + dy * dy # Base case: small number of points def closest_pair_util(pts): pts_len = len(pts) if pts_len <= 3: min_dist = float('inf') for i in range(pts_len): for j in range(i + 1, pts_len): d = dist_sq(pts[i], pts[j]) if d < min_dist: min_dist = d return min_dist # Divide mid = pts_len // 2 mid_x = pts[mid][0] left_min = closest_pair_util(pts[:mid]) right_min = closest_pair_util(pts[mid:]) min_dist = min(left_min, right_min) # Build strip of points within min_dist of the dividing line strip = [] for i in range(pts_len): dx = abs(pts[i][0] - mid_x) if dx < min_dist: strip.append(pts[i]) # Sort strip by y-coordinate strip.sort(key=lambda p: p[1]) # Check only points within min_dist in y-direction strip_len = len(strip) for i in range(strip_len): j = i + 1 while j < strip_len and (strip[j][1] - strip[i][1]) < min_dist: d = dist_sq(strip[i], strip[j]) if d < min_dist: min_dist = d j += 1 return min_dist return closest_pair_util(points_sorted)Second try
not solved · 9 of 11 testsanswer in 11 s · $0.0004The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])expected 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 9 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ time limit exceeded⏱ time limit exceededCode
import math def closest_pair(points: list[list[int]]) -> int: n = len(points) if n < 2: return 0 # Sort points by x-coordinate points_sorted = sorted(points, key=lambda p: p[0]) # Precompute squared distance def dist_sq(p1, p2): dx = p1[0] - p2[0] dy = p1[1] - p2[1] return dx * dx + dy * dy # Base case for small number of points def brute_force(pts): min_dist = float('inf') for i in range(len(pts)): for j in range(i + 1, len(pts)): d = dist_sq(pts[i], pts[j]) if d < min_dist: min_dist = d return min_dist # Recursive divide and conquer def closest_util(pts): pts_len = len(pts) if pts_len <= 3: return brute_force(pts) mid = pts_len // 2 mid_x = pts[mid][0] left_min = closest_util(pts[:mid]) right_min = closest_util(pts[mid:]) d = min(left_min, right_min) # Build strip strip = [] for i in range(pts_len): if abs(pts[i][0] - mid_x) < d: strip.append(pts[i]) # Sort by y-coordinate strip.sort(key=lambda p: p[1]) # Check points in strip strip_len = len(strip) for i in range(strip_len): j = i + 1 while j < strip_len and (strip[j][1] - strip[i][1]) < d: d = min(d, dist_sq(strip[i], strip[j])) j += 1 return d return int(closest_util(points_sorted))#4MoonshotAI Kimi K2.7 Codenot solved · 0 of 11 testsanswer in 60 s · runtime <1 ms · $0.02 SyntaxError: '[' was never closed (line 69)
✗ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2SyntaxError: '[' was never closed (line 69) — ✗ closest_pair([[2, 2], [2, 2]])expected 0SyntaxError: '[' was never closed (line 69) — ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxErrorCode
from operator import itemgetter def closest_pair(points: list[list[int]]) -> int: px = sorted(points) if len(px) < 2: return 0 ykey = itemgetter(1) def merge(a, b): i = 0 j = 0 la = len(a) lb = len(b) out = [] ap = out.append while i < la and j < lb: ai = a[i] bj = b[j] if ai[1] <= bj[1]: ap(ai) i += 1 else: ap(bj) j += 1 if i < la: out += a[i:] if j < lb: out += b[j:] return out def rec(p): n = len(p) if n == 2: (x0, y0), (x1, y1) = p dx = x0 - x1 dy = y0 - y1 if y0 <= y1: return dx * dx + dy * dy, p return dx * dx + dy * dy, [p[1], p[0]] if n == 3: (x0, y0), (x1, y1), (x2, y2) = p dx = x0 - x1 dy = y0 - y1 d = dx * dx + dy * dy dx = x0 - x2 dy = y0 - y2 t = dx * dx + dy * dy if t < d: d = t dx = x1 - x2 dy = y1 - y2 t = dx * dx + dy * dy if t < d: d = t return d, sorted(p, key=ykey) m = n >> 1 dl, yl = rec(p[:m]) if dl == 0: return 0, [] dr, yr = rec(p[m:]) if dr == 0: return 0, [] d = dl if dl < dr else dr ys = merge(yl, yr) mx = p[m][0] strip = [q for q in ys if (q[0] - mx)Second try
solved · 11 of 11 testsanswer in 6.4 s · $0.0031The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])expected 2 1 ms ✓ closest_pair([[2, 2], [2, 2]])expected 0 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.2 s⏱ 1.4 sCode
from operator import itemgetter def closest_pair(points: list[list[int]]) -> int: px = sorted(points) ykey = itemgetter(1) def merge(a, b): i = 0 j = 0 la = len(a) lb = len(b) out = [] ap = out.append while i < la and j < lb: ai = a[i] bj = b[j] if ai[1] <= bj[1]: ap(ai) i += 1 else: ap(bj) j += 1 if i < la: out += a[i:] if j < lb: out += b[j:] return out def rec(p): n = len(p) if n == 2: (x0, y0), (x1, y1) = p dx = x0 - x1 dy = y0 - y1 if y0 <= y1: return dx * dx + dy * dy, p return dx * dx + dy * dy, [p[1], p[0]] if n == 3: (x0, y0), (x1, y1), (x2, y2) = p dx = x0 - x1 dy = y0 - y1 d = dx * dx + dy * dy dx = x0 - x2 dy = y0 - y2 t = dx * dx + dy * dy if t < d: d = t dx = x1 - x2 dy = y1 - y2 t = dx * dx + dy * dy if t < d: d = t return d, sorted(p, key=ykey) m = n >> 1 dl, yl = rec(p[:m]) if dl == 0: return 0, [] dr, yr = rec(p[m:]) if dr == 0: return 0, [] d = dl if dl < dr else dr ys = merge(yl, yr) mx = p[m][0] strip = [q for q in ys if (q[0] - mx) * (q[0] - mx) < d] ln = len(strip) for i in range(ln): xi, yi = strip[i] for j in range(i + 1, min(i + 8, ln)): xj, yj = strip[j] dy = yi - yj dd = dy * dy if dd >= d: break dx = xi - xj dd += dx * dx if dd < d: d = dd return d, ys return rec(px)[0]
Tokens cost: $0.03 · How rounds are run and scored →