အခန်း ၄ - Two Pointers

Two Pointers ဆိုတာ သီးသန့် Data Structure တစ်ခု မဟုတ်ပါဘူး။ Array, String နဲ့ Linked List တွေမှာ တွေ့ရလေ့ရှိတဲ့ ပြဿနာတွေကို ဖြေရှင်းရာမှာ အသုံးပြုတဲ့ နည်းလမ်း (Algorithm Technique) တစ်ခု ဖြစ်ပါတယ်။ အထူးသဖြင့် ပုံမှန် Nested Loop နဲ့ $O(n^2)$ ကြာနိုင်တဲ့ ရှာဖွေမှု ပြဿနာတွေကို $O(n)$ သို့မဟုတ် $O(n \log n)$ အထိ လျှော့ချနိုင်တဲ့ နေရာမှာ အလွန် အသုံးဝင်ပါတယ်။

Two Pointers အလုပ်လုပ်ပုံကွဲများ

အဓိကအားဖြင့် Pointer ၂ ခုကို သုံးပြီး Data ကို ဖတ်ရှုတာ ဖြစ်ပါတယ်။ အသုံးအများဆုံး ပုံစံ ၂ မျိုး ရှိပါတယ်။

၁။ Opposite Direction (ဆန့်ကျင်ဘက်သို့ သွားခြင်း)

Pointer တစ်ခုကို အစ (left = 0) မှာ ထားပြီး၊ နောက်တစ်ခုကို အဆုံး (right = length - 1) မှာ ထားပါတယ်။ ပြီးရင် ပြဿနာရဲ့ အခြေအနေပေါ် မူတည်ပြီး အချင်းချင်း ဆုံတဲ့အထိ ရှေ့တိုး/နောက်ဆုတ် လုပ်သွားတဲ့ နည်းပါ။ ဒီနည်းလမ်းကို အများအားဖြင့် Sorted (စီစဉ်ပြီးသား) Array တွေမှာ အများဆုံး သုံးပါတယ်။

flowchart LR
    A[1] --- B[3] --- C[5] --- D[8] --- E[10] --- F[15]
    
    L["Left Pointer<br>(index: 0)"] -.-> A
    R["Right Pointer<br>(index: 5)"] -.-> F

၂။ Same Direction (ဦးတည်ရာ တူညီခြင်း - Fast & Slow Pointers)

Pointer ၂ ခုလုံး အစကနေပဲ စပါတယ်။ ဒါပေမယ့် တစ်ခုက အရှေ့ကနေ မြန်မြန်သွားပြီး (Fast pointer / Explorer) နောက်တစ်ခုက နှေးနှေးသွားတဲ့ (Slow pointer / Tracker) နည်းပါ။ မြန်တဲ့ကောင်က အရှေ့ကနေ လိုအပ်တဲ့ အခြေအနေကို လိုက်ရှာပေးပြီး၊ နှေးတဲ့ကောင်က လိုချင်တဲ့ နေရာရောက်တဲ့အခါ အလုပ်လုပ်တဲ့ သဘောမျိုးပါ။ တနည်းအားဖြင့် နောက်ပိုင်းတွေ့ရမည့် Sliding Window Technique မှာလည်း Same Direction သွားတဲ့ Two Pointers သဘောတရားကိုပဲ သုံးပါတယ်။

Questions

Two Pointers ကို ပိုမို နားလည်သွားစေဖို့ လက်တွေ့ အသုံးချရမယ့် လေ့ကျင့်ခန်း ပုစ္ဆာ တချို့ကို ကြည့်ရအောင်။

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Palindrome ဆိုတာ ရှေ့ကဖတ်ဖတ်၊ နောက်ကဖတ်ဖတ် အတူတူပဲ ဖြစ်နေတဲ့ စာသားကို ခေါ်တာပါ။ ဒီပုစ္ဆာမှာ စာလုံးအကြီးအသေး မခွဲခြားတဲ့အပြင်၊ စာသား (a-z) နဲ့ ဂဏန်း (0-9) ကလွဲပြီး ကျန်တဲ့ သင်္ကေတ (Symbols) တွေ အားလုံးကို ဖယ်ထုတ်/ကျော်သွားပြီး စစ်ရမှာပါ။

ဒီပြဿနာကို ဖြေရှင်းဖို့ Opposite Direction သုံးတဲ့ Two Pointers နည်းလမ်းက အကောင်းဆုံးပါ။ Left pointer ကို အစမှာထားပြီး Right pointer ကို အဆုံးမှာ ထားပါမယ်။ မလိုအပ်တဲ့ သင်္ကေတတွေ တွေ့ရင် ကျော်သွားပါမယ်။ နှစ်ခုလုံးက စာလုံးစစ်စစ် ဖြစ်တဲ့အခါ တူ/မတူ စစ်ဆေးပါမယ်။

