Split the Array

EASY

Description

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

Approaches

Checkout 4 different approaches to solve Split the Array. Click on different approaches to view the approach and algorithm in detail.

Sorting and Checking for Duplicates

A more efficient approach is based on the key insight that a valid split is impossible if and only if some number appears more than twice. By sorting the array, we can easily check this condition. If any number appears three or more times, these identical elements will be grouped together after sorting.

Algorithm

Sort the input array nums in non-decreasing order.
Iterate through the array from index i = 0 to n-3, where n is the length of the array.
In each iteration, check if nums[i] is equal to nums[i+2].
If they are equal, it means the number nums[i] appears at least three times, so return false.
If the loop completes without finding any such triplet, return true.

The core idea is that if a number x appears 3 or more times, we cannot place all instances of x into nums1 and nums2 without one of them having duplicate x's. For example, with three x's, by the pigeonhole principle, at least one array must get two x's, violating the distinctness rule. Conversely, if every number appears at most twice, a valid split is always possible.

The algorithm first sorts the input array nums. This brings all identical elements next to each other.

Then, it iterates through the sorted array and checks for any element that is repeated three or more times. A simple way to do this is to check if nums[i] == nums[i+2] for any i. If this condition is met, it implies nums[i], nums[i+1], and nums[i+2] are all the same, so we can immediately return false.

If the entire array is scanned without finding such a triplet, it means no number appears more than twice, and we can return true.

import java.util.Arrays;

class Solution {
    public boolean isPossibleToSplit(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return true;
        }
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] == nums[i+2]) {
                // This means nums[i], nums[i+1], and nums[i+2] are all equal
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n log n), dominated by the sorting step. The subsequent scan is `O(n)`.Space Complexity: O(log n) or O(n), depending on the space used by the sorting algorithm implementation (e.g., quicksort's recursion stack or mergesort's auxiliary array).

Pros and Cons

Pros:

Much more efficient than backtracking.
Simple to implement.

Cons:

The O(n log n) time complexity from sorting is not the most optimal.

Code Solutions

Checking out 4 solutions in different languages for Split the Array. Click on different languages to view the code.

public class Solution {
    public bool IsPossibleToSplit(int[] nums) {
        int[] cnt = new int[101];
        foreach(int x in nums) {
            if (++cnt[x] >= 3) {
                return false;
            }
        }
        return true;
    }
}

Video Solution

Watch the video walkthrough for Split the Array

Patterns:

Counting

Data Structures:

ArrayHash Table

Companies:

Visa |