အခန်း ၄ - Hash Table / Dictionary

Hashing

Hashing ဆိုတာ Data တစ်ခုကို သတ်မှတ်ထားသော Function တစ်ခု (Hash Function) မှတဆင့် ဖြတ်ကာ သိမ်းဆည်းမည့် နေရာ (Index) တွေ ရှာဖွေသည့် နည်းစနစ်ပါ။ ရလဒ်ကတော့ $O(1)$ ဖြင့် Data ထည့်ခြင်း၊ ရှာဖွေခြင်း၊ ဖျက်ခြင်း ပြုလုပ်နိုင်ခြင်း ဖြစ်ပါတယ်။

Hash Function

Hash Function ဆိုတာ Key တစ်ခုကို Integer (Index) တစ်ခုအဖြစ် ပြောင်းပေးသည့် Function ပါ။ ဥပမာ —

index = key % tableSize
// key=25, tableSize=10  =>  index = 25 % 10 = 5

Hash Function ကောင်းတစ်ခုမှာ အောက်ပါ ဂုဏ်သတ္တိ (properties) တွေ ရှိရပါမယ်။

Deterministic — တူညီသော Input ကို အမြဲ တူညီသော Output ထုတ်ပေးရမည်
Uniform Distribution — Data တွေကို Array တစ်ခုလုံးမှာ ညီညာအောင် ဖြန့်ကျက်ပေးရမည်
Fast Computation — Hash တွက်ချက်ချိန် $O(1)$ ဖြစ်ရမည်

Hash Table

Hash Table ဆိုတာ Hash Function ကို အသုံးပြု၍ Key-Value Pair တွေ သိမ်းသည့် Data Structure (Concept) ပါ။ လက်တွေ့အသုံးပြုရာမှာတော့ Hash Table နဲ့ Hash Map ဆိုတဲ့ စကားလုံးနှစ်ခုကို သဘောတရား အတူတူပဲလို့ မှတ်ယူပြီး အပြန်အလှန် (interchangeably) သုံးလေ့ရှိပါတယ်။

Java မှာဆိုရင် HashMap ဆိုတာ Hash Table ရဲ့ အဓိက Implementation တစ်ခု ဖြစ်ပါတယ်။

မှတ်ချက် - Java မှာ Hashtable ဆိုတဲ့ Thread-safe ဖြစ်တဲ့ class အဟောင်းတစ်ခု ရှိပေမယ့်၊ ယခုအခါမှာတော့ ပိုမြန်တဲ့ HashMap ကိုသာ အများဆုံး အသုံးပြုကြပါတယ်။

Concept အရ Hash Table လို့ ခေါ်ပြီး၊ ကုဒ်ရေးတဲ့အခါ Hash Map လို့ ခေါ်ပါတယ်။

import java.util.HashMap;
 
public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
 
        // Data ထည့်ခြင်း - O(1) average
        map.put("apple", 3);
        map.put("banana", 5);
        map.put("cherry", 1);
 
        // Data ရှာဖွေခြင်း - O(1) average
        System.out.println(map.get("apple")); // 3
 
        // Key ရှိမရှိ စစ်ဆေးခြင်း
        System.out.println(map.containsKey("banana")); // true
 
        // Data ဖျက်ခြင်း - O(1) average
        map.remove("cherry");
 
        // Key အားလုံး Iterate လုပ်ခြင်း - O(n)
        for (String key : map.keySet()) {
            System.out.println(key + " -> " + map.get(key));
        }
    }
}

Collision

Key နှစ်ခု မတူညီသော်လည်း Hash Function မှ တူညီသော Index ထုတ်ပေးသောအခါ Collision(ထပ်မိခြင်း) ဖြစ်ပါသည်။ ဥပမာ key=5 နှင့် key=15 တို့ကို tableSize=10 ဖြင့် hash လုပ်ပါက နှစ်ခုလုံး index 5 ကို ရရှိသည်။ Collision ကို ဖြေရှင်းသည့် နည်းလမ်းများမှာ —