$O(n)$ time complexity, space complexity $O(1)$ ဖြစ်ရပါမည်။

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // ဘယ်ဘက် pointer က စာလုံး/ဂဏန်း မဟုတ်ရင် ကျော်သွားမည်
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // ညာဘက် pointer က စာလုံး/ဂဏန်း မဟုတ်ရင် ကျော်သွားမည်
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            // အကြီးအသေး မခွဲဘဲ တိုက်စစ်မည်
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            // တူရင် ရှေ့ဆက်သွားမည်
            left++;
            right--;
        }

        return true;
    }
}

Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

ဒီပုစ္ဆာက Array & Hash Table အခန်း က Two Sum နဲ့ တူပါတယ်။ ဒါပေမယ့် ကွာခြားချက်တွေက—
၁။ Array က (အငယ်မှအကြီး) စီထားပြီးသား ဖြစ်နေတာ။
၂။ နေရာပို (Extra Space) လုံးဝ မယူရဘူး ($O(1)$ Space) ဆိုတာပါ။ Memory အသစ် မယူရတဲ့အတွက် HashMap ကို သုံးလို့ မရတော့ပါဘူး။

Array က စီထားပြီးသား ဖြစ်တဲ့အတွက် Two Pointers (Opposite Direction) ကို သုံးပြီး အလွယ်တကူ ဖြေရှင်းနိုင်ပါတယ်။ အစ (အငယ်ဆုံးတန်ဖိုး) နဲ့ အဆုံး (အကြီးဆုံးတန်ဖိုး) ကို ပေါင်းကြည့်ပါမယ်။

• ပေါင်းလဒ်က target ထက် ကြီးနေရင်၊ အဖြေကို သေးအောင် လုပ်ဖို့ လိုတဲ့အတွက် Right Pointer ကို တစ်ခန်း လျှော့ပါမယ်။
• ပေါင်းလဒ်က target ထက် ငယ်နေရင်၊ အဖြေကို ကြီးအောင် လုပ်ဖို့ လိုတဲ့အတွက် Left Pointer ကို တစ်ခန်း တိုးပါမယ်။

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

            if (currentSum == target) {
                // ပြဿနာက 1-indexed (index 1 ကနေစသည်) လို့ ဆိုထားသည့်အတွက် 1 ပေါင်းပေးရသည်
                return new int[] { left + 1, right + 1 };
            } else if (currentSum > target) {
                // ပေါင်းလဒ် များနေလျှင် တန်ဖိုးနည်းသွားစေရန် right ကို လျှော့သည်
                right--;
            } else {
                // ပေါင်းလဒ် နည်းနေလျှင် တန်ဖိုးများလာစေရန် left ကို တိုးသည်
                left++;
            }
        }

        return new int[] {};
    }
}

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

ဒီပုစ္ဆာက ဂဏန်း ၃ လုံး ပေါင်းရင် O ရမယ့် အစုလေးတွေကို ရှာခိုင်းတာပါ။ ပုံမှန်ဆို Loop ၃ ထပ် ပတ်ရမှာမိုလို့ $O(n^3)$ ဖြစ်သွားပါမယ်။
ပိုကောင်းတဲ့ ဖြေရှင်းနည်းကတော့ Array ကို အရင်ဆုံး Sort လုပ်လိုက်ပါမယ်။ Sort လုပ်လိုက်တဲ့အတွက် တူညီတဲ့ ဂဏန်းတွေဟာ ဘေးကပ်လျက် ရောက်သွားမှာဖြစ်ပြီး၊ Duplicate ဖြစ်နေတာတွေကို အလွယ်တကူ ကျော်သွား (Skip) လို့ ရသွားပါမယ်။
ပြီးရင် ဂဏန်းတစ်လုံးကို အသေထား (Loop ပတ်) ပြီး၊ ကျန်တဲ့ အပိုင်းကို "Two Sum II" မှာ သုံးခဲ့တဲ့ Two Pointers နည်းနဲ့ ဆက်ရှာသွားယုံပါပဲ။ Time Complexity $O(n^2)$ နဲ့ ရနိုင်ပါတယ်။

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // Two pointer သုံးရန်နှင့် Duplicate များ အလွယ်တကူဖယ်နိုင်ရန် Sort အရင်လုပ်သည်
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            // Duplicate ဖြစ်နေလျှင် ကျော်သွားမည်
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    // Duplicate အတွဲများ ထပ်မပါစေရန်
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return res;
    }
}

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the $i^{th}$ line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

