DSA
Cost

How Do You Enumerate Every Index Pair Exactly Once?

Pair enumeration uses i < j to exclude self-pairs and reversed duplicates. Its triangular iteration count explains the quadratic cost.

Two indexes form an unordered pair when i < j. That inequality does three jobs: it prevents pairing an index with itself, prevents counting both (i, j) and (j, i), and gives the inner loop an exact starting point.

Implementation

Theme
Terminal

Press Run to execute this example. Use console.log to print a value.

The invariant at the start of an outer-loop iteration is that count includes exactly the qualifying pairs whose left index is smaller than left. The inner loop then checks every legal right partner for this left index exactly once.

Worked example and cost

For three values, the legal index pairs are (0, 1), (0, 2), and (1, 2). In general the number of checks is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2, so time is O(n²) and scalar extra space is O(1).

TypeScript does not prove that a numeric array is dense. The explicit undefined check gives sparse-array behaviour a clear meaning. For ordinary dense inputs, it never triggers.

Edge cases and counterexamples

  • Empty and one-value arrays contain zero pairs.
  • Equal values at different indexes are a legal pair; one index used twice is not.
  • Starting right at 0 counts reversed pairs and self-pairs.
  • Starting right at left still counts self-pairs.
  • For ascending pairs, change only the predicate to leftValue < rightValue; do not change the index rule.

Use a nested scan when the exercise is explicitly about all pairs. If the predicate is equality and only the count matters, a frequency table can often reduce the work.

Optional enrichment

Derive the number of equal pairs from frequencies using count * (count - 1) / 2 for each distinct value, and compare its O(n) expected-time tradeoff with the direct O(n²) enumeration.

Related