10. Two Pointer Technique

Two Pointer Technique অ্যারের সমস্যা সমাধানে অত্যন্ত কার্যকর। এতে দুটি পয়েন্টার ব্যবহার করে টাইম কমপ্লেক্সিটি অনেক কমিয়ে আনা যায়।

---

1. পেয়ার সাম (Pair Sum / Two Sum in Sorted Array)

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

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

1. দুটি পয়েন্টার নিন: left (শুরুতে) ও right (শেষে)।
2. ইনডেক্স দুটির ভ্যালু যোগ করুন (sum = arr[left] + arr[right])।
3. যদি sum == target হয়, তবে সমাধান পাওয়া গেল।
4. যদি sum < target হয়, তবে যোগফল বাড়ানোর জন্য left পয়েন্টার ডানে সরান।
5. যদি sum > target হয়, তবে যোগফল কমানোর জন্য right পয়েন্টার বামে সরান।

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

• Time Complexity: O(n) - লুপের সাহায্যে এক পাশ থেকে অন্য পাশে একবার আসা।
• Space Complexity: O(1)

// Java
public int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

# Python
def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

---

2. কন্টেইনার উইথ মোস্ট ওয়াটার (Container with Most Water)

দুটি লাইন বেছে নিতে হবে যাতে তাদের মাঝখানে সবচেয়ে বেশি পানি ধরে রাখা যায়।

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

1. দুটি পয়েন্টার নিন: একদম শুরুতে এবং একদম শেষে।
2. এরিয়া ক্যালকুলেট করুন: Area = (Difference of Indices) * (Minimum Height).
3. maxArea ট্র্যাক করুন।
4. পয়েন্টার সরানোর শর্ত: যে পয়েন্টারের হাইট ছোট, সেটিকে সরাতে হবে (ভবিষ্যতে বড় হাইট পাওয়ার আশায়)।

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

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

// Java
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1, maxArea = 0;
    while (left < right) {
        int h = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, h * (right - left));
        if (height[left] < height[right]) left++;
        else right--;
    }
    return maxArea;
}

# Python
def max_area(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        h = min(height[left], height[right])
        max_area = max(max_area, h * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

---

3. সর্ট কালারস (Sort Colors / Dutch National Flag)

০, ১ এবং ২ সমৃদ্ধ একটি অ্যারেকে সর্ট করা ($O(n)$ এ)।

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

1. তিনটি পয়েন্টার নিন: low (০ এর জন্য), mid (১ এর জন্য) এবং high (২ এর জন্য)।
2. যদি arr[mid] == 0 হয়, তবে low এবং mid সোয়াপ করুন এবং দুটিই এক ঘর বাড়ান।
3. যদি arr[mid] == 1 হয়, তবে শুধু mid এক ঘর বাড়ান।
4. যদি arr[mid] == 2 হয়, তবে mid এবং high সোয়াপ করুন এবং high এক ঘর কমান।

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

• Time Complexity: O(n) - মাত্র একবার অ্যারে ট্রাভার্স করতে হয়।
• Space Complexity: O(1)

Implementation

// Java
public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low++] = nums[mid];
            nums[mid++] = temp;
        } else if (nums[mid] == 1) mid++;
        else {
            int temp = nums[high];
            nums[high--] = nums[mid];
            nums[mid] = temp;
        }
    }
}

# Python
def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[high], nums[mid] = nums[mid], nums[high]
            high -= 1

---

IMPORTANT

টু-পয়েন্টার অ্যাপ্লাই করার আগে চেক করুন ডাটা সর্টেড কি না। সর্টেড না হলে এটি কাজ নাও করতে পারে।