ဒီပုစ္ဆာမှာ တိုင်လေးတွေကြားမှာ ရေ အများဆုံး လှောင်နိုင်မယ့် အကျယ်ပြန့်ဆုံး (Volume အများဆုံး) ဧရိယာ ကို ရှာရမှာပါ။
ရေလှောင်နိုင်တဲ့ ပမာဏ = "အကျယ် (Width) $\times$ ရေလှောင်နိုင်တဲ့ အမြင့်" ဖြစ်ပါတယ်။
ရေလှောင်နိုင်တဲ့ အမြင့် ဆိုတာ တိုင်နှစ်ခုစလုံးမှာ နိမ့်တဲ့တိုင် ရဲ့ အမြင့်ကို ယူရမှာပါ။ နိမ့်တဲ့အမြင့်ထက် ကျော်ရင် ရေတွေ လျှံကျသွားမှာ ဖြစ်လို့ပါ။

Two Pointers ကို အစနဲ့ အဆုံးမှာ ချထားပါမယ်။ အစနဲ့ အဆုံး ဆိုတော့ အကျယ် (Width) အကြီးဆုံး အခြေအနေကနေ စတာပါ။
ရေဆိုတာ နိမ့်တဲ့တိုင်ကိုပဲ အခြေခံတာ ဖြစ်တဲ့အတွက်၊ နိမ့်နေတဲ့ တိုင်ဘက်က Pointer ကို ရွေ့ပြီး ပိုမြင့်မယ့်တိုင်များ တွေ့မလား ဆိုတာကို ဆက်ရှာပါမယ်။

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // ရေလှောင်နိုင်သည့် အမြင့်သည် အနိမ့်ဆုံးတိုင်ပေါ် မူတည်သည်
            int minHeight = Math.min(height[left], height[right]);
            // အကျယ်
            int width = right - left;
            // ဧရိယာ (Area)
            int area = minHeight * width;
            maxArea = Math.max(maxArea, area);

            // ပိုမြင့်သည့် တိုင်ကို ရှာရန် နိမ့်သောဘက်မှ Pointer ကို ရွေ့သည်
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

ဒီပုစ္ဆာက "Container With Most Water" နဲ့ ဆင်ပေမယ့် ပိုခက်ပါတယ်။ လမ်းတွေ/မြေပြင်တွေ ခွက်နေတဲ့ အခါ ရေဘယ်လောက် အိုင်နိုင်လဲ ဆိုတာကို တွက်ရမှာပါ။
တိုင်တစ်တိုင်ရဲ့ အပေါ်မှာ ရေ ဘယ်လောက်တင်မလဲ ဆိုတာဟာ သူ့ရဲ့ ဘယ်ဘက်မှာ ရှိတဲ့ အမြင့်ဆုံးတိုင် (MaxLeft) နဲ့ ညာဘက်မှာ ရှိတဲ့ အမြင့်ဆုံးတိုင် (MaxRight) တွေထဲက နိမ့်တဲ့အမြင့် min(MaxLeft, MaxRight) ကနေ လက်ရှိ တိုင်အမြင့် ကို နှုတ်လိုက်တဲ့ ပမာဏပါပဲ။

နေရာပိုမယူဘဲ အချိန် $O(n)$ ၊ Space $O(1)$ နဲ့ တွက်ဖို့အတွက် Two Pointers ကို သုံးနိုင်ပါတယ်။
Left နဲ့ Right ကို အစဆုံး ချထားပြီး လမ်းလျှောက်ပါမယ်။ MaxLeft နဲ့ MaxRight ကို မှတ်သွားပါမယ်။
အကယ်၍ ကိုယ့်ရဲ့ MaxLeft က MaxRight ထက် ငယ်နေရင် ဘယ်ဘက်ကရေအိုင်ဖို့ သေချာနေပြီ ဖြစ်တဲ့အတွက် (ရေလျှံမသွားနိုင်ပါ) ဘယ်ဘက်ကို တွက်ပြီး တိုးပါတယ်။ ပြောင်းပြန်ဆိုရင်တော့ ညာဘက်ကို တွက်ပြီး လျှော့ပါမယ်။

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0;
        int right = height.length - 1;
        
        int maxLeft = height[left];
        int maxRight = height[right];
        
        int totalWater = 0;

        while (left < right) {
            // maxLeft က ပိုငယ်နေလျှင် ဘယ်ဘက်ရှိ ရေကို တွက်မည်
            if (maxLeft < maxRight) {
                left++;
                maxLeft = Math.max(maxLeft, height[left]);
                totalWater += maxLeft - height[left];
            } 
            // maxRight က ပိုငယ်နေလျှင် ညာဘက်ရှိ ရေကို တွက်မည်
            else {
                right--;
                maxRight = Math.max(maxRight, height[right]);
                totalWater += maxRight - height[right];
            }
        }

        return totalWater;
    }
}