Sweep line, offline queries and geometry

The sweep-line recipe: events, a tie-break and an active set

Picture a vertical line that starts at the far left of the plane and moves right. Almost everywhere nothing happens as it moves: the same shapes are under it a moment later as a moment ago. It only matters at a handful of places, where a shape begins or ends. A sweep line is the habit of looking only at those places. You stop at each one, update what the line is touching, and answer the question from that. The line can just as well be a timeline, a pointer over sorted queries, or a row scanning a grid; the idea is to sort the moments that matter and keep a summary of "what is active right now".

The intervals chapter already uses this with the simplest possible summary, a counter: meeting rooms, car pooling and difference arrays are all sweeps where the active set is just a number. This chapter starts where a number stops being enough. The recipe is the same four steps every time:

1. Make events. Turn each object into the coordinates where it starts or stops mattering, carrying whatever the update needs (a height, a weight, an index).
2. Sort the events, with an explicit rule for what happens when two events share a coordinate.
3. Walk the events in order and update the active set.
4. Read the answer from the active set at the right moments: after every event, after every group of events at one coordinate, or between events when the answer accumulates over a stretch.

What changes from problem to problem is the structure that holds the active set. Choose it by the question you will ask of the set:

The tie-break is part of the algorithm

When a start and an end fall on the same coordinate, which one is processed first changes the answer, and the right choice comes from the question and not from a trick. Ask whether a thing that ends at x is still there at x. If the interval is closed, [1, 2] still contains 2, so a start at 2 should see it: process starts first. If it is half-open, [1, 2) no longer contains 2, so process ends first, which is what the intervals chapter does. Writing the order as named numbers keeps the choice visible in the code:

const START = 0, END = 1; // the order of these two numbers IS the tie-break

function maxOverlapClosed(intervals) {
  const events = [];
  for (const [from, to] of intervals) {
    events.push([from, START]);
    events.push([to, END]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // same time: starts first, so [1, 2] and [2, 3] touch
  let active = 0, best = 0;
  for (const [, kind] of events) {
    active += kind === START ? 1 : -1;
    best = Math.max(best, active);
  }
  return best;
}

For [[1, 2], [2, 3]] the events sort to (1, START), (2, START), (2, END), (3, END), so the count reaches 2: the two closed intervals share the point 2. Swapping the two constants gives 1, the answer for half-open intervals. The sort is O(n log n) and the walk is linear.

There are two ways to avoid tie-breaking altogether, and both appear below. One is to process all events at a coordinate before reading the answer, as the skyline does. The other is to read the answer only between coordinates, as the area sweep does: between two events at the same coordinate no width passes, so their order cannot change the total.

The skyline problem: a heap with lazy deletion

Each building is [left, right, height]: it stands on the ground from left up to, but not including, right. Draw them all and trace the outline against the sky. Report that outline as the list of key points [x, height], where each key point is the left end of a flat stretch, and the last one has height 0. The rule that makes the answer unique: when two neighbouring stretches have the same height, they are one stretch, so no key point appears between them.

Why the obvious way fails. You could compute the height at every integer x by scanning all buildings, then compress runs. That costs the width of the whole range times n, and the range can be 2³¹ wide.

The idea. The height at x is the maximum height over the buildings with left ≤ x < right. That maximum can only change at a coordinate where some building starts or ends, so the outline is decided by at most 2n coordinates. Sweep over them in order, keep the buildings covering the line in a structure that can say "the tallest", and whenever the tallest height differs from the height just before, record [x, height].

The active set needs three operations: insert a building when its left edge is reached, read the maximum height, and remove a building when its right edge is passed. A heap does the first two in O(log n) and O(1), but it cannot remove an arbitrary entry cheaply. The fix is lazy deletion: do not remove it. Leave the dead building where it is, and discard it only when it reaches the top, where it is about to be read. This is correct for a simple reason: you only ever read the top. A dead entry underneath a live top cannot change the maximum, and a dead entry on top is thrown away before you look. It also requires that death is permanent, and it is: the sweep only moves right, so a building that has ended never comes back.

class Heap {
  constructor(before) {
    this.before = before; // before(a, b) is true when a must leave the heap earlier than b
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!this.before(a[i], a[parent])) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1, right = left + 1;
        let first = i;
        if (left < a.length && this.before(a[left], a[first])) first = left;
        if (right < a.length && this.before(a[right], a[first])) first = right;
        if (first === i) break;
        [a[first], a[i]] = [a[i], a[first]];
        i = first;
      }
    }
    return top;
  }
}

function getSkyline(buildings) {
  const xs = [...new Set(buildings.flatMap(([left, right]) => [left, right]))].sort((a, b) => a - b);
  const byLeft = [...buildings].sort((a, b) => a[0] - b[0]);
  const alive = new Heap((a, b) => a[0] > b[0]); // entries [height, right]; the tallest leaves first
  const skyline = [];
  let next = 0, previous = 0;
  for (const x of xs) {
    while (next < byLeft.length && byLeft[next][0] <= x) {
      const [, right, height] = byLeft[next++];
      alive.push([height, right]);
    }
    while (alive.size > 0 && alive.peek()[1] <= x) alive.pop(); // lazy deletion: only a dead TOP has to go
    const height = alive.size > 0 ? alive.peek()[0] : 0;
    if (height !== previous) {
      skyline.push([x, height]);
      previous = height;
    }
  }
  return skyline;
}

The heap holds [height, right] pairs, so a building carries its own end with it, and "dead" simply means right <= x. The comparison is <= because the building is half-open: at x === right it no longer covers anything. All buildings that start at or before x are pushed first and all dead tops are popped next, and only then is the height read. That order is what makes ties harmless: a building ending at x and another starting at x are both dealt with before the single read at x.

Dry run: [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]

The answer is [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]. Watch x = 9: the building [10, 9] has ended, but it sits under [12, 12], so nobody notices and nobody pays for it. It is only removed at x = 12, when it surfaces together with the building on top of it. That is lazy deletion working as intended.

