1.4 Hashing / Frequency Counting

চিনবেন কীভাবে

"count", "frequency", "group by", "duplicate", "complement/pair sum", "first unique", O(1) lookup needed — turns an O(n²) scan into O(n)

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Longest Consecutive Sequence — LC 128 (Medium)

Statement (Demo): Given an unsorted integer array nums, return the length of the longest run of consecutive numbers. It must run in O(n). Example: [100,4,200,1,3,2] → 4 | ⚡ n ≤ 10⁵, -10⁹ ≤ nums[i] ≤ 10⁹

Approach: Put every number in a Set. Only start counting from a number whose x-1 is absent — that number is the start of a run. Each element is then touched at most twice, so it is O(n) without sorting.

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // not the start of a run → skip
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

Complexity: Time O(n), Space O(n)

প্রবলেম

Two Sumplan · দিন ০০১ LC 1
(complement lookup — do this one first)
Statement: Given an integer array nums and an integer target, return the indices of two numbers that add up to target. Exactly one solution exists; do not use the same index twice.
Example: nums=[2,7,11,15], target=9 → [0,1] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Group Anagramsplan · দিন ০০৮ LC 49
(sorted-string or frequency-signature key)
Statement: Given an array of strings strs, group the anagrams together. Any order is fine.
Example: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Valid Anagramplan · দিন ০১১ LC 242
Statement: Given strings s and t, return true if t is an anagram of s (same characters, same counts).
Example: s="anagram", t="nagaram" → true | ⚡ len ≤ 5×10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
First Unique Character in a StringLC 387
Statement: Given a lowercase string s, return the index of its first non-repeating character, or -1.
Example: s="leetcode" → 0 | ⚡ len ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
First Missing PositiveLC 41
(Hard — Meta High; index-as-hash trick, O(1) space)
Statement: Given an unsorted integer array nums, return the smallest missing positive integer in O(n) time and O(1) extra space.
Example: [3,4,-1,1] → 2 | ⚡ n ≤ 10⁵, -2³¹ ≤ nums[i] ≤ 2³¹-1
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Max Points on a LineLC 149
(Hard — Google High; slope as the hashmap key)
Statement: Given points on a 2D plane, return the largest number of points that lie on one straight line.
Example: [[1,1],[2,2],[3,3]] → 3 | ⚡ n ≤ 300
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Find the Index of the First Occurrence (strStr)LC 28
(entry point to KMP/Z-algorithm)
Statement: Given strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1.
Example: haystack="sadbutsad", needle="sad" → 0 | ⚡ len ≤ 10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে