Hash Map: Two Sum

একটু বেশি memory খরচ করে অনেক বেশি speed পান: যা আগে দেখেছেন সেটা মনে রাখুন।

মূল ধারণা

ধরুন একটা পার্টিতে আপনি এমন দুজন অতিথি খুঁজছেন যাদের বয়সের যোগফল 30। ধীর উপায়: প্রতিটা অতিথিকে বাকি সবার সাথে মিলিয়ে দেখা। Smart উপায়: প্রতিজন অতিথি আসার সাথে সাথে জিজ্ঞেস করুন “(30 − আমার বয়স) বয়সের কেউ কি আগেই এসেছে?” আসা অতিথিদের একটা খাতা (hash map) রাখলে এই প্রশ্নের উত্তর সাথে সাথে পাওয়া যায়। উত্তর হ্যাঁ হলে কাজ শেষ। না হলে এই অতিথিকে খাতায় লিখে পরেরজনের কাছে যান।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Time complexity: O(n) – একবার পুরো list দেখা হয়, আর map-এর প্রতিটা lookup/insert গড়ে O(1)। Space complexity: O(n) – map-এ সব সংখ্যাই থাকতে পারে। Brute-force double loop-এ time complexity O(n²) কিন্তু space complexity O(1)।