အခန်း ၃ - Array & Hash Table

Array ဆိုတာ Data တွေ တည်ဆောက်သည့်အထဲမှာ အခြေခံ အကျဆုံး နဲ့ အသုံးအများဆုံး Structure တစ်ခုပါ။ သူက Data တွေကို RAM မှာ တစ်ဆက်တည်း သိမ်းဆည်းထားတာ ဖြစ်ပါတယ်။ Array မှာ

Static Array
Dynamic Array

ဆိုပြီးရှိပါတယ်။

Static Array

Static Array ဆိုတာကတော့ ယူမည့် အခန်း အရေအတွက် ကို ကြေငြာပြီးရင် ပြန်ပြင်မရတော့ပါဘူး။ ယူမည့် အခန်းအရေအတွက်ကို အရင် ကြေငြာရပါတယ်။ Java မှာ ဆိုရင် int [] arr = new int[10]; လို့ ရေးပါတယ်။ ထပ်ချဲ့လို့ မရသည့် အတွက် Static Array လို့ ခေါ်ပါတယ်။

Array က ဘာလို့ မြန်တာလဲ ? ဥပမာ Array ရဲ့ အစ (base address) က 0×1000 ဖြစ်ပြီး int တစ်ခု က 4 bytes ဆီ နေရာယူတယ် ဆိုပါစို့။ arr[5] ၆ ခု မြောက်အခန်း ကို လိုချင်ရင် loop ပတ်ပြီး ရှာနေဖို့ မလိုပါဘူး။

Address = BaseAddress + (Index * DataSize)
Address = 1000 + (5 * 4) = 1020

ဒါဆိုရင် 1020 ကို တန်းသွားလိုက်တာနဲ့ data ရပါတယ်။ ဒါကြောင့် Array မှာ Read , Write က $O(1)$ ပဲ ကြာပါတယ်။

import java.util.Arrays;

public class ArrayExample {
    public static void main(String[] args) {
        // အခန်း ၆ ခန်းပါသော Array တည်ဆောက်ခြင်း (Data ၅ ခုပဲ ထည့်ထားပါမည်)
        int[] numbers = new int[6];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        // numbers[5] သည် တန်ဖိုးမထည့်ရသေးသဖြင့် 0 ဖြစ်နေပါမည်။
        
        System.out.println("Before Insertion: " + Arrays.toString(numbers));
    }
}

Dynamic Array

Static Array တွေမှာ အခန်းကို ကြိုသတ်မှတ်ရသည့် ပြဿနာ ဖြေရှင်းဖို့ Dynamic Array တွေပေါ်ပေါက်လာပါတယ်။ Java မှာ ArrayList လို့ လူသိများပါတယ်။ သူကတော့ Data တွေကို ထည့်ချင်သလောက် ထည့်လို့ရပြီး Size ကို အလိုလျောက်ညှိပေးသွားပါတွယ်။

Dynamic Array အလုပ်လုပ်ပုံကတော့

Initial Capacity : စစချင်းမှာ အခန်း အနည်းငယ် (ဥပမာ ၅ ခန်း) ပါသည့် Array တစ်ခု ကို နေရာယူလိုက်တယ်။
Checking Space: Data အသစ်တစ်ခု ထည့်လိုက်တိုင်း နေရာလောက်သေးလား စစ်တယ်။
Resizing: အကယ်၍ နေရာပြည့်သွားပြီဆိုရင်
1. အရင် Array ထက် ၂ ဆ ကြီးသည့် Array တစ်ခု ထပ်ဆောက်လိုက်တယ်။
2. အရင် Array အဟောင်းက Data တွေကို အသစ်ထဲ တစ်ခန်းဆီ Copy လုပ်တယ်။
3. ပြီးမှ အဟောင်း ကို ဖျက်ချပြီး အသစ်ကို ဆက်သုံးပါတယ်။

flowchart TD
    subgraph Step1[၁။ မူလ Array ပြည့်သွားခြင်း Size: 3]
        direction LR
        A1[10] --- B1[20] --- C1[30]
    end

    subgraph Step2[၂။ ၂ ဆ ကြီးသော Array အသစ်တည်ဆောက်ခြင်း Size: 6]
        direction LR
        A2[Empty] --- B2[Empty] --- C2[Empty] --- D2[Empty] --- E2[Empty] --- F2[Empty]
    end

    subgraph Step3[၃။ Data ဟောင်းများကို ကူးထည့်ခြင်း]
        direction LR
        A3[10] --- B3[20] --- C3[30] --- D3[Empty] --- E3[Empty] --- F3[Empty]
    end
    
    subgraph Step4[၄။ Data အသစ် ထပ်ထည့်ခြင်း]
        direction LR
        A4[10] --- B4[20] --- C4[30] --- D4([40]) --- E4[Empty] --- F4[Empty]
    end

    Step1 --> Step2 --> Step3 --> Step4