Chaining — တူညီသော Index တွင် Linked List ဖြင့် Data များ ချိတ်ဆက် သိမ်းဆည်းခြင်း (Linked List အကြောင်းကို အခန်း ၈ တွင် ဖော်ပြပါမည်)
Open Addressing — Collision ဖြစ်ပါက အနီးစပ်ဆုံး လွတ်နေသော Index ကို ရှာဖွေ သိမ်းဆည်းခြင်း

Open Addressing (နေရာ ရှာဖွေ သိမ်းဆည်းခြင်း)

Collision ဖြစ်ပါက Linked List မသုံးဘဲ Table ထဲတွင်ပင် နောက် index ကို ရှာ၍ သိမ်းပါသည်။ နည်းလမ်း ၃ မျိုး ကို အသုံးပြုသည်။

Linear Probing — collision ဖြစ်ရင် index + 1, +2, +3 အတိုင်း တစ်ခုချင်း ရှာခြင်း
Quadratic Probing — +1², +2², +3² ကွာဟချက်ဖြင့် ရှာခြင်း (clustering လျော့ချစေသည်)
Double Hashing — ဒုတိယ hash function တစ်ခု သုံး၍ ကွာဟချက် ရှာခြင်း

တို့ ဖြစ်သည်။

HashSet

HashSet ဆိုတာ HashMap ရဲ့ Key များသာ သိမ်းသည့် Version တစ်ခုပါ (Value မသိမ်း)။ ထပ်တလဲလဲ ရောက်လာသော Element များကို အလိုအလျောက် ဖယ်ရှားပေးသောကြောင့် Unique Element များ ထိန်းသိမ်းရာတွင် အသုံးဝင်သည်။

import java.util.HashSet;
 
HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("apple");  // ဒုတိယ "apple" ထပ်မထည့်ဘူး
set.add("banana");
System.out.println(set.contains("apple")); // true - O(1)
System.out.println(set.size());            // 2

Time Complexity

Operation	Average Case	Worst Case
put / add	$O(1)$	$O(n)$
get / contains	$O(1)$	$O(n)$
remove	$O(1)$	$O(n)$
size	$O(1)$	$O(1)$
iterate	$O(n)$	$O(n)$

မှတ်ချက်: Worst Case $O(n)$ ဆိုသည်မှာ Hash Collision အများကြီး ဖြစ်ပေါ်သောကြောင့် ဖြစ်ပါသည်။ ကောင်းမွန်သော Hash Function ဖြင့် Collision ကို နည်းစေ၍ Average $O(1)$ ကို ထိန်းသိမ်းနိုင်ပါသည်။

Hashing အသုံးပြုသည့် အခြေအနေများ

Duplicate Detection — HashSet ဖြင့် O(n) ကြာသော ကြည့်ရှုမှုကို $O(1)$ ဖြစ်စေနိုင်သည်
Frequency Count — HashMap ဖြင့် Key=Element, Value=Count ထားကာ $O(n)$ တစ်ကြိမ်ဖြတ်ကာ ရေတွက်နိုင်သည်
Two Sum ကဲ့သို့သော ပြဿနာများ — Array ကို Loop ပတ်ကာ Complement ကို HashMap တွင် စစ်ဆေးခြင်း
Cache / Memoization — Caching သဘောတရားအရ တွက်ချက်မှု ရလဒ်များကို HashMap တွင် သိမ်းကာ ထပ်တွက်မနေစေရ

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

Hash Table ကို နေ့စဉ် coding မှာ ဘယ်လိုသုံးလဲ ကြည့်ရအောင်။ Backend / Frontend development မှာ အသုံးအများဆုံးက lookup ပါ။

၁။ ID နဲ့ Object ရှာခြင်း (Lookup) — Database ကနေ user list ဆွဲထုတ်ပြီး userId နဲ့ ထပ်ခါထပ်ခါ ရှာရတဲ့အခါ List ကို loop ပတ်ရင် တစ်ကြိမ်လျှင် $O(n)$ ဖြစ်တယ်။ Map ထဲ တစ်ခါထည့်ထားရင် ရှာတိုင်း $O(1)$ ဖြစ်သွားတယ်။

// List ထဲ loop ပတ်ရှာ → ရှာတိုင်း O(n)
// Map ထဲ index လုပ်ထား → ရှာတိုင်း O(1)
Map<Integer, User> userById = new HashMap<>();
for (User u : users) {
    userById.put(u.getId(), u);
}

