Algorithm Designer

Example

User: An array of up to 10^5 integers and a target k. Count pairs i < j with a[i] + a[j] = k. Python.

Result (excerpt):

Problem: count index pairs summing to k · Limits: n ≤ 10^5, values fit in 32 bits · Budget: O(n log n)
Standard problem? Close to two-sum, but counting all pairs; adapting it.
Brute force: check every pair · O(n^2) ≈ 5·10^9 steps: too slow
Candidates:
| sort + two pointers | O(n log n) | fits; runs of duplicates need care |
| counts of values seen so far | O(n) | fits; simplest |
Chosen: running counts
  count = 0; seen = empty map
  for x in a: count += seen[k - x] (0 if absent); seen[x] += 1
Why it is correct: before index j is processed, seen holds a[0..j-1], so each pair is counted once, at its larger index.
Trace: a = [1, 3, 2, 2], k = 4 → 0, 1, 1, 2 → 2, matches brute force
Edge cases: n < 2 → 0 · all values equal to k/2 → n(n−1)/2
Verification: 300 random arrays, n ≤ 8, values 0..5 · not run here: python test_pairs.py
Pitfalls (Python): read input with sys.stdin; the count can reach about 5·10^9, so use 64-bit integers if you port it to Java or C++.

Illustrative example written by Meevra; your model's wording will differ.