Lodash sortedUniq Internal Data Structure Explained

This article explores the internal mechanics of the _.sortedUniq function in the Lodash JavaScript library, examining how it handles consecutive duplicates and revealing the underlying data structures used during execution. While developers often expect methods that filter duplicates to map elements into hash tables or sets, _.sortedUniq relies on a much simpler, highly optimized linear array approach that takes advantage of pre-sorted data.

The Underlying Structure: Native Arrays and Scalar Tracking

Unlike Lodash's standard _.uniq method—which may construct a native Set or an internal hash map to track previously seen values across unsorted collections—_.sortedUniq does not map values to any complex associative data structure.

Internally, _.sortedUniq delegates its work to an internal helper function called baseSortedUniq. The underlying data structures mapped during this process are:

1. A Single Result Array ([]): A standard, linear JavaScript Array allocated to store the unique values.
2. A Scalar Register (seen): A single primitive or reference pointer variable that stores only the most recently processed unique item.

Because the input array is already sorted, all identical elements appear sequentially. This eliminates the need for hash lookups, binary search trees, or Set allocations.

How baseSortedUniq Operates Internally

The core implementation in Lodash processes the input sequentially using an index-based while loop:

function baseSortedUniq(array, iteratee) {
  let seen
  let index = -1
  let resIndex = 0

  const { length } = array
  const result = []

  while (++index < length) {
    const value = array[index], computed = iteratee ? iteratee(value) : value
    if (!index || !eq(computed, seen)) {
      seen = computed
      result[resIndex++] = value
    }
  }
  return result
}

Instead of querying a lookup table to see if an element has appeared before, Lodash only evaluates whether the current element is identical to the value stored in the seen variable using the eq utility (an implementation of the SameValueZero algorithm).

When a new unique element is encountered:

• The scalar variable seen is overwritten with the current item's computed value.
• The element is assigned to result[resIndex++], pushing it into the output array by direct index assignment rather than calling Array.prototype.push.

Performance and Memory Implications

By avoiding hash maps and auxiliary set allocations, _.sortedUniq achieves significant performance advantages over unsorted deduplication:

• Time Complexity: Strict \(\mathcal{O}(n)\) time complexity, as each element is evaluated exactly once in a single linear pass.
• Auxiliary Space Complexity: \(\mathcal{O}(1)\) auxiliary memory beyond the output array itself, as only index counters and a single tracking pointer are retained in memory.
• Garbage Collection Efficiency: Since no intermediary lookup objects, hashes, or node structures are instantiated, memory churn is minimized, reducing overhead on the JavaScript engine's garbage collector.