Teaching Kids Programming – Split the Numbers into Two Distinct Arrays

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer array nums of even length. You have to split the array into two parts nums1 and nums2 such that:

• nums1.length == nums2.length == nums.length / 2.
• nums1 should contain distinct elements.
• nums2 should also contain distinct elements.

Return true if it is possible to split the array, and false otherwise.

Example 1:
Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: One of the possible ways to split nums is nums1 = [1,2,3] and nums2 = [1,2,4].

Example 2:
Input: nums = [1,1,1,1]
Output: false
Explanation: The only possible way to split nums is nums1 = [1,1] and nums2 = [1,1]. Both nums1 and nums2 do not contain distinct elements. Therefore, we return false.

Constraints:
1 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

Hint:
It’s impossible if the same number occurs more than twice. So just check the frequency of each value.

Split the Numbers into Two Distinct Arrays

If there are odd number of numbers, we cannot split into two equal parts. If any of the numbers appear more than 2 times, then we can’t make both arrays containing the distinct numbers.

Therefore, we can count the frequencies of each number and check if all counters appear less than or equal to 2.

1
2
3
4
5
6

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        if len(nums) & 1:
            return False
        c = Counter(nums)
        return max(c.values()) <= 2

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        if len(nums) & 1:
            return False
        c = Counter(nums)
        return max(c.values()) <= 2

The time/space complexity is O(N) where N is the number of the elements in the array, i.e. if the N numbers are all distinct, then the hash map will contain N elements.

–EOF (The Ultimate Computing & Technology Blog) —