@mauricioguerrero8890

1 month ago

We can apply the pigeonhole principle to determine whether it's possible to split an array into two subarrays such that each subarray contains distinct elements. The pigeonhole principle states that if you have more "pigeons" than "holes," then at least one "hole" must contain more than one "pigeon."

In this context, the "pigeons" are the occurrences of each number in the array, and the "holes" are the two subarrays. If any number appears more than twice in the array, it’s impossible to split the array into two subarrays where each number appears only once in each subarray. Therefore, if any number’s frequency is greater than 2, we can immediately conclude that it’s not possible to split the array in this way, and return False. Otherwise, we return True.

Below is an implementation of this:

# Create a frequency counter for each value in frequency_counter = { }

# Iterate over the nums list and update frequencies
# in the counter

for num in nums:
# If no (key, value) pair exists,
# set the default value to 0

# and increment

frequency_counter[num] = 1 + frequency_counter.get(num, 0)

# Check if any frequency exceeds 2, return False if so


for frequency in frequency_counter.values():

if frequency > 2:
return False

return True



EDIT: You can just immediately check if the current number's frequency is greater than 2 and immediately return False if it is.


for num in nums:
# If no (key, value) pair exists, set the default value to 0
# and increment

frequency_counter[num] = 1 + frequency_counter.get(num, 0)

if frequency_counter[num] > 2:
return False

return True

4 |