<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. DSA
  3. Hashing and problem-solving techniques
All lessons in this course

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Lesson 20 of 50 14 minIntermediate

Solving problems with HashSet and Dictionary

Five patterns that turn O(n²) loops into a single O(n) pass: seen-before, counting, complement lookup, grouping by a key and set operations.

Many slow programs share the same shape: a loop inside a loop, where the inner loop searches for something. If that search can become a hash lookup, the inner loop disappears and O(n²) becomes O(n). This lesson collects the patterns you will use again and again.

Pattern 1: have I seen this before?

Duplicate detection with two loops compares every pair. With a HashSet you check each item once. HashSet.Add returns false when the value is already there, which makes the code very short.

Duplicates.cs
string[] ids = { "B-12", "C-7", "B-40", "C-7", "S-3", "B-12" }; var seen = new HashSet<string>();var duplicates = new List<string>();foreach (var id in ids)    if (!seen.Add(id))          // false: it was already in the set        duplicates.Add(id); Console.WriteLine(string.Join(", ", duplicates));
Output
C-7, B-12

Pattern 2: counting

A Dictionary<key, int> is a tally sheet. GetValueOrDefault returns 0 for a key that is not there yet, so one line counts everything.

Counting.cs
string[] sections = { "IPE200", "HEA160", "IPE200", "SHS100", "IPE200", "HEA160" }; var count = new Dictionary<string, int>();foreach (var s in sections)    count[s] = count.GetValueOrDefault(s) + 1; foreach (var (section, n) in count)    Console.WriteLine($"{section}: {n}");
Output
IPE200: 3
HEA160: 2
SHS100: 1

Pattern 3: look up the partner (complement)

The classic interview question “find two numbers that add up to a target” is O(n²) with two loops. Turn it around: for each value x, the partner you need is target − x. Keep a dictionary of the values seen so far and ask it for the partner.

Interactive

Find a pair with a dictionary

Beam offcuts (m). Which two make exactly the target length? Instead of trying every pair, remember what you have seen.

Target
List
[0]7[1]2[2]11[3]4[4]9[5]6[6]3[7]8
Dictionary<value, index> (what we have seen)
empty
Items looked at 0 · Nested loops, worst case 28 pairs
Goal: two items that add up to 10. Walk the list once. For each value, ask the dictionary for its partner 10 − value; if it is not there, remember the value.
TwoSum.cs
static (int, int)? TwoSum(int[] a, int target){    var indexOf = new Dictionary<int, int>();          // value -> index    for (int i = 0; i < a.Length; i++)    {        if (indexOf.TryGetValue(target - a[i], out int j))            return (j, i);                              // partner seen earlier        indexOf[a[i]] = i;    }    return null;} int[] lengths = { 7, 2, 11, 4, 9, 6, 3, 8 };Console.WriteLine(TwoSum(lengths, 10));Console.WriteLine(TwoSum(lengths, 30)?.ToString() ?? "none");
Output
(3, 5)
none

Notice the order: check for the partner before adding the current value. Otherwise, for a target of 8, the value 4 would pair with itself.

Pattern 4: group by a key

To put items into groups, compute a key for each item and use a Dictionary<key, List<item>>. The trick is choosing a key that is equal for items that belong together. For anagrams (same letters, different order), sorting the letters gives such a key: “listen” and “silent” both become “eilnst”.

Anagrams.cs
string[] words = { "listen", "silent", "enlist", "stone", "notes", "tones", "beam" }; var groups = new Dictionary<string, List<string>>();foreach (var w in words){    string key = new string(w.OrderBy(c => c).ToArray());   // sorted letters    if (!groups.TryGetValue(key, out var list))        groups[key] = list = new List<string>();    list.Add(w);} foreach (var g in groups.Values)    Console.WriteLine(string.Join(" ", g));
Output
listen silent enlist
stone notes tones
beam

LINQ’s GroupBy and ToLookup do exactly this internally.

Pattern 5: compare two collections

“Which beams in the design are not installed yet?” With lists that is a nested loop. HashSet has set operations built in: ExceptWith (difference), IntersectWith (common items), UnionWith and SetEquals.

SetCompare.cs
var designed = new HashSet<string> { "B-1", "B-2", "B-3", "B-4" };var installed = new HashSet<string> { "B-2", "B-4", "B-9" }; var missing = new HashSet<string>(designed);missing.ExceptWith(installed);                 // designed but not installed var unexpected = new HashSet<string>(installed);unexpected.ExceptWith(designed);               // installed but not in the design Console.WriteLine("Missing: " + string.Join(", ", missing));Console.WriteLine("Not in design: " + string.Join(", ", unexpected));
Output
Missing: B-1, B-3
Not in design: B-9
QuestionToolTime
Any duplicates? First repeat?HashSet.Add returns falseO(n)
How many of each?Dictionary<key, int>O(n)
Is there a partner that…?Dictionary<value, index>, look up the complementO(n)
Group items that belong togetherDictionary<key, List<T>> or GroupByO(n)
What is in A but not B?HashSet.ExceptWithO(n + m)
Quick check

You need to know whether any two drawings share the same title, among 200,000 drawings. Which is fastest?

Quick check

In TwoSum, what goes wrong if you add a[i] to the dictionary before looking up target − a[i]?

Practice

Write LongestConsecutive(int[] a) that returns the length of the longest run of consecutive whole numbers, in any order in the array, in O(n). For { 100, 4, 200, 1, 3, 2 } the run 1, 2, 3, 4 gives 4. For { 9, 1, 8, 7, 3 } the answer is 3.

Show a hint

Put everything in a HashSet. A number starts a run only if x − 1 is not in the set. From each start, count upwards while x + len is in the set. Each number is counted once in total.

Show the solution
Solution.cs
static int LongestConsecutive(int[] a){    var set = new HashSet<int>(a);    int best = 0;    foreach (int x in set)    {        if (set.Contains(x - 1)) continue;   // not the start of a run        int len = 1;        while (set.Contains(x + len)) len++;        best = Math.Max(best, len);    }    return best;} Console.WriteLine(LongestConsecutive(new[] { 100, 4, 200, 1, 3, 2 }));Console.WriteLine(LongestConsecutive(new[] { 9, 1, 8, 7, 3 }));
Output
4
3

Remember

  • If an inner loop only searches, replace it with a hash lookup: O(n²) becomes O(n).
  • HashSet.Add returning false detects repeats; Dictionary + GetValueOrDefault counts.
  • For pair problems, look up the complement in a dictionary of what you have already seen.
  • Group with a well-chosen key; compare collections with ExceptWith / IntersectWith. The cost is O(n) extra memory.
0 of 50 lessons completed