Text Deduplication Algorithms — From O(n ) to O(n)

dev.to JavaScript2026-10-12 19:360 views

Text Deduplication Algorithms — From O(n²) to O(n)

Removing duplicate lines sounds trivial. The naive approach works for small inputs but breaks down at scale. Here's how to do it efficiently.

The Naive Approach: O(n²)

function dedupNaive(lines) { const result = []; for (const line of lines) { if (!result.includes(line)) { result.push(line); } } return result; }

Array.includes() is O(n), so this is O(n²) overall. For 10,000 lines, that's 50 million comparisons.

Using a Set: O(n)

function dedupWithSet(lines) { return [...new Set(lines)]; }

Set uses a hash table internally, giving O(1) average lookup. This is 100x faster for large inputs.

Case-Insensitive Deduplication

function dedupCaseInsensitive(lines) { const seen = new Set(); return lines.filter(line => { const key = line.toLowerCase(); if (seen.has(key)) return false; seen.add(key); return true; }); }

Preserving Original Case While Deduplicating

Keep the first occurrence's original case:

function dedupPreserveCase(lines) { const seen = new Set(); return lines.filter(line => { const key = line.trim().toLowerCase(); if (seen.has(key)) return false; seen.add(key); return true; }); }

Sort + Dedup

Sorting first, then deduplicating adjacent duplicates is O(n log n) but useful when you want sorted output:

function sortAndDedup(lines, caseInsensitive = false) { const sorted = [...lines].sort((a, b) => { const ca = caseInsensitive ? a.toLowerCase() : a; const cb = caseInsensitive ? b.toLowerCase() : b; return ca.localeCompare(cb); }); return sorted.filter((line, i) => { if (i === 0) return true; const prev = caseInsensitive ? sorted[i-1].toLowerCase() : sorted[i-1]; const curr = caseInsensitive ? line.toLowerCase() : line; return prev !== curr; }); }