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

ကျနော်တို့ဒီနေ့ရှင်းမယ့် ပြဿနာက Divide Array Into Arrays With Max Difference ဆိုတဲ့ leetcode question ဘဲဖြစ်ပါတယ်။

You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

Each element of nums should be in exactly one array.
The difference between any two elements in one array is less than or equal to k.
Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

 

Example 1:

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2
Output: [[1,1,3],[3,4,5],[7,8,9]]
Explanation: We can divide the array into the following arrays: [1,1,3], [3,4,5] and [7,8,9].
The difference between any two elements in each array is less than or equal to 2.
Note that the order of elements is not important.
Example 2:

Input: nums = [1,3,3,2,7,3], k = 3
Output: []
Explanation: It is not possible to divide the array satisfying all the conditions.
 

Constraints:

n == nums.length
1 <= n <= 105
n is a multiple of 3.
1 <= nums[i] <= 105
1 <= k <= 105

မေးခွန်းက ကျနော်တို့ကို nums ဆိုတဲ့ integer array ရယ် k ဆိုတဲ့ integer တခုပေးထားမယ်။ နောက်ဆက်ပီးတော့ပြောထားတာက လိုအပ်ချက်သုံးခုပေးထားမယ် အဲ့အချက်တွေနှင့်ညီတယ်ဆိုရင် array element သုံးခုပါတဲ့တခုအဖြစ် group လုပ်ပီးတော့ 2D array အဖြစ်ပြန်ပေးရမယ်။

သူလိုအပ်တယ်ဆိုတဲ့အချက်သုံးချက်က…
၁. Each element of nums should be in exactly one array. – ကျနော်တို့ group လုပ်တဲ့အချိန်မှာ ဒီ nums array ထဲမှာရှိတဲ့ array element ကိုတခါဘဲသုံးရမယ်။
၂. The difference between any two elements in one array is less than or equal to k. ကျနော်တို့ခွဲလိုက်တဲ့ group ထဲက elements တွေကို diff လုပ်လိုက်ရင် k ထက် less than or equal ဖြစ်ရမယ်
၃. Return a 2D array containing all the arrays. ဒါကတော့ရှင်းပါတယ် group လုပ်ပီးသား 3 elements ပါ array တွေကို 2 D array အဖြစ် အဖြေက return ပြန်ပေးရမယ်ဆိုတာပါ။

ဥပမာလေးတွေကြည့်လိုက်ရင်ပိုရှင်းသွားမယ်…

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2 
Output: [[1,1,3],[3,4,5],[7,8,9]]

[1,1,3]
[3,4,5]
[7,8,9]

မေးခွန်းကော ဥပမာကော ကြည့်ပီးပီဆိုရင် အဖြေကိုအောက်မှာရှင်းပါ့မယ်။ ကျနော်ဖြေရှင်းတာမကြည့်ခင်ကိုယ်ပိုင် try ကြည့်ဖို့တိုက်တွန်းလိုပါတယ်။

---

အဖြေကမေးခွန်းထဲမှာပါပီးသားပါဘဲ… သူ့လိုအပ်ချက်တွေနဲ့ကိုက်ညီအောင်လုပ်ကမှာ။ သူ့လိုအပ်ချက်တွေထဲမှာ နဲနဲစားတာက လိုအပ်ချက်နံပါတ် ၂။ ကျတော်တို့ group လုပ်မယ့် elements တွေက diff လုပ်လိုက်ရင် k ထက်ငယ်ကမယ်။ အဲ့လိုဆိုကျနော်စဥ်းစားမိတာက ပေးထားတဲ့ array ကို sorting လုပ်လိုက်မယ်။

[1, 1, 3, 3, 4, 5, 7, 8, 9]

အဲ့ကောင်ကိုမှကျနော်တို့ group ခွဲမယ် သုံးခုစီခွဲမယ်။ ဒီမှာမေးခွန်းကသေချာပြောထားတယ် n is a multiple of 3 ဆိုတော့ကျနော်တို့ပူစရာမလိုဘူး။

[1, 1, 3]
[3, 4, 5]
[7, 8, 9]

ဒါဆိုရင်အဖြေရပီပေါ့။ ဒါပေမယ့်ဒါကအလုပ်ဖြစ်တဲ့ example ပေးထားတာ။ အဲ့တော့သူ့ requirement က ကျနော်တို့ group လုပ်တဲ့ array elements တွေက သူပေးထားတဲ့ k နှင့် less than or equal ဖြစ်ရမယ်။ ဒီမှာကောင်းသွားတာက ကျနော်တို့က sort လုပ်ထားတော့ ကျနော်တို့ group ထဲက နောက်ဆုံး နဲ့ ပထမဆုံးကိုနှုတ်လိုက်ရင်အမြင့်ဆုံး diff ရပီအဲ့တော့အဲ့ဒီ့ကောင်နှင့်ဘဲစစ်လိုက်လို့ရပီ။ တကယ်လို့အဲ့လိုစစ်တဲ့အချိန်မှာမညီရင် သူပြောထားတဲ့ဥပမာအတိုင်းဘဲ [] empty array ပြန်လိုက်တာပေါ့။

ဒီလောက်ဆိုရင်ကုဒ်ကြည့်လိုက်တာနှင့်အဖြေကိုနားလည်ပီထင်ပါတယ်။

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var divideArray = function(nums, k) {
    nums.sort((a, b) => a - b);

    const result = []
    let temp = []

    for(let i=0; i < nums.length; i++) {
        temp.push(nums[i]); // ဝင်လာသမျှကို temp ထဲထည့်မယ်

        if(temp.length === 3) { // temp က 3 ဖြစ်ပီဆို k နှင့် diff ကိုစစ်မယ်
            if(temp[2] - temp[0] <= k) {
                result.push([...temp])
            } else {
                return [] // စစ်တာမကိုက်ဘူးဆိုရင် [] ပြန်မယ်
            }

            temp = [] //ကိစ္စပီးရင်အလွတ်ပြန်ထားလိုက်မယ်
        }
    }

    return result
};

Time က O(n log n) ဖြစ်သွားတယ်။ sort လိုက်ရတာကိုး။ space ကတော့ O(n) ပါ။