User u = userById.get(42); // O(1)

အလားတူ productId → product, permission → allowed? တို့ကိုလည်း Map နဲ့ index လုပ်ထားလေ့ ရှိတယ်။

၂။ Status code အလိုက် API error ရေတွက်ခြင်း (Frequency Count) — Log တွေထဲက error တွေကို status code အလိုက် ဘယ်နှစ်ကြိမ် ဖြစ်လဲ ရေတွက်ဖို့ Map ကို key=statusCode, value=count ထားပြီး တစ်ကြိမ်ဖြတ်ရုံပါပဲ။

Map<Integer, Integer> errorCount = new HashMap<>();
for (int status : responseStatuses) {
    if (status >= 400) {
        errorCount.merge(status, 1, Integer::sum); // count[status] += 1
    }
}
// {404: 12, 500: 3, ...}

ဒီ "Map နဲ့ ရေတွက်တယ်" ဆိုတဲ့ pattern က နောက်က Valid Anagram, Top K Frequent ပုစ္ဆာတွေမှာ ပြန်တွေ့ရမှာပါ။

၃။ တွက်ပြီးသားကို ပြန်မတွက်ခြင်း (Cache) — တူညီတဲ့ input အတွက် ထပ်ခါထပ်ခါ တွက်နေမယ့်အစား ရလဒ်ကို Map ထဲ သိမ်းထားလိုက်တယ်။ ဒုတိယအခါ ခေါ်ရင် Map ထဲက တန်းထုတ်ပေးနိုင်ပါတယ်။

Map<Integer, Long> cache = new HashMap<>();

long compute(int n) {
    if (cache.containsKey(n)) return cache.get(n); // cache hit - O(1)

    long result = expensiveWork(n);  // ပထမအကြိမ်မှာသာ တွက်တယ်
    cache.put(n, result);
    return result;
}

ဒါက Dynamic Programming အခန်းမှာ ပြောမယ့် Memoization ရဲ့ အခြေခံပါပဲ။

Questions

Array နှင့် Hash Table , Hash Set တို့ကို သိပြီ ဆိုလျှင် ကျွန်တော်တို့ တချို့ ပုစ္ဆာ တွေကို ကြည့်ရအောင်။

Contains Duplicate

Array ထဲတွင် duplicate ရှိမရှိ ရှာပါ။

ဥပမာ

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

Output: true

Input: nums = [1, 2, 3, 4]

Output: false

Time နှင့် Space complexity နှစ်ခုလုံး $O(n)$ ဖြစ်ရမည်။

ဒီ ပုစ္ဆာက array ကို စလေ့လာသည့် သူတွေ အတွက် အကောင်းဆုံး လေ့ကျင့်လို့ရတာပဲ။ သတိထားရမည့် အချက်က O(n) ဖြစ်နေတာပဲ။

ပုံမှန် ဆိုလျှင် အခန်း တစ်ခု ကို ယူ ၊ အစ ကနေ အကုန်တိုက်သည့် ပုံစံ ဖြင့်သွားရသည်။ ဒါဆိုရင် $O(n^2)$ ဖြစ်သွားပါမယ်။ $O(n)$ ရအောင် HashSet ကို သုံးနိုင်ပါတယ်။

public boolean hasDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) seen.add(n);
    return seen.size() < nums.length;
}

Array တွေ အကုန်လုံးကို Set ထဲထည့်လိုက်တယ်။ ပြီးရင် Set size နဲ့ array size ယှဥ်တယ်။ မတူရင် duplicate ရှိတယ် ဆိုတာ သိနိုင်ပါတယ်။

Valid Anagram

An anagram ဆိုတာကတော့ string ထဲမှာ ပါသည့် characters တွေကနေ နောက်ထပ် string ထဲမှာလည်း ပါနေသည့် သဘောပါ။ ဥပမာ

Input: s = "racecar", t = "carrace"

Output: true

Input: s = "jar", t = "jam"

Output: false

$O(n+m)$ Time Complexity ဖြစ်ရမည်။

