How Lodash _.sortedUniq Optimizes Duplicate Removal

The Lodash _.sortedUniq method provides a highly performant alternative to standard deduplication algorithms by exploiting the mathematical guarantees of pre-sorted data. This article explains how _.sortedUniq works under the hood, how its single-pass adjacent comparison eliminates the need for auxiliary tracking structures like hash maps or sets, and why it drastically reduces time and memory overhead compared to generic uniqueness functions.

The Inefficiency of Generic Deduplication

Generic uniqueness methods, such as Lodash’s _.uniq or native JavaScript [...new Set(array)], must assume that duplicates can appear at any index across the collection. To track whether an element has been encountered before, these methods typically:

  1. Maintain an internal hash set or hash table of all previously seen values.
  2. Calculate hash keys or perform lookups for every incoming element.
  3. Allocate additional memory proportional to the number of unique elements (\(O(u)\) auxiliary space).

While this achieves an average time complexity of \(O(n)\), it incurs constant-factor overhead due to hash calculations, set insertions, and dynamic memory allocation.

The Core Optimization: Adjacent Value Comparison

The optimization in _.sortedUniq relies on a fundamental property of sorted sequences: all duplicate instances of any element are strictly contiguous. If an item appears multiple times, every occurrence must be adjacent to the others.

Because of this property, the algorithm does not need to remember every element it has ever seen. It only needs to remember the single most recent unique element added to the result.

How the Algorithm Executes

Internally, Lodash optimizes _.sortedUniq using a fast, single-pass pointer loop:

  1. Initialization: Lodash creates an empty result array. A temporary variable (often called seen or tracking the last index) stores the last accepted unique item.
  2. First Element Insertion: The first item of the input array is directly pushed to the result array because it has no predecessor.
  3. Linear Scan: The algorithm iterates through the remaining elements sequentially from index 1 to n - 1.
  4. Neighbor Comparison: For each item, it performs an equality check against the last item written to the result array using the SameValueZero comparison:
    • If the item differs from the previous item: It is unique. The item is pushed to the result array, and the "last seen" reference is updated to this new value.
    • If the item matches the previous item: It is a duplicate. The loop immediately skips to the next iteration without writing to the array or modifying state.
// Simplified conceptual implementation of _.sortedUniq
function simpleSortedUniq(array) {
  const length = array == null ? 0 : array.length;
  if (!length) {
    return [];
  }

  const result = [array[0]];
  let seen = array[0];

  for (let i = 1; i < length; i++) {
    const value = array[i];
    // SameValueZero check: handles standard equality and NaN values
    if (value !== seen && !(value !== value && seen !== seen)) {
      seen = value;
      result.push(value);
    }
  }

  return result;
}

Key Performance Advantages

1. Zero Auxiliary Tracking Structures

Generic deduplication requires allocating a hash table or a native Set. _.sortedUniq requires only a single variable to store the previous value. This reduces auxiliary space complexity to \(O(1)\) (excluding the returned array), avoiding garbage collection pressure and allocation latency.

2. Elimination of Lookup Overhead

Hashing and retrieving items from a Set or an object map involves internal bucket calculations, reference lookups, and collision handling. In _.sortedUniq, the lookup is replaced by a single scalar comparison against an active CPU register or local variable.

3. CPU Cache Locality

Because the loop accesses both the input array and the output array sequentially, it fully utilizes CPU L1/L2 cache prefetching. Random lookups in large hash maps often cause cache misses; sequential reads and writes in _.sortedUniq maximize cache line utilization.

When to Use _.sortedUniq

Use _.sortedUniq whenever the incoming dataset is already sorted—such as results returned from a database query with an ORDER BY clause, time-series data, or outputs from binary search operations. When sorting is not already guaranteed, using a standard Set-based approach like _.uniq or Array.from(new Set(arr)) is generally preferred, as sorting the array first (\(O(n \log n)\)) just to use _.sortedUniq would eliminate the algorithmic performance gains.