Cost. Sorting the coordinates is O(n log n). Each building is pushed once and popped at most once, each in O(log n), so the sweep is O(n log n) too. The heap never holds more than n entries, so the space is O(n).

The ordered-set alternative. Instead of a heap you can keep the heights of the active buildings in a sorted multiset: insert at the left edge, remove that exact height at the right edge, read the largest. Nothing is left dead, so there is no lazy deletion, and the same O(n log n) holds. JavaScript has no built-in ordered set, which is why the heap version is the one to write in an interview; the ordered structures chapter builds the structure if you want the other version.

Offline queries: answer them in the order that suits you

A static pile of intervals and a list of questions about it: how many cover this time, which one is the smallest that contains this point. Answering each question by scanning the intervals costs O(n) per question and O(n · q) in all. The way out is the word offline. If you get all the questions before you must answer any, you are free to answer them in any order you like, as long as each answer is written back to its original slot. The order worth choosing is usually sorted by the thing being asked, because then the sweep above applies: the "line" is the query value moving upward.

To answer in a different order, sort indices rather than values: order = queries.map((_, i) => i).sort((a, b) => queries[a] - queries[b]). Then answer[order[k]] is where the k-th smallest query's answer goes. Sorting the query values themselves loses the positions and you cannot undo it.

Number of flowers in full bloom: a count is a difference of two counts

Each flower is in bloom on the closed range [start, end]. For each visitor arriving at time t, report how many flowers are in bloom. A flower is in bloom at t when start ≤ t and t ≤ end. Count the flowers that have opened by t (start ≤ t) and subtract the ones that have closed before t (end < t). A flower that closed before t opened before t too, so every subtracted flower was counted, and what remains is exactly the flowers in bloom. Each of the two counts is "how many values in a sorted array are at most (or below) t", which is a binary search.

function countAtMost(sorted, t) {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] <= t) lo = mid + 1;
    else hi = mid;
  }
  return lo; // how many values are <= t
}

function countBelow(sorted, t) {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] < t) lo = mid + 1;
    else hi = mid;
  }
  return lo; // how many values are < t
}

function fullBloomFlowers(flowers, people) {
  const starts = flowers.map(([start]) => start).sort((a, b) => a - b);
  const ends = flowers.map(([, end]) => end).sort((a, b) => a - b);
  return people.map((t) => countAtMost(starts, t) - countBelow(ends, t)); // opened by t, minus closed before t
}

Dry run: flowers [[1, 6], [3, 7], [9, 12], [4, 13]], visitors [2, 3, 7, 11]

starts = [1, 3, 4, 9], ends = [6, 7, 12, 13]

The answer is [1, 2, 2, 2]. Look at t = 7: the flower [3, 7] ends at 7 and is still in bloom, which is why the second count uses end < t and not end <= t. Using the same comparison in both helpers is the standard off-by-one here. Sorting is O(n log n) and each visitor costs two binary searches, so the total is O((n + q) log n), with O(n) extra space. This version does not even need the queries sorted, because binary search answers any order.

Minimum interval to include each query: the sweep with a heap

Now the question changes to: for each query point q, what is the size (right - left + 1) of the smallest interval that contains it, or -1 if there is none? A count could be split into two counts; a minimum cannot. So keep the intervals that currently contain q in a min-heap keyed by size, and sort the queries so that q only grows.

Sorted this way, two things happen as q increases. Intervals with left ≤ q become candidates, and they stay candidates until they end. Intervals with right < q are useless for this query and also for every later one, since later queries are larger. That permanent death is exactly what lazy deletion needs. So: push every interval whose left end is at or before q, pop dead tops, and the top is the answer. The code reuses the Heap class from the skyline, here ordered so that the smallest size comes out first.

function minInterval(intervals, queries) {
  const byLeft = [...intervals].sort((a, b) => a[0] - b[0]);
  const order = queries.map((_, i) => i).sort((a, b) => queries[a] - queries[b]); // query indices, smallest query first
  const open = new Heap((a, b) => a[0] < b[0]); // entries [size, right]; the smallest size leaves first
  const answer = new Array(queries.length).fill(-1);
  let next = 0;
  for (const qi of order) {
    const q = queries[qi];
    while (next < byLeft.length && byLeft[next][0] <= q) {
      const [left, right] = byLeft[next++];
      open.push([right - left + 1, right]);
    }
    while (open.size > 0 && open.peek()[1] < q) open.pop(); // ended before q, so it also ends before every later query
    if (open.size > 0) answer[qi] = open.peek()[0];
  }
  return answer;
}

Dry run: intervals [[1, 4], [2, 4], [3, 6], [4, 4]], queries [2, 3, 4, 5]

Heap entries are [size, right]; the queries are already in sorted order here.

The result is [3, 3, 1, 4]. At q = 5 the entries [1, 4] and [3, 4] sit on top and both ended at 4, so both are popped. Two entries of size 4 remain: [4, 6], which is still alive, and [4, 4], which is dead. This run leaves the live one on top, so the loop stops and the answer is 4; had the dead one been on top, it would have been popped next and the answer would be the same. A dead entry that stays buried is harmless, which is the whole point of deleting lazily.

The cost is one sort of the intervals, one sort of the query indices, and a push and a pop per interval, so O((n + q) log(n + q)) time and O(n + q) space. The pitfalls are the ones to rehearse. Write the answer at answer[qi], not at the sorted position. Pop on right < q, not <=, because the range is closed. And do not forget the -1 default for a query that no interval reaches.

When offline is not available

Offline needs every query up front, and no query may depend on an earlier answer. If the queries arrive one at a time and each must be answered before the next appears, there is no sorted order to exploit, and you need a structure that answers any query on demand, such as the trees in the segment and Fenwick tree chapter. Ask the interviewer which case you are in. "Are all queries given up front?" is often the most valuable single question in these problems.

