Topic: Learning notes

LeetCode 347: Top K Frequent Elements in TypeScript, From Frequency Sorting to Buckets

Start with Map frequency counting and sorting, then remove the O(n log n) sort with frequency buckets.

I first counted values with a Map, then sorted by frequency. It returns the right answer and is a reasonable first step. The problem follow-up requires time better than O(n log n), so the full sort still needs replacing.

Problem

Original problem: LeetCode 347: Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. Output order does not matter. The problem guarantees a unique answer and asks for a follow-up solution faster than O(n log n).

Brute force counts the same values repeatedly

The direct approach scans the whole array again for each value to count its occurrences, then finds the top k. Each value may revisit nums, which takes O(n²) time.

Keeping counts first removes that repeated work.

My original Map-counting and sorting solution

function topKFrequent(nums: number[], k: number): number[] {
  if (k === 1 && nums.length === 1) return nums;

  const map = new Map<number, number>();

  for (let index = 0; index < nums.length; index += 1) {
    const num = nums[index];
    map.set(num, (map.get(num) ?? 0) + 1);
  }

  return [...map]
    .sort((left, right) => right[1] - left[1])
    .slice(0, k)
    .map(([num]) => num);
}

This was my first solution. The first loop stores every number’s frequency in a Map. Spreading the map produces [number, count] pairs, which are sorted by index 1, sliced to k, and mapped back to numbers.

map[Symbol.iterator]() is also valid because the default Map iterator yields [key, value] pairs. [...map] or [...map.entries()] is easier to read. MDN’s Map reference documents that iteration over a map produces key-value pairs.

The k === 1 && nums.length === 1 early return is unnecessary. The normal path already handles one input value.

Complexity and limit of this version

Use u for the number of unique values, so it is not confused with the problem parameter k.

• Counting: O(n).
• Spreading the map: O(u).
• Sorting: O(u log u).
• slice() and the final map(): O(k).

Total time is O(n + u log u). In the worst case, u = n, which becomes O(n log n). This is a valid baseline solution, but it does not meet the follow-up. Auxiliary space for the map and entry array is O(u), with another O(k) for the output.

JavaScript does not require Array.prototype.sort() to use one fixed sorting algorithm or complexity. O(u log u) is the comparison-sort model used in interviews. MDN’s sort reference notes that real complexity depends on the implementation.

Buckets meet the follow-up

No value can occur more than nums.length times. Buckets indexed from 0 through n can therefore use their indexes as frequencies, without sorting all unique values.

function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();

  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }

  const buckets: number[][] = Array.from(
    { length: nums.length + 1 },
    () => [],
  );

  for (const [num, frequency] of counts) {
    buckets[frequency].push(num);
  }

  const result: number[] = [];

  for (let frequency = buckets.length - 1; frequency > 0; frequency -= 1) {
    for (const num of buckets[frequency]) {
      result.push(num);

      if (result.length === k) return result;
    }
  }

  return result;
}

Array.from(..., () => []) creates a separate array for every bucket. Do not write new Array(nums.length + 1).fill([]), because every index would share one array.

The first pass takes O(n). Placing u values into buckets takes O(u), and scanning buckets from frequency n down plus collecting values takes at most O(n + u). Total time is O(n). Buckets, the Map, and the result take O(n) space. This meets the follow-up.

Correctness and loop invariant

After processing nums[0..i] in the counting loop, counts.get(num) equals the number of times num appears in that prefix.

After building buckets, every unique number is in exactly one bucket whose index equals its final frequency. When the code scans frequencies from high to low, result contains only values with frequencies at least as high as every bucket not yet scanned. When its length reaches k, it contains the k most frequent values.

Minimal verification

Output order is unspecified, so the tests sort results before comparing them.

import assert from "node:assert/strict";

function sorted(values: number[]): number[] {
  return [...values].sort((left, right) => left - right);
}

assert.deepStrictEqual(sorted(topKFrequent([1, 1, 1, 2, 2, 3], 2)), [1, 2]);
assert.deepStrictEqual(sorted(topKFrequent([1], 1)), [1]);
assert.deepStrictEqual(
  sorted(topKFrequent([1, 2, 1, 2, 1, 2, 3, 1, 3, 2], 2)),
  [1, 2],
);
assert.deepStrictEqual(sorted(topKFrequent([-1, -1, -1, 0, 0, 2], 1)), [-1]);

Common mistakes

• Calling the number of unique values k. The problem already uses k for the requested output size. Use u for unique count.
• Treating count-and-sort as a follow-up solution. Sorting all unique values can still cost O(n log n).
• Building buckets with fill([]), which makes every frequency share one array.
• Testing a fixed output order. The problem accepts any order.
• Using new Map() without types, which allows any keys and values.

Transferable idea

When a value range is bounded by the input size, buckets can replace comparison sorting. Here, frequencies are between 1 and n, so frequency itself becomes an index. The same idea appears in counting sort and frequency-based processing.

References

• LeetCode 347: Top K Frequent Elements: problem, constraints, and complexity follow-up.
• MDN: Map: key-value pairs and iteration behavior.
• MDN: Array.prototype.sort(): in-place sorting and implementation-dependent complexity.
• Node.js: assert.deepStrictEqual(): strict array comparison.