ဒီ ပုစ္ဆာ ဆိုရင် အဖြေ နှစ်မျိုး ရှိနိုင်တယ်။ Space Complexity က ဘယ်လောက် လိုချင်သလဲ။ $O(1)$ သာဖြစ်ခဲ့ရင် character က fix length (a-z) ဖြစ်မယ်။ character က latin တွေ ပါ ပါလာနိုင်လား။ ပါလာနိုင်ရင်တော့ dynamic ဖြစ်ပြီး $O(1)$ နဲ့ မရနိုင်တော့ဘူး။ Space complexity က $O(n)$ မှ အဆင်ပြေမယ်။

အရင်ဆုံး a-z ပဲ ရှိမယ် သတ်မှတ်ပြီး ရေးကြည့်ရအောင်။

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] count = new int[26]; //a မှ z အထိ

    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;//a-a = 0 , b-a = 1
        count[t.charAt(i) - 'a']--;
    }
    //count ထဲဝင် a-z count ဖြစ်သွားပါပြီ။
    for (int c : count) {
        if (c != 0) return false;
    }

    return true;
}

ဒီ Code Idea ကတော့ ရိုးရှင်းပါတယ်။ a-z အခန်း ယူထားတယ်။ s ထဲမှာ a ပါရင် အခန်း ကို +1 လုပ်လိုက်တယ်။ t ထဲမှာ a ပါရင် -1 လုပ်လိုက်တယ်။ ဒါဆိုရင် အခန်းက မူရင်း အတိုင်း 0 ပြန်ဖြစ်သွားမှာပေါ့။ တကယ်လို့ s မှာ a ပါပြီး t မှာ a မပါရင် အခန်းထဲမှာ 0 ပြန်မဖြစ်ပါဘူး။ ဒါဆိုရင် anagram မဖြစ်တာ သေချာသွားပြီ။

s.charAt(i) - 'a' ဆိုသည့် သဘောကတော့ a - a = 0 ဖြစ်သည့် သဘောပါ။ b - a ဆိုရင် 1 ပါ။ တနည်းပြောရင် အခန်း 0 ကနေ 25 ထိ တွက်သည့် သဘောပါပဲ။

အကယ်၍ character က a-z အပြင် တခြား latin character တွေ ပါပါလာခဲ့ရင် array size fix က အဆင်မပြေတော့ပါဘူး။ အဲဒီ အတွက် HashMap ကို ပြောင်းသုံးပါမယ်။

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    Map<Character, Integer> count = new HashMap<>();

    for (int i = 0; i < s.length(); i++) {
        count.merge(s.charAt(i), 1, Integer::sum);
        count.merge(t.charAt(i), -1, Integer::sum);
    }

    for (int val : count.values()) {
        if (val != 0) return false;
    }

    return true;
}

Dictionary key ကို သုံးပြုပြီး +1 , -1 လုပ်သွားတာပါပဲ။ loop ပြီးသွားသည့် အခါမှာ အကုန် 0 တွေ ဖြစ်နေရမှာပါ။ count.merge ဆိုတာကတော့ လက်ရှိ ရှိနေသည့် value ကို ပေါင်းပေးတာပါ။

merge မသုံးပဲ put သုံးခဲ့ရင်တော့ အခုလို ရေးရပါမယ်။

count.put(s.charAt(i), count.getOrDefault(s.charAt(i), 0) + 1);

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because numbers[0] + numbers[1] == 9, we return [0, 1].

Example 2:

Input: numbers = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: numbers = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than $O(n^2)$ time complexity?

ဒီ ပုစ္ဆာ က ကြည့်လိုက်တာနဲ့ ရိုးရှင်းပါတယ်။ ပုံမှန် သမာရိုးကျ နည်းလမ်း စဥ်းစားရင် loop နှစ်ခါ ပတ်လိုက်ရင် ရပါပြီ။ ဒါပေမယ့် time complexity က $O(n^2)$ ဖြစ်နေပါတယ်။ ဒါကြောင့် ကျွန်တော်တို့တွေ ပုံမှန် သုံးနေကျ Hash Table နဲ့ ပဲ စဥ်းစားပါမယ်။

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (seen.containsKey(complement)) {
                return new int[] { seen.get(complement), i };
            }

            seen.put(nums[i], i);
        }

        return new int[] {}; // unreachable given valid input
    }
}

Group Anagram

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

