အခန်း ၅ - 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 တွေမှာ အများဆုံး သုံးပါတယ်။

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

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

ဘယ်အချိန်မှာ Two Pointers သုံးမလဲ

အောက်ပါ လက္ခဏာတွေ တွေ့ရင် Two Pointers ကို စဉ်းစားသင့်ပါတယ်။

• Array သို့မဟုတ် String ထဲက အတွဲ (pair) ဒါမှမဟုတ် အစု (triplet) ကို ရှာရတဲ့အခါ
• Data က Sorted (စီထားပြီးသား) ဖြစ်နေတဲ့အခါ — အစ/အဆုံးကနေ ချဉ်းကပ်လို့ ရတယ်
• Nested loop $O(n^2)$ နဲ့ ဖြေလို့ရပေမယ့် ပိုမြန်အောင် လုပ်ချင်တဲ့အခါ
• Extra space မယူရ ($O(1)$) လို့ ကန့်သတ်ထားတဲ့အခါ — HashMap သုံးလို့ မရတော့လို့

ပိုပြီး real-world feeling ရအောင် ဒီလိုချဲ့ရေးနိုင်ပါတယ်။

Real-world မှာ ဘယ်လိုသုံးလဲ

Two Pointers က Interview အတွက် Algorithm တစ်ခုလို့ပဲ ထင်ရပေမယ့် Production System တွေမှာ နေ့စဉ် သုံးနေတဲ့ Pattern တစ်ခုပါ။ အထူးသဖြင့် sorted data တွေ၊ streaming data တွေ၊ large dataset တွေကို memory များများ မသုံးဘဲ process လုပ်တဲ့အခါ အသုံးဝင်တယ်။

• Sorted list နှစ်ခု ပေါင်းခြင်း (Merge) — Database query နှစ်ခုက timestamp အလိုက် စီထားပြီးသား result တွေကို activity feed တစ်ခုအဖြစ် ပေါင်းတဲ့အခါ pointer နှစ်ခုနဲ့ တစ်ကြိမ်စီ ရှေ့တိုးသွားရုံပဲ လိုတယ်။ Data တစ်ခုစီကို တစ်ခါပဲ ဖတ်ရတဲ့အတွက် $O(n+m)$ နဲ့ အလုပ်ပြီးတယ်။ Merge Sort ရဲ့ merge step ကလည်း ဒီအယူအဆပဲ ဖြစ်တယ်။

• Sorted list နှစ်ခု နှိုင်းယှဉ်ခြင်း — System version နှစ်ခုကြား ပြောင်းလဲသွားတဲ့ record တွေကို ရှာခြင်း၊ user ID နှစ်စုရဲ့ intersection / difference ထုတ်ခြင်း၊ inventory list နှစ်ခုကို reconcile လုပ်ခြင်း စတဲ့နေရာတွေမှာ အသုံးများတယ်။ Hash Table မသုံးဘဲ memory သက်သာစွာနဲ့ scan တစ်ကြိမ်တည်း လုပ်နိုင်တယ်။

• Duplicate ဖယ်ခြင်း (In-place Deduplication) — Log file, user list, transaction record စတဲ့ sorted data တွေထဲက duplicate တွေကို array အသစ်မဆောက်ဘဲ ဖယ်ရှားနိုင်တယ်။ Slow pointer က valid data ရေးမယ့်နေရာကို ညွှန်ပြီး fast pointer က data ကို scan လုပ်တဲ့ pattern ကို database engine တွေ၊ ETL pipeline တွေမှာ မကြာခဏ တွေ့ရတယ်။

• Sliding Window Analysis — Time-series data, monitoring metric, stock price, sensor data တွေမှာ အချိန်ကာလတစ်ခုအတွင်း average, maximum, unique count စတာတွေကို တွက်ချက်တဲ့အခါ left/right pointer နှစ်ခုနဲ့ window ကို ရွှေ့သွားတယ်။ Log analytics နဲ့ observability platform တွေမှာ အသုံးများတဲ့ technique ဖြစ်တယ်။

• Streaming Data Processing — Kafka, Kinesis, RabbitMQ ကဲ့သို့ data stream တွေကို ဖတ်တဲ့အခါ record အားလုံး memory ထဲ မတင်နိုင်ဘူး။ Pointer နှစ်ခု သို့မဟုတ် iterator နှစ်ခုနဲ့ stream နှစ်ခုကို တစ်ပြိုင်နက်တည်း ဖတ်ပြီး compare, merge, join လုပ်ကြတယ်။

