We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split the Array

Number: 3324

Difficulty: Easy

Paid? No

Companies: Visa

Problem Description

Given an integer array nums of even length, determine whether you can split it into two parts, nums1 and nums2, such that each part has length nums.length / 2 and each part contains distinct elements.

Key Insights

  • Each number can be used at most once per part, so any number appearing more than twice immediately makes a valid split impossible.
  • The overall distribution of numbers is tightly constrained by the fact that the total length equals the sum of singles (appear only once) and pairs (appear exactly twice). In fact, if we let x be the number of singles and y be the number of numbers that appear twice, then x + 2y equals the total number of elements.
  • Because each double contributes one distinct element to both halves, and singles can only go to one half, the frequencies force a unique split when possible.
  • The problem can be solved simply by counting the frequency of each element.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array (we simply count element frequencies).
Space Complexity: O(n) in the worst case for the frequency hash table.

Solution

The solution involves counting the frequency of each number in the input array.

  • If any element appears more than twice, it is impossible to place them in two halves without duplicity, so we return false.
  • If every element appears at most twice, a valid split exists.

This approach uses a hash table (or dictionary) to store counts, ensuring a quick frequency check across the array. The trick here is noticing that the exact counts force the uniqueness in both halves when possible.

Code Solutions

# Python solution with line-by-line comments

def splitArray(nums):
    # Create a dictionary to count the frequency of each element.
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        # If any element appears more than twice, return False immediately.
        if counts[num] > 2:
            return False
    # If the loop completes without any count > 2, the split is possible.
    return True

# Example usage:
# nums = [1,1,2,2,3,4]
# print(splitArray(nums))  # Expected output: True
← Back to All Questions