ဒီပုစ္ဆာမှာ Anagram ဖြစ်တယ်ဆိုရင် သိနိုင်မယ့် နည်းက သက်ဆိုင်ရာ String တွေကို Sort လုပ်လိုက်တာပါပဲ။ ဥပမာ eat ရော tea ရော ate ရော အားလုံးကို sort လုပ်လိုက်ရင် aet ဆိုပြီး ရလာပါမယ်။ ဒီတော့ aet ကို Map ရဲ့ Key အနေနဲ့ သုံးပြီး တူရာတွေကို Group ဖွဲ့လို့ ရပါတယ်။

ဒါပေမယ့် Sort လုပ်မယ်ဆိုရင် Time Complexity က $O(m \cdot n \log n)$ ( $m$ က string အရေအတွက်၊ $n$ က string တစ်ခုရဲ့ ပျမ်းမျှ အရှည်) ဖြစ်သွားပါမယ်။
ပိုမြန်တဲ့ နည်းလမ်းကတော့ Array Counting နည်းနဲ့ Group ဖွဲတာပါ။ a-z အထိ character ၂၆ လုံးအတွက် Array ဆောက်ပြီး ရေတွက်လိုက်မယ်ဆိုရင် Time Complexity ကို $O(m \cdot n)$ အထိ လျှော့ချလို့ ရပါတယ်။

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            // character 26 လုံးအတွက် count မှတ်ရန် array
            char[] hash = new char[26];
            for (char c : s.toCharArray()) {
                hash[c - 'a']++;
            }
            
            // ယင်း Array ကို String အနေနဲ့ ပြောင်းပြီး Key အဖြစ်သုံးခြင်း
            String key = new String(hash);
            
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

Top K Frequent Element

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Constraints:

Your algorithm's time complexity must be better than $O(n \log n)$ , where n is the array's size.

ဒီပုစ္ဆာမှာ element တွေ ဘယ်နှစ်ကြိမ် ပါလဲဆိုတာကို အရင်ဆုံး HashMap နဲ့ ရေတွက်လိုက်ပါမယ်။ အဲဒီနောက် အကြိမ်ရေ အများဆုံး k ခုကို ရှာရမှာပါ။ Constraints အရ $O(n \log n)$ ထက်မြန်ရမယ် ဆိုတော့ ပုံမှန် Sort လုပ်တဲ့နည်းကို သုံးလို့ မရပါဘူး။

ဒီအခါမှာ Bucket Sort သဘောတရားကို အသုံးပြုနိုင်ပါတယ်။ Array တစ်ခုတည်ဆောက်ပြီး အဲဒီ Array ရဲ့ Index ကို "ပါဝင်တဲ့အကြိမ်ရေ (Frequency)" အနေနဲ့ သတ်မှတ်ပါမယ်။ Array ရဲ့ Values ကတော့ အဲဒီ အကြိမ်ရေပြည့်တဲ့ နံပါတ်တွေရဲ့ List ဖြစ်ပါမယ်။ သုံးမယ့် Time Complexity ကတော့ $O(n)$ ပါ။ Space Complexity လည်း $O(n)$ ပါပဲ။

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        // တစ်ခုချင်းစီ ဘယ်နှစ်ကြိမ်ပါလဲ ရေတွက်ခြင်း
        for (int num : nums) {
            count.merge(num, 1, Integer::sum);
        }

        // ကြိမ်ရေ (Frequency) ကို Index အဖြစ်သုံးရန် Array တည်ဆောက်ခြင်း
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // Map ထဲက Data တွေကို ကြိမ်ရေနဲ့ ကိုက်ညီတဲ့ အခန်းထဲ သွားထည့်ခြင်း
        for (int key : count.keySet()) {
            buckets[count.get(key)].add(key);
        }

        // နောက်ဆုံးကနေ ပြန်ဖတ်ပြီး အကြိမ်ရေများတဲ့ k ခုကို ပြန်ပေးခြင်း
        int[] result = new int[k];
        int index = 0;
        for (int i = buckets.length - 1; i >= 0 && index < k; i--) {
            for (int num : buckets[i]) {
                result[index++] = num;
                if (index == k) return result;
            }
        }
        return result;
    }
}

Valid Sudoku

