Prompt
When implementing algorithms, prioritize reducing computational complexity before adding special cases or optimizing for specific scenarios. Key practices:
- Identify and eliminate O(n²) operations, especially nested loops and repeated array operations
- Use appropriate data structures based on access patterns
- Combine multiple passes into single operations where possible
Example - Converting O(n²) to O(n):
// Poor: O(n²) complexity with multiple array operations
selections = selections.filter((s, idx, arr) => {
return arr.map(sel => sel.endLineNumber)
.indexOf(s.endLineNumber) === idx;
});
// Better: O(n) complexity with single pass
const seen = new Set();
const uniqueSelections = [];
for (const selection of selections) {
if (!seen.has(selection.endLineNumber)) {
seen.add(selection.endLineNumber);
uniqueSelections.push(selection);
}
}
When using Set operations, ensure object identity works as expected for your data type. For complex objects like URIs, implement custom equality comparisons or use appropriate key extraction.