Coordinate compression, exactly

Many of these problems give coordinates up to 10⁹ but only a few hundred or thousand distinct ones. The algorithm cannot index an array by such a coordinate, but it does not need to: a sweep, a sort or a segment tree only asks whether one coordinate is smaller than another. Coordinate compression replaces each value by its rank among the distinct values, which keeps every comparison and shrinks the range to at most the number of distinct values.

function compress(values) {
  const sorted = [...new Set(values)].sort((a, b) => a - b); // the comparator matters: the default sort is textual
  const rank = new Map(sorted.map((value, i) => [value, i]));
  return { sorted, rank };
}

function rankTransform(array) {
  const { rank } = compress(array);
  return array.map((value) => rank.get(value) + 1);
}

For [100, 7, 1000000000, 7, 42] the distinct sorted values are [7, 42, 100, 1000000000], so the ranks are 0, 1, 2 and 3, and rankTransform returns [3, 1, 4, 1, 2] with ranks starting at 1. Equal values get equal ranks, and the order is preserved. The cost is O(n log n) for the sort, and each later lookup in the Map is O(1) on average. If you need the rank of a value that may not be in the set, such as a query coordinate, binary search the sorted array instead: the number of distinct values below it, countBelow(sorted, v) from above, is its rank.

What compression keeps and what it destroys. Order survives; distances do not. Two coordinates one apart and two coordinates a billion apart can be neighbours after compression. Anything that depends on a distance must go back to the original values, and the sorted array is how: the length of the gap between rank i and rank i + 1 is sorted[i + 1] - sorted[i]. The rectangle union below uses exactly that.

Rectangle union: the simple way and the segment tree

Given n axis-aligned rectangles [x1, y1, x2, y2], find the area of their union, with overlaps counted once. Adding the areas counts overlaps several times, and correcting for them by inclusion and exclusion is exponential. Counting grid cells fails when the coordinates reach 10⁹.

The idea. Sweep along x. Between two consecutive distinct x coordinates (a slab) the set of rectangles that cover the slab does not change, so the covered height is one number for the whole slab, and the slab contributes width × covered height. The covered height is the total length of the union of the y-ranges of those rectangles, which is the interval merge from the intervals chapter. There are at most 2n - 1 slabs.

function unionAreaSimple(rects) {
  const xs = [...new Set(rects.flatMap(([x1, , x2]) => [x1, x2]))].sort((a, b) => a - b);
  const byBottom = [...rects].sort((a, b) => a[1] - b[1]); // sorted by y once, so each slab needs no sort
  let total = 0n;
  for (let i = 0; i + 1 < xs.length; i++) {
    const left = xs[i], right = xs[i + 1];
    let covered = 0, reach = -Infinity;
    for (const [x1, y1, x2, y2] of byBottom) {
      if (x1 > left || x2 < right || y2 <= reach) continue; // not covering this slab, or already inside what is covered
      covered += y2 - Math.max(y1, reach); // count only the part above what is already covered
      reach = y2;
    }
    total += BigInt(right - left) * BigInt(covered); // width times height can pass 2 ** 53
  }
  return total;
}

Sorting the rectangles by bottom edge once means every slab can merge the y-ranges in one pass, with reach as the highest point covered so far: a range lying entirely below reach adds nothing, and any other adds only the part above reach. There are up to 2n - 1 slabs, and each scans n rectangles, so this is O(n²) time and O(n) space. For rectangles [[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]] the slabs are [0, 1], [1, 2] and [2, 3] with covered heights 2, 3 and 1, so the area is 2 + 3 + 1 = 6.

Faster: let a segment tree keep the covered length. The quadratic version recomputes the covered length from scratch for every slab, though only one or two rectangles enter or leave between slabs. What is needed is a structure that supports "add 1 to the cover of the y-range [a, b)", "subtract 1 from it", and "total covered length right now". Compress the y coordinates first. The elementary segments are the gaps between neighbouring distinct y values, numbered 0 to m - 1, and a rectangle covers the segments from the rank of its bottom to the rank of its top, exclusive.

Each tree node stands for a range of elementary segments and stores two numbers. cover is how many rectangles have this node as one of the pieces their y-range was split into, so each such rectangle covers the node's whole range. length is the covered length inside the node's range. If cover is positive, the whole range is covered and the length is ys[hi] - ys[lo]. Otherwise the length is whatever the two children report, or 0 at a leaf. Nothing has to be pushed down to children, because every removal subtracts from exactly the nodes where the matching insertion added, and after every update the root's length is the covered height.

function unionArea(rects) {
  const ys = [...new Set(rects.flatMap(([, y1, , y2]) => [y1, y2]))].sort((a, b) => a - b);
  const yIndex = new Map(ys.map((y, i) => [y, i]));
  const segments = ys.length - 1; // the gaps between neighbouring y values
  if (segments < 1) return 0n;
  const cover = new Array(4 * segments).fill(0); // how many rectangles cover this node's whole range
  const length = new Array(4 * segments).fill(0); // covered length inside this node's range

  function update(node, lo, hi, from, to, delta) { // node stands for gaps lo .. hi - 1
    if (to <= lo || hi <= from) return;
    if (from <= lo && hi <= to) {
      cover[node] += delta;
    } else {
      const mid = (lo + hi) >> 1;
      update(2 * node, lo, mid, from, to, delta);
      update(2 * node + 1, mid, hi, from, to, delta);
    }
    if (cover[node] > 0) length[node] = ys[hi] - ys[lo];
    else if (hi - lo === 1) length[node] = 0;
    else length[node] = length[2 * node] + length[2 * node + 1];
  }

  const events = [];
  for (const [x1, y1, x2, y2] of rects) {
    if (x1 === x2 || y1 === y2) continue;
    events.push([x1, 1, yIndex.get(y1), yIndex.get(y2)]);
    events.push([x2, -1, yIndex.get(y1), yIndex.get(y2)]);
  }
  events.sort((a, b) => a[0] - b[0]); // ties do not matter: no width passes between them
  let total = 0n, previousX = events.length > 0 ? events[0][0] : 0;
  for (const [x, delta, from, to] of events) {
    total += BigInt(x - previousX) * BigInt(length[1]); // the covered length held since the last event
    previousX = x;
    update(1, 0, segments, from, to, delta);
  }
  return total;
}