Determine if a 9x9 Sudoku board is valid.

Rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Sudoku board တစ်ခု မှန်ကန်မှုရှိမရှိ စစ်ဆေးဖို့အတွက် အခြေအနေ ၃ ခုကို စစ်ရပါမယ်။ လိုင်း (Row) ထဲမှာ ဂဏန်းတွေ ထပ်နေလား၊ တိုင် (Column) ထဲမှာ ထပ်နေလား၊ 3x3 အကွက်လေး (Sub-box) ထဲမှာရော ထပ်နေလား ဆိုတာပါ။

ဒီအတွက် HashSet ကို သုံးပြီး လွယ်လွယ်ကူကူ ဖြေရှင်းနိုင်ပါတယ်။ HashSet ထဲကစာသားကို သေချာဖွဲ့စည်းပေးလိုက်ပါမယ်။ ဥပမာ "5 found in row 0", "5 found in column 2", သို့မဟုတ် "5 found in sub-box 0-0" လို့ String လေးတွေ တည်ဆောက်ပြီး Set ထဲ ထည့်လိုက်ပါမယ်။ HashSet.add() က ပါပြီးသား (duplicate) ဆိုရင် false Return ပြန်ပေးတဲ့အတွက် အထပ်ပါနေတာကို အလွယ်တကူ သိနိုင်ပါတယ်။

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char current = board[i][j];
                if (current != '.') {
                    // String တွေ တည်ဆောက်ပြီး Set ထဲထည့်ရန် ကြိုးစားခြင်း
                    if (!seen.add(current + " found in row " + i) ||
                        !seen.add(current + " found in col " + j) ||
                        !seen.add(current + " found in sub-box " + (i / 3) + "-" + (j / 3))) {
                        return false; 
                        // သတ်မှတ်ထားတဲ့ လိုင်း, တိုင်, သို့မဟုတ် အကွက်လေး ထဲမှာ အဆိုပါဂဏန်း ပါနေခဲ့ပြီ ဆိုတာကို ပြသသည်
                    }
                }
            }
        }
        return true;
    }
}

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in $O(n)$ time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

ဆက်တိုက်ဖြစ်နေတဲ့ ဂဏန်းစဉ် (Sequence) အရှည်ဆုံးကို ရှာရမှာပါ။ ဥပမာ 1, 2, 3, 4 ပါရင် အရှည် ၄ ဆိုပြီး အဖြေထုတ်ပေးရမှာပါ။ Constraints မှာ $O(n)$ နဲ့ တွက်ရမယ် ဆိုတာကြောင့် Array ကို Sort လုပ်ရင် $O(n \log n)$ ဖြစ်သွားမှာမိုလို့ Sort လုပ်ခွင့် မရှိပါဘူး။

$O(n)$ နဲ့ ရဖို့အတွက် array ထဲက element တွေ အကုန်လုံးကို HashSet ထဲ အရင်ထည့်လိုက်ပါမယ်။
ပြီးရင် number တစ်ခုချင်းစီဟာ sequence တစ်ခုရဲ့ အစ (Start of Sequence) ဟုတ်မဟုတ် စစ်ဆေးပါမယ်။
ဘယ်လိုစစ်မလဲ ဆိုတော့ သက်ဆိုင်ရာနံပါတ် num ရဲ့ အရှေ့နံပါတ် num - 1 က HashSet ထဲမှာ မရှိဘူး ဆိုရင် ဒါဟာ အစပဲ ဖြစ်ပါတယ်။ ကဲ အစကို ရပြီ ဆိုတာနဲ့ အဲဒီနံပါတ်ကနေ စပြီး num + 1, num + 2 တွေ Set ထဲ ရှိမရှိ ဆက်တိုက် ရှာသွားလိုက်ယုံပါပဲ။

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        // ထပ်နေတာတွေ ဖယ်ပြီး အလွယ်တကူ စစ်နိုင်အောင် HashSet သုံးခြင်း
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        for (int num : set) {
            // Sequence ရဲ့ အစ ဟုတ်မဟုတ် စစ်ဆေးခြင်း
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // နောက်နံပါတ်တွေ ဆက်တိုက် ရှိမရှိ စစ်ဆေးခြင်း
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}