Split the Array

Difficulty: Easy | Acceptance: 61.20% | Paid: No Topics: Array, Hash Table, Counting

You are given an integer array nums of length n. You want to split nums into two arrays arr1 and arr2 such that:

• arr1 and arr2 are non-empty.
• arr1 and arr2 together contain all elements of nums.
• The frequency of each element in arr1 is less than or equal to 1.
• The frequency of each element in arr2 is less than or equal to 1.

Return true if it is possible to split nums according to the above conditions, or false otherwise.

• Examples
• Constraints
• Hash Map Frequency Counting
• Sorting and Linear Scan

Examples

Example 1:

Input: nums = [1,2,3,4]
Output: true
Explanation: We can split the array into [1,2] and [3,4].

Example 2:

Input: nums = [1,1,1,1]
Output: false
Explanation: We cannot split the array because we need to place all four 1s in either arr1 or arr2, but the frequency limit is 1 for each array.

Constraints

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

Hash Map Frequency Counting

Intuition The problem requires that no element appears more than once in either of the two resulting arrays. This implies that for any specific number in the original array, its total frequency cannot exceed 2 (one for arr1 and one for arr2). If any number appears 3 or more times, it is impossible to distribute them without violating the frequency constraint.

Steps

• Initialize a hash map (or dictionary) to store the frequency of each number in nums.
• Iterate through the nums array and update the frequency count for each number.
• During the iteration (or after), check if any number’s frequency exceeds 2.
• If a frequency greater than 2 is found, return false.
• If the loop completes without finding such a number, return true.

from collections import Counter
from typing import List

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        freq = Counter(nums)
        for count in freq.values():
            if count > 2:
                return False
        return True

Complexity

• Time: O(n), where n is the length of the array. We iterate through the array once, and hash map operations take O(1) on average.
• Space: O(n), to store the frequency counts in the hash map. In the worst case (all distinct elements), the map size is n.
• Notes: This is the most optimal approach for time complexity.

Sorting and Linear Scan

Intuition If we sort the array, identical numbers will be grouped together consecutively. We can then iterate through the sorted array and count the length of each consecutive group of identical numbers. If any group has a length greater than 2, the split is impossible.

Steps

• Sort the input array nums in ascending order.
• Initialize a counter variable to 1.
• Iterate through the array starting from the second element.
• If the current element is the same as the previous one, increment the counter.
• If the counter exceeds 2, return false immediately.
• If the current element is different from the previous one, reset the counter to 1.
• If the loop finishes, return true.

from typing import List

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        nums.sort()
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                count += 1
                if count > 2:
                    return False
            else:
                count = 1
        return True

Complexity

• Time: O(n log n), due to the sorting step. The linear scan takes O(n), which is dominated by the sort.
• Space: O(1) or O(n), depending on the sorting algorithm’s implementation (e.g., heapsort uses O(1), quicksort uses O(log n), Timsort uses O(n)).
• Notes: This approach is useful if memory space is extremely constrained and the input modification (sorting) is allowed, though it is slower than the hash map approach.