Array Filtering, Reordering, And Pairwise Computation

What's being tested

These problems test array filtering, stable reordering, and pairwise computation using clear iteration and appropriate data structures. You should demonstrate correct handling of empty inputs, duplicates, ordering requirements, and time/space complexity without overengineering straightforward transformations.

Patterns & templates

• Filter then reverse — collect qualifying values in one pass, then reverse with [::-1] or two pointers; typically O(n) time and O(k) space.

• In-place compaction — use a write index to retain selected elements while scanning; reduces auxiliary space to O(1) when mutation is allowed.

• Preserve stable order — append values as encountered unless explicitly asked to reorder; never sort when reversal or original-relative ordering is required.

• Hash-set membership — store seen or target values for expected O(1) lookup; useful for pair-sum identification in O(n) time and O(n) space.

• Pairwise difference — compare every unordered pair with nested loops for O(n²) time; track the minimum rather than storing all differences.

• Sort for pair optimization — sorting enables adjacent comparisons or two pointers in O(n log n) time; only use it when original indices/order do not matter.

• Edge-case checklist — test empty and singleton arrays, no matches, all matches, duplicates, negatives, zero, and pairs that reuse or cannot reuse an element.

Common pitfalls

Pitfall: Sorting to find a result can silently violate requirements to preserve input order or return original indices.

Pitfall: Treating duplicate values as the same element can miss valid pairs or accidentally reuse one array position twice.

Pitfall: Claiming O(1) space while constructing a filtered or reversed output array; distinguish auxiliary space from the returned result.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.