Dry run: [[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]], with y values 0, 1, 2, 3

The total is 6, matching the slab version. Two events at x = 1 and two at x = 2 are processed in whatever order the sort leaves them, and the second of each pair adds area 0, so the order does not matter. Each update touches O(log m) nodes, and there are 2n updates, so the whole sweep is O(n log n) after sorting, with O(n) space.

Geometry in integers: cross product and orientation

The rest of the chapter is plane geometry, and nearly all of it rests on one operation. For vectors u = (ux, uy) and v = (vx, vy), the cross product is the number ux · vy - uy · vx. To see what it means, write the vectors by length and angle, u = |u| (cos α, sin α) and v = |v| (cos β, sin β). Then the cross product is |u| |v| (cos α sin β - sin α cos β), which is |u| |v| sin(β - α). Its sign is the sign of the sine of the angle you turn through to get from u to v: positive for a counter-clockwise turn of less than a half turn, negative for clockwise, and zero when the vectors are parallel or one is zero. Its size is the area of the parallelogram the two vectors span.

For three points, take the vectors from o to a and from o to b. Walking o → a → b turns left if the cross product is positive, right if negative, and goes straight (or back on itself) if zero.

function cross(o, a, b) {
  return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
}

function orientation(o, a, b) {
  const c = cross(o, a, b);
  return c > 0 ? 1 : c < 0 ? -1 : 0; // 1: left turn, -1: right turn, 0: collinear
}

orientation reduces the number to -1, 0 or 1. Keep to that sign whenever you only need the direction: the size of cross is easy to overflow, while its sign is all the algorithms below use. One caution about pictures: on a screen, y grows downward, which mirrors the plane, so a "left turn" in the formula looks clockwise there. Decide by the sign and the formula, not by how the points look on screen.

Exactness. With integer coordinates every operation here is an integer operation, so the result is exact, and zero really means collinear. A Number holds integers exactly up to 2⁵³, about 9 · 10¹⁵. If every coordinate has absolute value at most M, each difference is at most 2M, each product at most 4M², and the cross product at most 8M². That stays below 2⁵³ while M is up to about 3 · 10⁷. Beyond that, use BigInt, shown in the floating-point section.

Collinear points and the point-on-segment test

Three points are collinear when cross(a, b, c) === 0. That says c is on the line through a and b, not on the segment between them. To restrict it to the segment, add the bounding box check: c must lie between the endpoints in x and in y.

function onSegment(a, b, p) {
  return (
    cross(a, b, p) === 0 &&
    Math.min(a[0], b[0]) <= p[0] && p[0] <= Math.max(a[0], b[0]) &&
    Math.min(a[1], b[1]) <= p[1] && p[1] <= Math.max(a[1], b[1])
  );
}

Why the box is enough once the point is on the line: along a line, x and y both change steadily, so a point between the endpoints in the coordinate that varies is between them on the line. For a vertical segment the x test is trivially true and the y test does the work; for a horizontal one it is the other way round. A degenerate "segment" with a === b has cross product 0 for every p, and the box shrinks to a single point, so only p === a passes, which is correct. This is O(1).

Do two segments intersect?

Segment ab and segment cd cross properly when c and d are on opposite sides of the line through a and b, and a and b are on opposite sides of the line through c and d. Opposite sides means the two orientations differ. Both conditions are needed: the first says that segment cd crosses the line through ab, but not that it crosses the segment ab itself, and the second closes that gap from the other side.

Write the comparison as "the two orientations differ", not as "the product of two cross products is negative". A zero is then its own side, and the same test also accepts an endpoint that lies on the other segment (a T) and two segments that share an endpoint, which is what interviewers like to probe. What it cannot see is the case where both endpoints of one segment lie on the other's line, so two orientations are 0 and equal: the segments are collinear and may overlap or leave a gap. A segment that has shrunk to a single point lands there too. For those, check whether an endpoint of one segment lies inside the other: orientation 0 and inside its bounding box.

function segmentsIntersect(a, b, c, d) {
  const o1 = orientation(a, b, c), o2 = orientation(a, b, d);
  const o3 = orientation(c, d, a), o4 = orientation(c, d, b);
  if (o1 !== o2 && o3 !== o4) return true; // each segment straddles the other's line
  if (o1 === 0 && onSegment(a, b, c)) return true; // an endpoint lies on the other segment
  if (o2 === 0 && onSegment(a, b, d)) return true;
  if (o3 === 0 && onSegment(c, d, a)) return true;
  if (o4 === 0 && onSegment(c, d, b)) return true;
  return false;
}

Dry run on seven cases

In the T case c is on the line of ab while d is off it, and a and b fall on opposite sides of the line through cd, so the first test reports the touch even though o1 is 0. In the two all-zero rows the first test cannot fire, since o1 === o2, and only the endpoint checks can say true. Two collinear segments that overlap always have an endpoint of one inside the other, so those four checks are enough. Across 200,000 random pairs of segments on a 5 × 5 grid, including collinear, touching and single-point segments, the function matched an independent exact calculation every time, and it gave the same answer with the two segments swapped or their endpoints reversed.

Polygon area by the shoelace formula

The cross product gives the area of a triangle: for the triangle o, a, b it is half of cross(o, a, b), with a sign. A polygon with vertices p0, p1, ..., p(n-1) given in order around its boundary can be cut into the fan of triangles (p0, p1, p2), (p0, p2, p3), .... Adding their signed areas gives the polygon's area, and this holds for concave polygons too. A fan triangle can stick out of a concave polygon, but each triangle carries the sign of its own turn, so a piece that sticks out is counted once forwards and once backwards by the triangles of the fan, and cancels. It is called the shoelace formula because, written out in coordinates, the products cross like laces.

