DSA · INTERVIEW & OA PREP

Topic 2 of 12

Hashing & Two Pointers

Hash maps turn many O(n²) scans into O(n), and two pointers exploit sorted or paired structure. Together they solve a huge fraction of medium problems — recognising when to reach for each is the real skill.

Key concepts

• Hash map / set gives O(1) average lookup — use it to trade space for time.
• Count frequencies, detect duplicates, and group anagrams with a map.
• Two pointers on a sorted array find pairs/triplets without extra space.
• Know the difference between a hash set (membership) and hash map (key→value).

Questions that get asked

• Group anagrams together.
• 3-sum: find triplets summing to zero.
• First non-repeating character in a string.
• Contains duplicate within k distance.
• Subarray sum equals k (prefix sum + hash map).