Split the Array

Easy
981.

Split the Array

Split the Array is an easy coding problem on arrays, hash table and counting, asked in Amazon, Google and TCS interviews.

nums has an even length. Split it into two arrays nums1 and nums2 of equal length so that each of them holds only distinct values.

Return true if such a split exists.

Example 1

Input
nums = [1,1,2,2,3,4]
Output
true
Explanation
`[1,2,3]` and `[1,2,4]`.

Example 2

Input
nums = [1,1,1,1]
Output
false
Explanation
The value 1 appears four times, so one half must repeat it.

Example 3

Input
nums = [5,5]
Output
true

Constraints

  • 1 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossibleToSplit = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Split the Array — Solution in Python, Java & C++

Split the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and hash table.

Split the Array is an easy coding problem on arrays, hash table and counting, asked in Amazon, Google and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums has an even length. Split it into two arrays nums1 and nums2 of equal length so that each of them holds only distinct values.

Return true if such a split exists.

Example 1

Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: `[1,2,3]` and `[1,2,4]`.

Example 2

Input: nums = [1,1,1,1]
Output: false
Explanation: The value 1 appears four times, so one half must repeat it.

Example 3

Input: nums = [5,5]
Output: true

Constraints

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

Hints for Split the Array

  1. Hint 1

    Each half may hold a given value at most once.

  2. Hint 2

    So across both halves a value may appear at most twice.

  3. Hint 3

    Count the occurrences and check none exceeds 2.

How to solve Split the Array

A split exists exactly when no value occurs more than twice, because the two halves can hold at most one copy each.

Approach

  1. Count how often each value appears.
  2. Return false the moment a count reaches 3.
  3. Otherwise return true.

Why it works

The condition is not just necessary but sufficient: with every count at most 2, send one copy of each value to each half and the halves come out the same size, because the array's length is even and the leftovers pair up. So no construction is needed — counting decides it.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The limit is 2 across the whole array, not 2 per half.
  • The length is guaranteed even, so the sizes never need checking.
  • Sorting works too but is slower than counting.

Reference solution

Python

from typing import List
from collections import Counter

def isPossibleToSplit(nums: List[int]) -> bool:
    return all(c <= 2 for c in Counter(nums).values())

Java

public static boolean isPossibleToSplit(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int v : nums) {
        int c = count.merge(v, 1, Integer::sum);
        if (c > 2) return false;
    }
    return true;
}

C++

bool isPossibleToSplit(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int v : nums) {
        if (++count[v] > 2) return false;
    }
    return true;
}

JavaScript

var isPossibleToSplit = function(nums) {
    var count = new Map();
    for (var i = 0; i < nums.length; i++) {
        var cur = count.get(nums[i]);
        var c = (cur === undefined ? 0 : cur) + 1;
        if (c > 2) return false;
        count.set(nums[i], c);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets