မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

Leetcode မေးခွန်းကိုကြည့်ရန် ဒီ Link ကိုနှိပ်ပါ။

Title နဲ့တင်ကိုရှင်းပါတယ် duplicate ပါမပါစစ်ကမှာ။ ဥပမာလေးတွေကိုတချက်ကြည့်ကြည့်ရအောင်…

Example 1:

Input: nums = [1,2,3,1]
Output: true
Example 2:

Input: nums = [1,2,3,4]
Output: false
Example 3:

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

အဲ့တော့ duplicate ဖြစ်မဖြစ်စစ်ကမှာ။ အဲ့လိုစစ်ဖို့ပထမဆုံးတွေးမိတာက Brute Force နဲ့ စစ်မယ်။code ကိုတချက်ကြည့်လိုက်ရအောင်…

function containsDuplicate(nums) {
	for (let i = 0; i < nums.length; i++) {
		for(let j = i + 1; j < nums.length; j++) {
			if(nums[i] === nums[j]) {
				return true;
			}
		}
    }

	return false
}

သူ့ပြဿနာကဘာလဲဆိုတော့ Time Complexity: O(n^2) ဖြစ်နေတာ၊ ဒါပေမယ့် Space Complexity က O(1)။

နောက်တနည်းတွေးမိတာက sort လုပ်ပီးတော့ loop ပတ်မယ် နောက်က element ကလက်ရှိနဲ့တူလားစစ်မယ်အဲ့လိုမျိုးပေါ့။ Sort လုပ်တဲ့အတွက် သူ့ time complexity က O(n log n), duplicate ဖြစ်မဖြစ်ရှာတာက O(n) အဲ့တော့ time complexity က O(n log n)။ Space complexity ကတော့ O(1)။ (တကယ်တော့ space complexity က sorting ပေါ်မှာလဲမူတည်နိုင်ပါတယ်။)

Code ကိုတချက်ကြည့်ကြည့်လိုက်ရအောင်…

function containsDuplicate(nums) {
	nums.sort((a, b) => a - b);

	for(let i = 0; i < nums.length - 1; i++) {
		if (nums[i] === nums[i + 1]) {
			return true
		}
	}

	return false
}

နောက်ထက်တနည်းကတော့ Hash Table/Hash Set သုံးတဲ့နည်း။ ဒီနည်းကကြတော့ ပထမဆုံး Set data type နဲ့ variable တခုကြေငြာထားမယ်။ ပေးထားတဲ့ array ကို loop ပတ်ပီးတော့ ခုနက Set ထားတဲ့ထဲမှာရှိလားကြည့်မယ် ရှိတယ်ဆို duplicate ဖြစ်နေလို့ မဟုတ်ဘူးဆိုရင် သူ့ကို Set ထဲထည့်မယ်။ အောက်က code ကိုကြည့်ရင်ပိုရှင်းသွားမယ်ထင်တယ်။

function containsDuplicate(nums) {
	const seen = new Set();

	for (let i = 0; i < nums.length; i++) {
		if (seen.has(nums[i])) {
			return true;
		}

		seen.add(nums[i])
	}

	return false;
}

ဒီကောင်ရဲ့ Time Complexity က O(n), Space ကလဲ O(n) ဘဲ။

ဒီပြဿနာကိုဖြေရှင်းလို့ရတဲ့တခြားနည်းတွေလဲရှိသေးတယ် ကျနော်ကတော့ဒီသုံးခုကိုဘဲအဓိကရှင်းပြသွားတာပေါ့။ အင်တာဗျူးမှာမေးလာရင်တော့ Time/Space situration ပေါ်မူတည်ပီးတော့အဆင်ပြေမယ့်နည်းနဲ့ရှင်းရမှာပေါ့။

---

English လို Neetcode ရှင်းပြထားတာကိုကြည့်ချင်တယ်ဆိုရင် အောက်ဖော်ပြပါ YouTube video ကိုကြည့်နိုင်ပါတယ်။