Master dictionary-based problem-solving patterns including frequency counting, bijection mapping, cycle detection, and complement strategies. Solve 15 essential LeetCode and Codility problems with complete C# implementations.
Hash maps and sets provide constant-time lookups and enable pattern-based solutions across counting, grouping, and relationship problems.
Average O(1) lookup, insertion, deletion. TryGetValue pattern prevents exceptions and is idiomatic C#.
var freq = new Dictionary<int, int>(); if (!freq.TryGetValue(num, out int count)) count = 0; freq[num] = count + 1;
O(1) Contains, Add, Remove. No duplicates. Use for deduplication and membership testing.
var seen = new HashSet<int>(); if (!seen.Add(num)) { // Duplicate found }
Find element appearing odd number of times. Codility ★
Given array where every element except one appears even times, return the single odd-occurrence element. All other integers appear even times.
a ^ a = 0 and a ^ 0 = a. XOR all elements—pairs cancel, leaving the odd one.
public int OddOccurrences(int[] arr) { int result = 0; foreach (int num in arr) result ^= num; return result; }
Find element appearing > n/2 times. Codility ★★
Find majority element appearing > n/2 times, or -1 if none exists.
Track candidate with a count. Increment for matches, decrement otherwise. When count hits 0, switch candidate. Verify the final candidate.
public int Dominator(int[] arr) { int candidate = -1, count = 0; // Find candidate foreach (int num in arr) { if (count == 0) candidate = num; count += (num == candidate) ? 1 : -1; } // Verify candidate count = 0; foreach (int num in arr) if (num == candidate) count++; return (count * 2 > arr.Length) ? candidate : -1; }
Partition strings into anagram groups. LeetCode 49 ★★
Given list of strings, group anagrams together. Return list of groups.
Sort each string's characters. Identical anagrams have identical sorted forms. Use sorted form as dict key to group.
public IList<IList<string>> GroupAnagrams(string[] strs) { var groups = new Dictionary<string, List<string>>(); foreach (string s in strs) { char[] sorted = s.ToCharArray(); Array.Sort(sorted); string key = new string(sorted); if (!groups.ContainsKey(key)) groups[key] = new List<string>(); groups[key].Add(s); } return new List<IList<string>>(groups.Values); }
n = number of strings, k = max string length
Return k most frequent elements. LeetCode 347 ★★
Given array and k, return k most frequent elements. Assume k ≤ unique elements.
Count frequencies. Create array of buckets indexed by frequency. Elements can appear 1 to n times. Collect from high-frequency buckets down.
public int[] TopKFrequent(int[] nums, int k) { var freq = new Dictionary<int, int>(); foreach (int n in nums) { if (!freq.TryGetValue(n, out int c)) c = 0; freq[n] = c + 1; } var buckets = new List<int>[nums.Length + 1]; for (int i = 0; i < buckets.Length; i++) buckets[i] = new List<int>(); foreach (var pair in freq) buckets[pair.Value].Add(pair.Key); var result = new List<int>(); for (int i = buckets.Length - 1; i >= 0 && result.Count < k; i--) result.AddRange(buckets[i]); return result.ToArray(); }
Find longest streak of consecutive numbers. LeetCode 128 ★★
Given unsorted array, return length of longest consecutive elements sequence. O(n) time.
Store all nums in HashSet. For each number, if it's a sequence start (num-1 not in set), expand right counting consecutive numbers.
public int LongestConsecutive(int[] nums) { if (nums.Length == 0) return 0; var numSet = new HashSet<int>(nums); int maxLen = 0; foreach (int num in numSet) { // Only start from sequence beginning if (!numSet.Contains(num - 1)) { int current = num; int streak = 1; while (numSet.Contains(current + 1)) { current++; streak++; } maxLen = Math.Max(maxLen, streak); } } return maxLen; }
Each element visited once during expansion (amortized)
Check if two strings are anagrams. LeetCode 242 ★
Given two strings s and t, return true if t is anagram of s (same characters, different order).
Count chars in s. Decrement counts for chars in t. If all counts are 0, they're anagrams.
public bool IsAnagram(string s, string t) { if (s.Length != t.Length) return false; int[] freq = new int[26]; for (int i = 0; i < s.Length; i++) { freq[s[i] - 'a']++; freq[t[i] - 'a']--; } foreach (int f in freq) if (f != 0) return false; return true; }
Fixed array size 26 (alphabet)
Check if strings follow same character mapping. LeetCode 205 ★
Two strings s and t are isomorphic if chars map one-to-one (bijection). E.g., "badc" and "baba" map a→b, b→a, d→b, c→a.
Track s→t and t→s mappings. For each pair, check consistency in both directions. If conflict, return false.
public bool IsIsomorphic(string s, string t) { var sToT = new Dictionary<char, char>(); var tToS = new Dictionary<char, char>(); for (int i = 0; i < s.Length; i++) { char c1 = s[i], c2 = t[i]; if (sToT.ContainsKey(c1)) { if (sToT[c1] != c2) return false; } else { sToT[c1] = c2; } if (tToS.ContainsKey(c2)) { if (tToS[c2] != c1) return false; } else { tToS[c2] = c1; } } return true; }
Max 26 keys per dict (alphabet)
Find first char appearing once. LeetCode 387 ★
Given string s, return index of first char appearing only once. Return -1 if none.
Pass 1: Count frequency of all chars. Pass 2: Scan left-to-right, return index of first char with frequency 1.
public int FirstUniqChar(string s) { var freq = new Dictionary<char, int>(); // Count frequencies foreach (char c in s) { if (!freq.TryGetValue(c, out int count)) count = 0; freq[c] = count + 1; } // Find first non-repeating for (int i = 0; i < s.Length; i++) { if (freq[s[i]] == 1) return i; } return -1; }
Max 26 keys (lowercase letters)
Count subarrays with sum = k. LeetCode 560 ★★
Given array of integers and integer k, return count of contiguous subarrays with sum = k.
Track cumulative sums. For each position, check if (cumSum - k) exists in map. If yes, all subarrays ending here with that prefix sum have target sum.
public int SubarraySum(int[] nums, int k) { var sumCount = new Dictionary<int, int>(); sumCount[0] = 1; // Base case int cumSum = 0, count = 0; foreach (int num in nums) { cumSum += num; int target = cumSum - k; if (sumCount.TryGetValue(target, out int freq)) count += freq; if (!sumCount.TryGetValue(cumSum, out int c)) c = 0; sumCount[cumSum] = c + 1; } return count; }
Count quadruplets with sum = 0. LeetCode 454 ★★
Given 4 arrays nums1-4, count tuples (i,j,k,l) where nums1[i]+nums2[j]+nums3[k]+nums4[l]=0.
Compute all pair sums from nums1+nums2, store in map. For each pair from nums3+nums4, check if its negation exists in map.
public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { var sumMap = new Dictionary<int, int>(); // Store all pair sums from nums1 + nums2 for (int i = 0; i < nums1.Length; i++) { for (int j = 0; j < nums2.Length; j++) { int sum = nums1[i] + nums2[j]; if (!sumMap.TryGetValue(sum, out int c)) c = 0; sumMap[sum] = c + 1; } } int count = 0; for (int k = 0; k < nums3.Length; k++) { for (int l = 0; l < nums4.Length; l++) { int needed = -(nums3[k] + nums4[l]); if (sumMap.TryGetValue(needed, out int cnt)) count += cnt; } } return count; }
n = array length (all same size)
Implement Least-Recently-Used cache. LeetCode 146 ★★★
Design cache with get(key) and put(key,val). Both O(1). Evict least-recently-used when capacity exceeded.
Dict maps key→node. LinkedList maintains LRU order (most recent at tail). On access, move to tail. On full, evict head.
public class LRUCache { private class Node { public int Key, Val; public Node Prev, Next; } private Node head, tail; private Dictionary<int, Node> cache; private int capacity; public LRUCache(int capacity) { this.capacity = capacity; cache = new Dictionary<int, Node>(); head = new Node(); tail = new Node(); head.Next = tail; tail.Prev = head; } public int Get(int key) { if (!cache.ContainsKey(key)) return -1; Node node = cache[key]; MoveToTail(node); return node.Val; } public void Put(int key, int value) { if (cache.ContainsKey(key)) { Node node = cache[key]; node.Val = value; MoveToTail(node); } else { Node newNode = new Node { Key = key, Val = value }; cache[key] = newNode; AddToTail(newNode); if (cache.Count > capacity) { Node lru = head.Next; Remove(lru); cache.Remove(lru.Key); } } } private void MoveToTail(Node node) { Remove(node); AddToTail(node); } private void AddToTail(Node node) { node.Prev = tail.Prev; node.Next = tail; tail.Prev.Next = node; tail.Prev = node; } private void Remove(Node node) { node.Prev.Next = node.Next; node.Next.Prev = node.Prev; } }
Check if word sequence matches pattern bijection. LeetCode 290 ★
Given pattern and words, check if words follow pattern with bijection. E.g., pattern="abba", words=["redbluebluered"] should match.
Map pattern char→word and word→char. Ensure one-to-one correspondence. Reject if mapping conflicts arise.
public bool WordPattern(string pattern, string s) { string[] words = s.Split(' '); if (pattern.Length != words.Length) return false; var patToWord = new Dictionary<char, string>(); var wordToPat = new Dictionary<string, char>(); for (int i = 0; i < pattern.Length; i++) { char c = pattern[i]; string w = words[i]; if (patToWord.ContainsKey(c)) { if (patToWord[c] != w) return false; } else { patToWord[c] = w; } if (wordToPat.ContainsKey(w)) { if (wordToPat[w] != c) return false; } else { wordToPat[w] = c; } } return true; }
n = pattern length
Detect if repeated sum-of-squares reaches 1 or cycles. LeetCode 202 ★
Repeat: replace number with sum of squares of digits. Return true if reaches 1, false if cycles.
Track seen sums. If we revisit a sum, we're in a cycle (not happy). If reach 1, happy.
public bool IsHappy(int n) { var seen = new HashSet<int>(); while (n != 1 && !seen.Contains(n)) { seen.Add(n); n = GetNext(n); } return n == 1; } private int GetNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; }
Cycle size bounded by digit sum patterns
Find common elements in two arrays. LeetCode 350 ★
Given two arrays, return array of their intersection. Each element in result appears as many times as in both arrays.
Count freq of shorter array. Iterate longer array, matching and decrementing counts.
public int[] Intersect(int[] nums1, int[] nums2) { if (nums1.Length > nums2.Length) return Intersect(nums2, nums1); var freq = new Dictionary<int, int>(); foreach (int n in nums1) { if (!freq.TryGetValue(n, out int c)) c = 0; freq[n] = c + 1; } var result = new List<int>(); foreach (int n in nums2) { if (freq.TryGetValue(n, out int cnt) && cnt > 0) { result.Add(n); freq[n]--; } } return result.ToArray(); }
Find all duplicates in 1-n array in-place. LeetCode 442 ★★
Given array of n integers [1,n], find all duplicates appearing twice. Use O(1) space (in-place).
Use array indices as hash. For each num, mark arr[num-1] as negative. If already negative, num is duplicate.
public IList<int> FindDuplicates(int[] nums) { var result = new List<int>(); foreach (int num in nums) { int idx = Math.Abs(num) - 1; if (nums[idx] < 0) { // Already marked, so num is duplicate result.Add(Math.Abs(num)); } else { // Mark as visited nums[idx] = -nums[idx]; } } return result; }
Excludes output list space