Two Pointers

দুটো nested loop-এর বদলে দুটো index pointer ব্যবহার করুন।

মূল ধারণা

ধরুন সংখ্যা লেখা কিছু পাথর sorted ক্রমে সাজানো আছে, আর দুজন মানুষ দুই প্রান্ত থেকে একে অপরের দিকে হাঁটছে। আপনার দরকার এমন দুটো পাথর যাদের যোগফল target-এর সমান। যোগফল খুব ছোট হলে বাঁ দিকের জন ডানে গিয়ে একটা বড় পাথরে দাঁড়ায়। খুব বড় হলে ডান দিকের জন বাঁয়ে গিয়ে একটা ছোট পাথরে দাঁড়ায়। প্রতিটা ধাপে একটা পাথর চিরতরে বাদ হয়ে যায়, তাই একবার পুরো list দেখলেই হয়।

একই কৌশলে list in place reverse করা যায়: দুই প্রান্তের মান swap করুন, দুটো pointer ভেতরের দিকে সরান, আর দেখা না হওয়া পর্যন্ত এটা repeat করুন।

Run করে দেখুন

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

সাধারণ ভুল

Complexity

Time complexity: O(n) – pointer শুধু ভেতরের দিকে যায়, তাই প্রতিটা item বড়জোর একবার দেখা হয়। Nested loop দিয়ে করলে লাগে O(n²)। Space complexity: O(1) – শুধু দুটো integer।