একটু বেশি memory খরচ করে অনেক বেশি speed পান: যা আগে দেখেছেন সেটা মনে রাখুন।
ধরুন একটা পার্টিতে আপনি এমন দুজন অতিথি খুঁজছেন যাদের বয়সের যোগফল 30। ধীর উপায়: প্রতিটা অতিথিকে বাকি সবার সাথে মিলিয়ে দেখা। Smart উপায়: প্রতিজন অতিথি আসার সাথে সাথে জিজ্ঞেস করুন “(30 − আমার বয়স) বয়সের কেউ কি আগেই এসেছে?” আসা অতিথিদের একটা খাতা (hash map) রাখলে এই প্রশ্নের উত্তর সাথে সাথে পাওয়া যায়। উত্তর হ্যাঁ হলে কাজ শেষ। না হলে এই অতিথিকে খাতায় লিখে পরেরজনের কাছে যান।
9: দুটো সংখ্যার মধ্যে পরেরটা আসার সময় pair পাওয়া যায়। প্রথমটা আসার সময় কেন নয়?100: loop কোনো pair না পেয়েই শেষ হয়। শেষে map দেখতে কেমন?3, 3 আর target 6। এটা কেন কাজ করে?5 আর target 10 দিন। এটা কি ভুলভাবে নিজের সাথেই pair হয়? ক্রমটা দেখুন: lookup হয় store করার আগে।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)।