• Large File Comparison — Git, diff tool, synchronization software တွေက file version နှစ်ခုကို line-by-line နှိုင်းယှဉ်တဲ့အခါ pointer နှစ်ခုကို အသုံးပြုတယ်။ File တစ်ခုလုံး memory ထဲ တင်စရာမလိုဘဲ sequential scan လုပ်နိုင်လို့ performance ကောင်းတယ်။

• Network & Log Processing — Access log, event log, audit log တွေက အချိန်အစဉ်အတိုင်း စီထားလေ့ရှိတယ်။ Service A ရဲ့ log နဲ့ Service B ရဲ့ log ကို correlation လုပ်ပြီး request flow ကို ချိတ်ဆက်ကြည့်တဲ့အခါ timestamp အလိုက် pointer နှစ်ခုနဲ့ လိုက်ဖတ်တာက အထိရောက်ဆုံး နည်းလမ်းတစ်ခု ဖြစ်တယ်။

Two Pointers ရဲ့ အဓိက အားသာချက်က nested loop ကို linear scan အဖြစ် ပြောင်းပေးနိုင်ခြင်း ဖြစ်တယ်။ Data က sorted ဖြစ်နေပြီဆိုရင် Hash Map မလိုဘဲ memory သက်သာစွာနဲ့ $O(n)$ သို့မဟုတ် $O(n+m)$ အတွင်း ပြဿနာအများစုကို ဖြေရှင်းနိုင်တယ်။

ဒီ pattern တွေက အောက်က ပုစ္ဆာတွေမှာ ပြန်တွေ့ရမှာပါ။

Questions

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

Reverse String

Character array s တစ်ခုကို နေရာပို မယူဘဲ (in-place) ပြောင်းပြန် လှန်ပါ။

Example:

Input:  s = ['h','e','l','l','o']
Output: ['o','l','l','e','h']

ဒါက Two Pointers (Opposite Direction) ရဲ့ အရိုးရှင်းဆုံး ဥပမာပါ။ Left ကို အစ၊ Right ကို အဆုံးမှာ ထားပြီး အချင်းချင်း လဲ (swap) လိုက်တယ်။ ပြီးရင် နှစ်ခုလုံး အလယ်ဆီ တိုး/ဆုတ် သွားလိုက်ရုံပါပဲ။ Time $O(n)$၊ Space $O(1)$ ဖြစ်ပါတယ်။

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }
}

Remove Duplicates from Sorted Array

(အငယ်မှအကြီး) စီထားပြီးသား array nums ထဲက ထပ်နေတဲ့ ဂဏန်းတွေကို နေရာပို မယူဘဲ (in-place) ဖယ်ပြီး၊ ကျန်တဲ့ unique element အရေအတွက်ကို ပြန်ပေးပါ။

Example:

Input:  nums = [1,1,2,2,3]
Output: 3,  nums = [1,2,3,...]

ဒါက Same Direction (Slow & Fast) ရဲ့ classic ဥပမာပါ။ Array က စီထားပြီးသား ဖြစ်တဲ့အတွက် ထပ်နေတဲ့ ဂဏန်းတွေဟာ ဘေးချင်းကပ်လျက် ရှိနေမှာပါ။

• Fast pointer က array တစ်ခုလုံးကို ဖြတ်သွားပြီး element တိုင်းကို ကြည့်တယ်။
• Slow pointer က unique element တွေကို သိမ်းမယ့် နေရာကို ထိန်းတယ်။ Fast က အသစ်တစ်ခု (ရှေ့ကနဲ့ မတူတာ) တွေ့မှ slow ကို တိုးပြီး အဲဒီနေရာမှာ ရေးချတယ်။

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0; // unique element တွေ ဆုံးတဲ့ နေရာ

        for (int fast = 1; fast < nums.length; fast++) {
            // ရှေ့က element နဲ့ မတူမှ အသစ်လို့ သတ်မှတ်သည်
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }

        return slow + 1; // အရေအတွက် = နောက်ဆုံး index + 1
    }
}

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]]

ဒီပုစ္ဆာက ဂဏန်း ၃ လုံး ပေါင်းရင် 0 ရမယ့် အစုလေးတွေကို ရှာခိုင်းတာပါ။ ပုံမှန်ဆို 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.

ဒီပုစ္ဆာမှာ တိုင်လေးတွေကြားမှာ ရေ အများဆုံး လှောင်နိုင်မယ့် အကျယ်ပြန့်ဆုံး (Area အများဆုံး) ဧရိယာ ကို ရှာရမှာပါ။
ရေလှောင်နိုင်တဲ့ ပမာဏ = "အကျယ် (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;
    }
}