Sorting and Sets

USACO Bronze and Codeforces <1200 are full of problems whose model is: put the values in order, then walk once. Sorting is not a topic you 'finish.' It is the default first move when the statement mentions distinct, closest, median, or 'assign the smallest available.'

Constraints: n ≤ 2·10⁵ makes O(n log n) the budget. n ≤ 10³ still prefers a sort over an O(n²) invent-your-own. Do not write bubble sort. Use the library (sort, Arrays.sort, [...].sort((a,b)=>a-b) — and remember JS default sort is lexicographic).

Distinct count after a sort — CSES Distinct Numbersjs

function distinctNumbers(a) {
  if (a.length === 0) return 0;
  const b = a.slice().sort((x, y) => x - y);
  let count = 1;
  for (let i = 1; i < b.length; i++) {
    if (b[i] !== b[i - 1]) count++;
  }
  return count;
}

A set stores unique keys. An ordered set (C++ set, JS is a hash set — use a sorted unique array or a tree if you need order) answers:

- has(x) — seen this key? - lower_bound(x) — first key ≥ x - erase / insert while scanning

Hash sets (unordered_set, JS Set) are expected O(1) and are the right Bronze tool for 'distinct' and 'already used.' They do not give you the next larger key. When the problem says 'give this customer the cheapest ticket that is at least t' (CSES Concert Tickets), you need order: set + lower_bound, not a hash.

TRACE

Sort [4, 1, 4, 2, 1] and count distinct by walking adjacent pairs.

Sort

After a numeric sort the array is [1, 1, 2, 4, 4]. Equal values are now neighbors.

[1, 1, 2, 4, 4]

1 / 5

CHECK

n = 2·10⁵ values up to 10⁹. You need the number of distinct values. Which is legal and simplest?

CHECK

CSES Concert Tickets: for each customer with budget t, assign the most expensive remaining ticket with price ≤ t. Why is a hash set of prices wrong?

Checks 0/2

Next lesson