1.4 Hashing / Frequency Counting

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

"count", "frequency", "group by", "duplicate", "complement/pair sum", "first unique", O(1) lookup দরকার — O(n²) scan-কে O(n) এ নামানো

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

Demo: Longest Consecutive Sequence — LC 128 (Medium)

Statement (Demo): unsorted integer array nums দেওয়া — সবচেয়ে দীর্ঘ consecutive sequence (পর পর সংখ্যা) কতটুকু বলুন। O(n) সময়ে সমাধান করতে হবে। উদাহরণ: [100,4,200,1,3,2] → 4 | ⚡ n ≤ 10⁵, -10⁹ ≤ nums[i] ≤ 10⁹

Approach: সব সংখ্যা Set-এ ঢুকান। কেবল সেই সংখ্যা থেকে গোনা শুরু করুন যার x-1 নেই (মানে সেটাই sequence-এর শুরু) — তাহলে প্রতিটা এলিমেন্ট সর্বোচ্চ দুবার দেখা হয়, sort ছাড়াই O(n)।

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // sequence-এর শুরু না হলে 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 — সবার আগে এটা)
Statement: integer array nums ও integer target দেওয়া — দুটো সংখ্যার index বের করুন যাদের যোগফল target। একটাই solution আছে, একই index দুবার ব্যবহার করা যাবে না।
উদাহরণ: nums=[2,7,11,15], target=9 → [0,1] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Group Anagramsplan · দিন ০২৯ LC 49
(sorted string / freq-signature key)
Statement: string array strs দেওয়া — anagram-গুলোকে একসাথে গ্রুপ করুন। উত্তরের ক্রম যেকোনো হতে পারে।
উদাহরণ: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Valid Anagramplan · দিন ০০২ LC 242
Statement: দুটো string s ও t দেওয়া — t যদি s-এর anagram হয় true, নাহলে false return করুন। (Anagram মানে same character, same count।)
উদাহরণ: s="anagram", t="nagaram" → true | ⚡ len ≤ 5×10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
First Unique Character in a StringLC 387
Statement: lowercase string s দেওয়া — প্রথম non-repeating character-এর index বের করুন। না থাকলে -1।
উদাহরণ: s="leetcode" → 0 | ⚡ len ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
First Missing PositiveLC 41
(Hard — Meta High; index-as-hash trick, O(1) space)
Statement: unsorted integer array nums দেওয়া — সবচেয়ে ছোট missing positive integer বের করুন। O(n) time ও O(1) extra space।
উদাহরণ: [3,4,-1,1] → 2 | ⚡ n ≤ 10⁵, -2³¹ ≤ nums[i] ≤ 2³¹-1
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Max Points on a LineLC 149
(Hard — Google High; slope-কে hashmap key বানানো)
Statement: 2D plane-এ points array দেওয়া — একটা সরলরেখার উপর সর্বোচ্চ কতটা point থাকতে পারে বলুন।
উদাহরণ: [[1,1],[2,2],[3,3]] → 3 | ⚡ n ≤ 300
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Find the Index of the First Occurrence (strStr)LC 28
(advanced string matching: KMP/Z-algorithm শেখার entry point)
Statement: দুটো string haystack ও needle দেওয়া — haystack-এ needle-এর প্রথম occurrence-এর index বের করুন। না থাকলে -1।
উদাহরণ: haystack="sadbutsad", needle="sad" → 0 | ⚡ len ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন