32. Hashing - Problems

হ্যাশিং (Hashing) ব্যবহার করে অনেক ইন্টারভিউ প্রবলেম খুব দ্রুত (বিশেষ করে $O(n)$ সময়ে) সমাধান করা যায়। এখানে ৮টি জনপ্রিয় হ্যাশিং প্রবলেম নিয়ে আলোচনা করা হলো।

---

1. টু সাম প্রবলেম (Two Sum Problem)

একটি অ্যারে থেকে দুটি সংখ্যা খুঁজে বের করা যাদের যোগফল একটি নির্দিষ্ট সংখার (Target) সমান।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি খালি Hash Map তৈরি করুন।
2. অ্যারের প্রতিটি এলিমেন্ট num ট্রাভার্স করুন।
3. target - num অর্থাৎ বাকি অংশটি ম্যাপে আছে কি না চেক করুন।
4. যদি থাকে, তবে আপনি উত্তর পেয়ে গেছেন। না থাকলে num কে ম্যাপে ইনডেক্সসহ সেভ করুন।

Implementation

// Java Two Sum (Hashing)
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) return new int[]{map.get(complement), i};
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

# Python Two Sum (Hashing)
def two_sum(nums, target):
    mapping = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in mapping:
            return [mapping[complement], i]
        mapping[num] = i
    return [-1, -1]

---

2. সাব-অ্যারে সাম ০ (Subarray with Sum 0)

অ্যারেতে এমন কোনো সাব-অ্যারে আছে কি না যার এলিমেন্টগুলোর যোগফল ০।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• Prefix Sum + HashSet: অ্যারের প্রতিটি ইনডেক্স পর্যন্ত যোগফল (Prefix Sum) বের করুন। যদি একই প্রিফিক্স সাম দুইবার পাওয়া যায় অথবা প্রিফিক্স সাম ০ হয়, তবে সেখানে এমন একটি সাব-অ্যারে আছে যার যোগফল ০।

Implementation

// Java Subarray Sum 0
public boolean hasZeroSumSubarray(int[] arr) {
    Set<Integer> set = new HashSet<>();
    int sum = 0;
    for (int x : arr) {
        sum += x;
        if (sum == 0 || set.contains(sum)) return true;
        set.add(sum);
    }
    return false;
}

# Python Subarray Sum 0
def has_zero_sum_subarray(arr):
    s = set()
    current_sum = 0
    for x in arr:
        current_sum += x
        if current_sum == 0 or current_sum in s:
            return True
        s.add(current_sum)
    return False

---

3. লংগেস্ট সাব-অ্যারে সাম K (Longest Subarray with Sum K)

সবচেয়ে দীর্ঘ সেই সাব-অ্যারেটি খুঁজে বের করা যার যোগফল K।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি HashMap নিয়ে প্রিফিক্স সাম এবং তার ইনডেক্স স্টোর করুন।
2. প্রতিবার CurrentSum - K ভ্যালুটি ম্যাপে খুঁজুন।
3. যদি পাওয়া যায়, তবে বর্তমান ইনডেক্স এবং ম্যাপের ইনডেক্সের দূরত্ব বের করে ম্যাক্সিমাম লেন্থ আপডেট করুন।

---

4. ডিস্টিনক্ট এলিমেন্ট কাউন্ট (Count Distinct Elements)

একটি অ্যারেতে কয়টি ইউনিক বা অদ্বিতীয় এলিমেন্ট আছে তা বের করা।

💡 টিপস

পুরো অ্যারেটি একটি HashSet-এ পাঠিয়ে দিন। সেটের সাইজই হবে ইউনিক এলিমেন্টের সংখ্যা।

---

5. ফ্রিকুয়েন্সি কাউন্টিং (Frequency Counting)

অ্যারের প্রতিটি এলিমেন্ট কতবার করে আছে তা বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• একটি HashMap ব্যবহার করুন যেখানে Key হবে এলিমেন্ট এবং Value হবে তার কাউন্টার। প্রতিবার এলিমেন্টটি পেলে ম্যাপের কাউন্টার ১ বাড়িয়ে দিন।

Implementation

// Java Frequency Count
public Map<Integer, Integer> countFreq(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int x : arr) map.put(x, map.getOrDefault(x, 0) + 1);
    return map;
}

# Python Frequency Count
from collections import Counter
def count_freq(arr):
    return dict(Counter(arr))

---

6. ফার্স্ট রিপিটিং এলিমেন্ট (First Repeating Element)

অ্যারেতে কোন এলিমেন্টটি প্রথমবারের মতো দুইবার এসেছে (অথবা সর্বনিম্ন ইনডেক্সে রিপিট হয়েছে)।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• ডানদিক থেকে অ্যারে ট্রাভার্স করুন এবং প্রতিটি এলিমেন্ট একটি HashSet-এ স্টোর করুন। সর্বশেষ যে রিপিটিং এলিমেন্টটি পাবেন সেটিই হবে উত্তর।

---

7. গ্রুপ অ্যানাগ্রাম (Group Anagrams)

একই ক্যারেক্টার দিয়ে তৈরি ভিন্ন ভিন্ন শব্দগুলোকে একসাথে গ্রুপ করা। (যেমন: eat, tea, ate)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. প্রতিটি শব্দ অ্যালফাবেটিক্যালি সর্ট (Sort) করুন।
2. এই সর্টেড শব্দটিকে Key হিসেবে ব্যবহার করে HashMap-এ অরিজিনাল শব্দগুলো লিস্ট হিসেবে স্টোর করুন।

Implementation

// Java Group Anagrams
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] ca = s.toCharArray();
        Arrays.sort(ca);
        String key = String.valueOf(ca);
        if (!map.containsKey(key)) map.put(key, new ArrayList<>());
        map.get(key).add(s);
    }
    return new ArrayList<>(map.values());
}

# Python Group Anagrams
from collections import defaultdict
def group_anagrams(strs):
    mapping = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        mapping[key].append(s)
    return list(mapping.values())

---

8. লংগেস্ট কনসিকিউটিভ সিকোয়েন্স (Longest Consecutive Sequence)

একটি আন-সর্টেড অ্যারে থেকে সবচেয়ে দীর্ঘ পরপর থাকা সংখ্যার সিকোয়েন্স বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. সব এলিমেন্ট একটি HashSet-এ রাখুন।
2. প্রতিটি এলিমেন্ট x এর জন্য চেক করুন x-1 সেটে আছে কি না।
3. যদি না থাকে, তবে বুঝবেন এটি একটি সিকোয়েন্সের শুরু। এবার x+1, x+2... করে সিকোয়েন্সের দৈর্ঘ্য মাপুন।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

Problem	Time Complexity	Space Complexity
Two Sum	O(n)	O(n)
Count Distinct	O(n)	O(n)
Group Anagrams	O(n * k log k)	O(n * k)
Longest Consecutive	O(n)	O(n)

---

IMPORTANT

হ্যাশিং ব্যবহার করার ফলে ব্রুট-ফোর্স সলিউশন ($O(n^2)$) থেকে লিনিয়ার টাইমে ($O(n)$) সমস্যাগুলো সমাধান করা সম্ভব হয়।

---

TIP

যখনই কোনো সার্চিং বা ফ্রিকুয়েন্সি সংক্রান্ত প্রবলেম দেখবেন, প্রথমেই HashMap বা HashSet ব্যবহারের কথা ভাবুন।