function doubledArea(polygon) {
  let sum = 0;
  for (let i = 1; i + 1 < polygon.length; i++) {
    sum += cross(polygon[0], polygon[i], polygon[i + 1]); // the triangle fan from vertex 0
  }
  return sum; // positive for counter-clockwise, negative for clockwise
}

The function returns twice the area, as an integer, which avoids the halves and keeps the arithmetic exact; divide by 2 at the end if you need the area itself. The sign tells the orientation: positive when the vertices run counter-clockwise, negative for clockwise, so Math.abs gives the area and the sign is a free orientation test. For the rectangle [[0, 0], [4, 0], [4, 3], [0, 3]] the fan has two triangles with doubled areas 12 and 12, so the result is 24 and the area is 12. For the concave polygon [[0, 0], [6, 0], [6, 6], [3, 2], [0, 6]] it returns 48, an area of 24, and reversing the vertex order gives -48. Time is O(n), space O(1).

A cross-check you can trust. For a polygon whose vertices all have integer coordinates, Pick's theorem says that area = I + B / 2 - 1, where I is the number of lattice points strictly inside and B the number on the boundary. B is the sum of gcd(|dx|, |dy|) over the edges, using the gcd from the math chapter: an edge from one lattice point to another contributes exactly that many lattice points, counting one of its ends. In the chapter's checks, the shoelace result equalled 2I + B - 2 on three thousand random polygons.

Point in polygon by ray casting

Is a point inside a polygon, possibly a concave one? Shoot a ray from the point to the right, to infinity, and count how many edges it crosses. Each crossing switches between outside and inside, and the far end of the ray is outside, so the point is inside exactly when the count is odd. That is the whole idea. The difficulty is in the edge cases, and an exact integer test removes all of them.

Three things go wrong if you code it carelessly:

• The ray passes through a vertex. Two edges meet there, and a naive test counts the crossing twice, or not at all.
• An edge lies along the ray. A horizontal edge on the ray's row has no single crossing point.
• The point is on the boundary. Neither "inside" nor "outside" is obviously right.

The first two are solved by one half-open rule. Count an edge only when (a.y > p.y) !== (b.y > p.y): exactly one endpoint is strictly above the ray's row. This treats a vertex exactly on the row as if it were slightly below the ray, so the ray never actually touches a vertex. An edge ending on the row is counted only if its other end is above, once, and a horizontal edge, which has both ends on the same side, is never counted. For an edge that passes the test, decide whether the crossing is to the right of the point with the cross product sign: for an edge going up, the point must be on its left (cross > 0); for an edge going down, on its right (cross < 0). No division and no rounding are involved. The boundary is handled first, with onSegment.

function pointInPolygon(p, polygon) {
  let crossings = 0;
  for (let i = 0; i < polygon.length; i++) {
    const a = polygon[i], b = polygon[(i + 1) % polygon.length];
    if (onSegment(a, b, p)) return "boundary";
    if ((a[1] > p[1]) !== (b[1] > p[1])) { // the edge straddles the row of p; a flat edge never does
      const side = cross(a, b, p);
      if (b[1] > a[1] ? side > 0 : side < 0) crossings++; // the crossing lies to the right of p
    }
  }
  return crossings % 2 === 1 ? "inside" : "outside";
}

Dry run: the diamond [[2, 0], [4, 2], [2, 4], [0, 2]] and the point (1, 2)

The ray from (1, 2) runs right along y = 2, straight through the vertex (4, 2).

One crossing, an odd count, so the point is inside, which is right. The vertex (4, 2) was used by two edges but counted once. A naive rule that counts an edge whenever the row lies between its ends inclusively counts both edges at (4, 2) and gets 2, an even number, so it calls the point outside. The same function reports (5, 2) as outside, (4, 2) as the boundary and (2, 2) as inside. Time is O(n) per point and space is O(1).

Rectangles: overlap, area and the perfect rectangle

An axis-aligned rectangle is [x1, y1, x2, y2] with x1 < x2 and y1 < y2: bottom-left and top-right corners. Two rectangles overlap in a region of positive area exactly when their x-ranges overlap and their y-ranges overlap. Two ranges (a1, a2) and (b1, b2) overlap when a1 < b2 and b1 < a2, the same test as the My Calendar check in the intervals chapter.

function rectanglesOverlap(a, b) {
  return a[0] < b[2] && b[0] < a[2] && a[1] < b[3] && b[1] < a[3]; // strict: sharing an edge is not overlap
}

function overlapArea(a, b) {
  const width = Math.min(a[2], b[2]) - Math.max(a[0], b[0]);
  const height = Math.min(a[3], b[3]) - Math.max(a[1], b[1]);
  return Math.max(0, width) * Math.max(0, height); // clamp each side separately, then multiply
}

function totalArea(a, b) {
  const area = (r) => (r[2] - r[0]) * (r[3] - r[1]);
  return area(a) + area(b) - overlapArea(a, b);
}

The comparisons are strict, so two rectangles that share only an edge or a corner do not overlap. If a problem counts touching as overlap, use <=, and say so. For the area, each side of the overlap is the smaller of the two top values minus the larger of the two bottom values, and that can be negative when the rectangles are apart. Clamp each side at 0 before multiplying. Clamping only the product is the classic bug: two negative sides multiply to a positive number, and rectangles that are apart in both directions would report a phantom overlap. The union of two rectangles has area A + B - overlap. All three functions are O(1), and they agreed with a cell-by-cell count on twenty thousand random pairs.

The perfect rectangle: two checks, each catching what the other misses

Given n rectangles, do they fit together to cover one larger rectangle exactly, with no gaps and no overlaps? Two tests, both linear:

1. The areas add up. The sum of the rectangle areas must equal the area of the bounding box, the smallest rectangle containing all of them.
2. The corners cancel. Look at every corner of every rectangle. In a perfect tiling, a point where tiles meet is a corner of an even number of them: a point inside a straight edge of one tile is the corner of two neighbours, and a point where four tiles meet is the corner of all four. Only the four corners of the whole bounding box belong to exactly one tile. So toggle each corner in a set, adding it if absent and removing it if present. At the end, exactly the four bounding-box corners must be left.

function isRectangleCover(rects) {
  let left = Infinity, bottom = Infinity, right = -Infinity, top = -Infinity, area = 0;
  const corners = new Set();
  const toggle = (x, y) => {
    const key = x + "," + y;
    if (corners.has(key)) corners.delete(key);
    else corners.add(key);
  };
  for (const [x1, y1, x2, y2] of rects) {
    left = Math.min(left, x1);
    bottom = Math.min(bottom, y1);
    right = Math.max(right, x2);
    top = Math.max(top, y2);
    area += (x2 - x1) * (y2 - y1);
    toggle(x1, y1);
    toggle(x1, y2);
    toggle(x2, y1);
    toggle(x2, y2);
  }
  if (area !== (right - left) * (top - bottom)) return false;
  return (
    corners.size === 4 &&
    corners.has(left + "," + bottom) && corners.has(left + "," + top) &&
    corners.has(right + "," + bottom) && corners.has(right + "," + top)
  );
}

Neither test is enough alone, and it is worth seeing why. The two rectangles [0, 0, 1, 2] and [0, 0, 2, 1] overlap in a unit square and leave a unit gap at the top right, so the area is 2 + 2 = 4, which equals the 2 × 2 bounding box and passes the first check; but the corner (0, 0) is toggled twice and disappears, so the second check fails. Three copies of [0, 0, 1, 1] toggle every corner three times, so exactly the four box corners remain and the second check passes, but the area 3 is not 1, so the first check fails. Together they catch both.

A note on how much to trust the pair. The necessity of both tests is the argument above. That the two together are also sufficient is true, but the proof is longer than the code. What this chapter relies on is a brute-force comparison: every set of up to 5 rectangles on a 3 × 3 grid and up to 4 on a 4 × 4 grid, about 5.3 million sets in all, plus twenty thousand tilings with one rectangle removed, duplicated, stretched, shrunk or shifted, checked cell by cell. It never disagreed. Time is O(n) and space is O(n) for the set.

Dry run: [[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]]

The areas sum to 9, the bounding box is 3 × 3 = 9, and the corners left are (1,1), (1,4), (4,1) and (4,4), which are exactly the four box corners. The answer is true. The input [[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4]] leaves the middle column empty: its areas sum to 6 against a box of 9, so the first check already fails.

Maximum points on a line: hash the direction, not the slope

Given n points, find the largest number that lie on one straight line. Testing every triple with the cross product is O(n³). The better question is: fix one point as an anchor. Every other point gives a direction from the anchor, and the points that line up with the anchor are exactly the ones with the same direction. So count points per direction with a Map, and the best line through the anchor holds the largest count plus the anchor. Repeat for every anchor: O(n²) lookups.

The direction is the whole problem. The slope dy / dx looks natural, but it fails twice. A vertical line has dx = 0 and needs a special case, and a division of two integers can give the same floating-point number for two different slopes. The exact key is the pair (dy, dx) after two normalisations. Reduce it by dividing both by their gcd, taken from the math chapter, so that (2, 4), (1, 2) and (3, 6) all become (1, 2): two integer vectors are parallel exactly when they are the same vector after dividing out the gcd and fixing the sign. Fix the sign, so that (1, 2) and (-1, -2), which point opposite ways along the same line, get one key: make dx positive, and when dx is 0, make dy positive.

function maxPoints(points) {
  const n = points.length;
  if (n <= 2) return n;
  let best = 1;
  for (let i = 0; i < n; i++) {
    const slopes = new Map();
    let duplicates = 0, onBestLine = 0;
    for (let j = i + 1; j < n; j++) {
      let dx = points[j][0] - points[i][0];
      let dy = points[j][1] - points[i][1];
      if (dx === 0 && dy === 0) {
        duplicates++; // the same point again belongs to every line through i
        continue;
      }
      const g = gcd(dx, dy);
      dx /= g;
      dy /= g;
      if (dx < 0 || (dx === 0 && dy < 0)) { // one direction, not two opposite ones
        dx = -dx;
        dy = -dy;
      }
      const key = dy + "/" + dx;
      const count = (slopes.get(key) ?? 0) + 1;
      slopes.set(key, count);
      onBestLine = Math.max(onBestLine, count);
    }
    best = Math.max(best, onBestLine + duplicates + 1);
  }
  return best;
}

Two details deserve a sentence each. The loop looks only at points after the anchor (j > i): the best line's lowest-indexed point, used as the anchor, sees every other point on that line later in the array, so nothing is missed. And a point identical to the anchor lies on every line through the anchor, so it is counted separately in duplicates and added to whichever direction wins. If every point is the same, onBestLine stays 0 and the answer is the number of duplicates plus the anchor, which is n.

Dry run: anchor (1, 4) among (1,4) (1,1) (3,2) (5,3) (4,1) (2,3)

The key is written dy/dx. Three points share -1/1, so the line through the anchor holds 3 + 1 = 4 points, the answer for this input. The row for (1,1) shows the sign rule: the vertical direction (0, -3) becomes 1/0, not -1/0. Time is O(n² log C), where C bounds the coordinate differences, because each gcd takes a logarithmic number of steps, and the space is O(n) for one map.

Valid square without a single square root

Four points are given in any order. Do they form a square? Trying the orderings and checking right angles works but is clumsy. A neater test uses distances. A square with side s has six pairwise distances: four equal sides, and two equal diagonals. In squared form, which stays in integers, the sides are s² and the diagonals are 2s² by Pythagoras. So compute the six squared distances, sort them, and require four equal smallest values that are not zero, then two equal larger values, each twice the smaller.

