algorithms

Two Pointers

Arkar Min Tun

Oct 22, 2023 • 2 min read

Two pointers ဆိုတာကတော့ array နဲ့ string problem တွေကို ဖြေရှင်းဖို့ အသုံးပြုလေ့ရှိတဲ့ technique တွေထဲက တခုပဲ ဖြစ်ပါတယ်။ နာမည်မှာပါတဲ့အတိုင်းပဲ ကျွန်တော်တို့ pointer ၂ခုကို အသုံးပြုပြီး string တွေ array တွေကို traverse လုပ်သွားတာမျိုး ဖြစ်ပါတယ်။

String (သို့) Array ရဲ့ အစနဲ့အဆုံးကနေ အလယ်မှာ ဆုံတဲ့အထိ တဆင့်ချင်း ရွေ့သွားတာမျိုးကိုတော့ အသုံးများပါတယ်။ တခြားနည်းတွေနဲ့လဲ traverse လုပ်တာမျိုးရှိပါတယ်။ အဓိကကတော့ pointer ၂ခုကို အသုံးပြုတာပဲ ဖြစ်ပါတယ်။

ဒီ technique ကို အသုံးပြုနိုင်တဲ့ problem တွေကတော့

Palindrome ဟုတ်မဟုတ် စစ်တာတွေ
String Reverse လုပ်တာတွေ
Sorted Two Sum စစ်တာတွေ
Sorted Array ၂ခုကို ပေါင်းတာတွေ
String subsequence စစ်တာတွေ စသဖြင့်မှာ အသုံးပြုလို့ရပါတယ်။

Palindrome

Palindrome ဆိုတာကတော့ string တခုကိုပဲ ရှေ့ကနေနောက်ထိ အစီအရီနဲ့ နောက်ကနေရှေ့ထိ အစီအရီ တူနေတာမျိုးပဲ ဖြစ်ပါတယ်။ ဥပမာ - racecar လိုမျိုး စကားလုံးဆို ရှေ့ကနေနောက်ကို ဖတ်တာနဲ့ နောက်ကနေ ရှေ့ကိုဖတ်တာ တူနေတာမျိုးပဲ ဖြစ်ပါတယ်။

Two pointer technique နဲ့ palindrome ဟုတ်မဟုတ် ဘယ်လိုစစ်မလဲဆိုတာ ကြည့်ကြည့်ရအောင်ပါ။

const isPalindrome = (arr) => {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    if(arr[left] !== arr[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

Complexities အနေနဲ့ကြည့်မယ်ဆိုလဲ time complexity O(n) နဲ့ space complexity O(1) ပဲရှိပါတယ်။ value တွေကို traverse လုပ်တဲ့နေရာမှာ တခုကို တခါစီပဲ လုပ်သွားတာဖြစ်ပြီး space အနေနဲ့ဆိုရင်လဲ left နဲ့ right pointer ၂ခုကိုပဲ အသုံးပြုသွားတာဖြစ်ပါတယ်။

String Reverse

ပေးထားတဲ့ string တခုကို reverse လုပ်တဲ့နေရာမှာလဲ two pointer technique ကို အသုံးပြုလို့ရပါတယ်။ အပေါ်မှာ ပြထားတဲ့ Palidrome အလုပ်လုပ်ပုံနဲ့ အနည်းငယ် ဆင်တူပါတယ်။ ဒီမှာတော့ value ချင်းကို ယှဥ်ကြည့်တာမျိုး မဟုတ်ဘဲ နေရာရွှေ့တာမျိုးနဲ့ လုပ်သွားတာပဲ ဖြစ်ပါတယ်။

const reverseString = (s) => {
  let i = 0, j = s.length - 1;
  let temp;
  while (i < j) {
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
    i++;
    j++;
  }
  return s;
}

Sorted Two Sum

ဒီ problem set မှာတော့ unique integer sorted array တခုပါဝင်ပြီး ကျွန်တော်တို့ target value ရအောင် ပေါင်းလို့ရမယ့် pair ပါမပါ စစ်တာမျိုးပဲ ဖြစ်ပါတယ်။ Two Sum problem set နဲ့မတူတာကတော့ ဒီ problem set မှာ ပါတဲ့ array က sorted ဖြစ်နေတာပဲ ဖြစ်ပါတယ်။ ဒီတော့ ကျွန်တော်တို့ brute force နည်းနဲ့ array ကို loop ၂ခါလုပ်ပြီး (O(n^2) complexitiy) စစ်တာထက် two pointer technique ကို အသုံးပြုပြီး စစ်လို့ရပါတယ်။

const checkTarget = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;

  while(left < right) {
    let sum = arr[left] + arr[right];
    if(sum === target) {
      return true;
    }

    if(sum > target) {
      right--;
    } else {
      left++;
    }
  }

  return false;
}

Combine Two Sorted Arrays

Two pointer ကို array ရဲ့ ရှေ့ဆုံးနဲ့ နောက်ဆုံးမှာ သုံးတာမျိုးမဟုတ်ဘဲ တခြားပုံစံနဲ့လဲ သုံးလို့ရပါသေးတယ်။ အခုပြောသွားမယ့် problem set ကတော့ sorted array ၂ခုကိုပေါင်းပြီး sorted array ၁ခုရအောင် ဘယ်လိုလုပ်ရမလဲဆိုတာပဲ ဖြစ်ပါတယ်။

const combine = (arr1, arr2) => {
  let result = [];
  let i = 0, j = 0;

  while(i < arr1.length && j < arr2.length) {
    if(arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  while(i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }

  while(j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  return result;
}

Is Subsequence

ဒီ problem set မှာတော့ string ၂ခုပါဝင်ပြီးတော့ ပေးထားတဲ့ string တစ်ခုဟာ နောက် string တစ်ခုရဲ့ value တွေ အစဥ်လိုက်ပါဝင်လား မပါဝင်လား စစ်ရတာမျိုးပဲ ဖြစ်ပါတယ်။ ဆိုလိုတာကတော့ string တခုက value တချို့ကို ဖယ်ထုတ်လိုက်ရင် နောက် string တခုနဲ့ တူနိုင်မလားဆိုတာမျိုးပဲ ဖြစ်ပါတယ်။ ဥပမာ - "ahbgdc" ဆိုတဲ့ string ဟာ "abc" ဆိုတဲ့ string တွေပါဝင်တဲ့ subsequence ပဲ ဖြစ်ပါတယ်။ h, g, d ဆိုတာတွေ ဖယ်လိုက်တဲ့အခါ "ahbgdc" ကနေ "abc" အဖြစ်ပြောင်းလဲ သွားနိုင်လို့ပဲ ဖြစ်ပါတယ်။

const isSubsequence = (s, t) => {
  let i = 0, j = 0;
  while(i < s.length && j < t.length) {
    if(s[i] === t[j]) {
      i++;
    }
    j++;
  }

  return i === s.length;
}