import java.util.ArrayList;

public class DynamicArrayExample {
    public static void main(String[] args) {
        // Dynamic Array တည်ဆောက်ခြင်း (Size ကြိုပြောစရာမလို)
        ArrayList<Integer> list = new ArrayList<>();
        
        // Data ထည့်ခြင်း - O(1) [Amortized]
        list.add(10);
        list.add(20);
        list.add(30);
        
        // အလယ်မှာ ထည့်ခြင်း - O(n) [နောက်ကကောင်တွေ ရွှေ့ရလို့]
        list.add(1, 15); 
        
        // Data ဖတ်ခြင်း - O(1)
        System.out.println("Element at index 1: " + list.get(1));
        
        // လက်ရှိ ဘယ်နှစ်ခု ရှိနေပြီလဲ
        System.out.println("Current size: " + list.size());
    }
}

Dynamic Array ဟာ resize ပြန်လုပ်သည့် အချိန်မှာ နှေးသွားနိုင်ပါတယ်။ ဒါကြောင့် size အတိအကျ သိလျှင် Static Array ကို အသုံးပြုသင့်ပါတယ်။

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 ကောင်းတစ်ခုမှ အောက်ပါ function တွေ ရှိပါတယ်။

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

Hash Table

Hash Table ဆိုတာ Hash Function ကို အသုံးပြု၍ Key-Value Pair တွေ သိမ်းသည့် Data Structure ပါ။ Java မှာ HashMap ဆိုသည်ကတော့ Hash Table ၏ Implementation တစ်ခုပါ။

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 များ ချိတ်ဆက် သိမ်းဆည်းခြင်း
Open Addressing — Collision ဖြစ်ပါက အနီးစပ်ဆုံး လွတ်နေသော Index ကို ရှာဖွေ သိမ်းဆည်းခြင်း

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 — လွန်ခဲ့သော Computation ရလဒ်များကို HashMap တွင် သိမ်းကာ ထပ်တွက်မနေစေရ

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

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

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

ပုံမှန် ဆိုလျှင် အခန်း တစ်ခု ကို ယူ ၊ အစ ကနေ အကုန်တိုက်သည့် ပုံစံ ဖြင့်သွားရသည်။ ဒါဆိုရင် $O(n²)$ ဖြစ်သွားပါမယ်။ $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 ထဲမှာ ပါသည့် chaters တွေကနေ နောက်ထပ် 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];

    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }

    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 တွေ ဖြစ်နေရမှာပါ။ counter.merge ဆိုတာကတော့ လက်ရှိ ရှိနေသည့် value ကို ပေါင်းခြင်လို့ပါ။

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

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

Swift code ကို ကြည့်လိုက်ရင် ပိုနားလည် လွယ်ပါလိမ့်မယ်။

func isAnagram(_ s: String, _ t: String) -> Bool {
    if s.count != t.count { return false }

    var count = [Character: Int]()

    for (cs, ct) in zip(s, t) {
        count[cs, default: 0] += 1
        count[ct, default: 0] -= 1
    }

    return count.values.allSatisfy { $0 == 0 }
}

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: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

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

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

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

ဒီ ပုစ္ဆာ က ကြည့်လိုက်တာနဲ့ ရိုးရှင်းပါတယ်။ ပုံမှန် သမာရိုးကျ နည်းလမ်း စဥ်းစားရင် loop နှစ်ခါ ပတ်လိုက်ရင် ရပါပြီ။ ဒါပေမယ့် tim complexity က $O(n²)$ ဖြစ်နေပါတယ်။ ဒါကြောင့် ကျွန်တော်တို့တွေ ပုံမှန် သုံးနေကျ 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;
    }
}

Swift နဲ့ ဆိုရင်

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var count = [Int: Int]()
        
        // တစ်ခုချင်းစီ ဘယ်နှစ်ကြိမ်ပါလဲ ရေတွက်ခြင်း
        for num in nums {
            count[num, default: 0] += 1
        }
        
        // ကြိမ်ရေ (Frequency) ကို Index အဖြစ်သုံးရန် Array တည်ဆောက်ခြင်း
        var buckets: [[Int]] = Array(repeating: [], count: nums.count + 1)
        
        // Dictionary ထဲက Data တွေကို ကြိမ်ရေနဲ့ ကိုက်ညီတဲ့ အခန်းထဲ သွားထည့်ခြင်း
        for (num, freq) in count {
            buckets[freq].append(num)
        }
        
        // နောက်ဆုံးကနေ ပြန်ဖတ်ပြီး အကြိမ်ရေများတဲ့ k ခုကို ပြန်ပေးခြင်း
        var result = [Int]()
        for i in stride(from: buckets.count - 1, through: 0, by: -1) {
            for num in buckets[i] {
                result.append(num)
                if result.count == 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;
    }
}