function squaredDistance(a, b) {
  return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
}

function validSquare(p1, p2, p3, p4) {
  const points = [p1, p2, p3, p4];
  const d = [];
  for (let i = 0; i < 4; i++) {
    for (let j = i + 1; j < 4; j++) d.push(squaredDistance(points[i], points[j]));
  }
  d.sort((a, b) => a - b);
  return d[0] > 0 && d[0] === d[3] && d[4] === d[5] && d[4] === 2 * d[0]; // four equal sides, two diagonals of twice the square
}

For (0,0) (1,1) (1,0) (0,1) the six squared distances sorted are [1, 1, 1, 1, 2, 2]: four of 1, two of 2, and 2 is twice 1, so the answer is true. A tilted square such as (0,0) (2,1) (1,3) (-1,2) gives [5, 5, 5, 5, 10, 10] and is accepted. The parallelogram (0,0) (2,0) (3,1) (1,1), whose sides have two different lengths, gives [2, 2, 2, 4, 4, 10] and is rejected. The cost is 6 distances and a sort of 6 numbers: O(1).

Why the pattern is sufficient. That a square produces it is clear. The converse needs an argument, because the test never looks at angles. Suppose four of the six squared distances equal d > 0 and the other two equal 2d. The two long pairs either share a point or are disjoint.

• Disjoint long pairs, say AC and BD: then the four other pairs AB, BC, CD, DA have squared length d. In triangle ABC, AB² + BC² = 2d = AC², so the angle at B is a right angle, and it is an isosceles right triangle on the hypotenuse AC. The same holds for triangle ADC. There are only two points that make an isosceles right triangle on a given hypotenuse, one on each side of it; D cannot equal B because BD² = 2d > 0, so D is the other one, and ABCD is a square.
• Long pairs sharing a point, say PQ and PR: then PS, QR, QS, RS all have squared length d, so Q, R and S form an equilateral triangle of side √d, and P is at distance √d from S and √(2d) from both Q and R. P is then on the perpendicular bisector of QR, which passes through S, at distance √d from S: either on the far side of S from QR or on the same side as QR. Measuring from the midpoint M of QR, S is (√3/2)√d from M, so those two positions are (√3/2 + 1)√d and (1 - √3/2)√d from M, while PQ² = 2d demands PM² = 2d - d/4, that is (√7/2)√d. Neither matches, so this case cannot occur.

I also checked the test against a permutation-and-right-angle definition on all 65,536 ordered quadruples of points from a 4 × 4 grid, and on 100,000 random ones, with no disagreement.

Convex hull by monotone chain (erect the fence)

The convex hull of a set of points is the smallest convex polygon that contains all of them: stretch a rubber band around the points and let go. "Erect the fence" asks for every point that lies on that band, including points in the middle of a straight stretch. The monotone chain method builds the hull in two halves and uses nothing but the cross product.

Sort the points by x, breaking ties by y. Build the lower hull going left to right with a stack: for each new point p, while the stack has two or more points and the last two points a, b together with p make a right turn (cross(a, b, p) < 0), pop b; then push p. Then do the same over the points in reverse order for the upper hull. The two chains joined give the boundary in counter-clockwise order.

Why the cross-product test is the right one. The lower hull is the part of the boundary you see from below: going left to right it only ever turns left (or goes straight), because a right turn would make a dent pointing into the hull. Look at what a right turn means for the three points a, b, p, whose x values do not decrease. Then b lies strictly above the segment from a to p (when x values tie, the same holds with "above" read as the vertical order). The point on that segment directly below b is a blend of a and p, both in the set, so the hull reaches strictly below b there, and b cannot be on the lower boundary. Popping it loses nothing. After the pops stop, the last two stack points and p make a left turn or go straight, and the invariant, "every consecutive triple on the stack turns left or goes straight", holds again with p on top. p itself belongs on the stack because nothing to its right has been seen yet and it is the newest rightmost point of the prefix.

A straight triple, cross === 0, is the one decision that differs between versions. The middle point is on the hull boundary but is not a corner. "Erect the fence" wants it, so pop only when the cross product is strictly negative. A problem that wants only the corners pops on <= 0 as well.

function convexHull(points, keepCollinear) {
  const sorted = [...points].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const pts = sorted.filter((p, i) => i === 0 || p[0] !== sorted[i - 1][0] || p[1] !== sorted[i - 1][1]);
  if (pts.length <= 2) return pts;
  const mustPop = keepCollinear ? (turn) => turn < 0 : (turn) => turn <= 0;

  function chain(list) {
    const stack = [];
    for (const p of list) {
      while (stack.length >= 2 && mustPop(cross(stack[stack.length - 2], stack[stack.length - 1], p))) stack.pop();
      stack.push(p);
    }
    return stack;
  }

  const lower = chain(pts);
  const upper = chain([...pts].reverse());
  const seen = new Set();
  const hull = [];
  for (const p of [...lower, ...upper]) {
    const key = p[0] + "," + p[1];
    if (!seen.has(key)) {
      seen.add(key);
      hull.push(p);
    }
  }
  return hull;
}

Dry run: [[1,1],[2,0],[2,2],[2,4],[3,3],[4,2]], keeping collinear points

Sorted by x then y, the order is (1,1) (2,0) (2,2) (2,4) (3,3) (4,2).

Joining the lower chain (1,1) (2,0) (4,2) with the upper chain (4,2) (3,3) (2,4) (1,1) and dropping repeats gives (1,1) (2,0) (4,2) (3,3) (2,4). The point (2,2) is correctly absent: it is inside the hull. If every point is on one line, both chains hold all of them, and removing repeats leaves each once.

Cost. The sort is O(n log n). In each chain every point is pushed once and popped at most once, so building both chains is O(n), and the total is O(n log n) time and O(n) space. The same code with keepCollinear set to false returns only the corners: for the bottom-edge example (0,0) (1,0) (2,0) (2,2) (0,2) it returns four points, and with true it returns five, including (1,0).

Closest pair of points

Given n points, find the smallest distance between any two. Comparing all pairs is O(n²). Two ways reach O(n log n). The divide and conquer version splits the points by x, solves both halves, and repairs the pair that straddles the split; it belongs with the other recursive splits in the divide and conquer chapter. The sweep version fits this chapter: process the points in x order and keep the already-seen points whose x is within the best distance d found so far, ordered by y. For a new point, only the active points whose y is within d of it can improve the answer, and a packing argument says there are a small constant number of them (the argument below gives at most eight): all pairs among the processed points are at least d apart, a box d wide and 2d tall splits into eight squares of side d / 2, and two points in one such square would be closer than d. Finding those neighbours in the y-ordered set needs an ordered structure, which the ordered structures chapter covers.

A short version needs no special structure and is usually fast. Sort by x, and for each point scan backwards through the earlier points, stopping as soon as the gap in x alone is no smaller than the best distance found so far, because every earlier point is at least that far away in x.

function closestPairSquared(points) {
  const pts = [...points].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let best = Infinity;
  for (let i = 1; i < pts.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      const dx = pts[i][0] - pts[j][0];
      if (dx * dx >= best) break; // everything further left is at least this far away in x
      const dy = pts[i][1] - pts[j][1];
      best = Math.min(best, dx * dx + dy * dy);
    }
  }
  return best;
}

It returns the squared distance, which is exact in integers and avoids the square root; take Math.sqrt only for display. It returns Infinity for fewer than two points. The honest cost is O(n²) in the worst case: if all points share one x, the gap in x is 0, the early exit never fires, and every pair is compared. On well-spread input it does far less, but when an interviewer asks for the guaranteed bound, use the sweep with an ordered set or the divide and conquer.

Floating point: why geometry stays in integers

JavaScript numbers are 64-bit floating point. Every integer up to 2⁵³ is stored exactly, and so is every sum, difference and product of integers whose result stays within that range. Geometry with integer input stays exact as long as no intermediate value leaves that range. Once it does, the damage is silent: no error, just a wrong sign. Here is a concrete case. The points o = (0, 0), a = (94911150, 94911151) and b = (94911149, 94911150) are not collinear, since the exact cross product is 94911150 · 94911150 - 94911151 · 94911149 = 1. In floating point the two products are both 9008126394322500, and the cross product comes out as 0, "collinear". The slopes 94911151 / 94911150 and 94911150 / 94911149 are also the same double. When coordinates can be this large, BigInt restores exactness:

function crossBig(o, a, b) {
  const ax = BigInt(a[0]) - BigInt(o[0]), ay = BigInt(a[1]) - BigInt(o[1]);
  const bx = BigInt(b[0]) - BigInt(o[0]), by = BigInt(b[1]) - BigInt(o[1]);
  return ax * by - ay * bx; // exact whatever the size; compare it with 0n
}

crossBig(o, a, b) for the points above returns 1n. A BigInt is slower and cannot be mixed with a Number, so convert the coordinates up front, and compare the result with 0n, > 0n and < 0n. Use it only when the coordinates can exceed about 3 · 10⁷; below that, Number is exact and much faster.

The rules that follow:

• Compare, do not divide. Ask whether two slopes are equal by cross-multiplying, dy1 * dx2 === dy2 * dx1, while the products stay in the safe range, or by reducing with the gcd, not by comparing quotients.
• Compare squared distances. Skip Math.sqrt and Math.hypot: a² + b² < c² is exact for integers and the root is rounded.
• Do not use an epsilon on integer input. A tolerance such as Math.abs(x - y) < 1e-9 is not transitive: with 0, 0.8e-9 and 1.6e-9, the first two are "equal", the last two are "equal", and the first and last are not. Its right size also depends on the scale of the data. Epsilon belongs to genuinely real-valued input, where you should state the tolerance you chose.
• Sort by angle with the cross product, not with Math.atan2, when you can: split the plane into two half-planes first, then compare within a half-plane by the sign of the cross product. Two different directions can have the same atan2: the vectors (94911151, 94911150) and (94911150, 94911149) do.
• Leave a note on the range. "Coordinates up to 10⁴, so the cross product is at most about 8 · 10⁸ and fits" is a sentence that earns trust in an interview.

Two small -0 facts, since negative zero surfaces whenever a zero is negated, as in the sign fix of a direction key. 0 * -1 is -0, which is === to 0 and prints as "0" in a string key, and a Map treats -0 and 0 as one key. So it is harmless in comparisons and hash keys, but Object.is(0 * -1, 0) is false, which matters only to equality checks built on Object.is.

Recognizing it in an unseen problem

• Buildings, intervals, rectangles or events with start and end coordinates, and a question about "the tallest", "the smallest" or "the total covered" at each moment → a sweep line, with a heap, an ordered set or a segment tree as the active set
• The answer changes only at the endpoints → look at the 2n endpoints only, not the whole range
• Many queries against a fixed set, all known up front → offline: sort the queries (keeping their indices) and sweep; or turn a count into a difference of two prefix counts with binary search
• Coordinates up to 10⁹ with few distinct values, and only comparisons matter → coordinate compression, going back to the sorted values when a length is needed
• "Area of the union of rectangles" → a sweep over x with a segment tree over compressed y, or the quadratic slab version when n is small
• "Do these segments touch or cross", "which side of the line", "is this a left turn" → the cross product and orientation, handling the zero cases explicitly
• "Is the point inside this polygon" → ray casting with the half-open rule; "area of this polygon" → the shoelace sum
• "Most points on a line" or "group points by direction" → a gcd-reduced, sign-normalised pair as the key, not a floating-point slope
• "Do these four points form a square" → six squared distances; "which points enclose all the rest" → monotone chain
• Any of the above with huge coordinates → check whether a cross product can pass 2⁵³, and switch to BigInt if it can