Divide Array Into Arrays With Max Difference - Leetcode 2966 - Python

0:00 - Read the problem
0:10 - Drawing Explanation
4:38 - Coding Explanation

leetcode 2966

#neetcode #leetcode #python

[julianelmasry]

NO WAY. HELLA EFFICIENT EASTER EGG ACTUALLY GOT DROPPED

[dong-hanguyen]

class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
# Sort the nums
nums.sort() # O(nlogn)
ans = []
low = float('-inf')
split = []

# Runs through O(n) for each index in nums
for i in range(len(nums)):
# Sets the low
if low == float('-inf'):
low = nums[i]

# Checks difference
if abs(low - nums[i]) > k:
return []
else:
split.append(nums[i])

# Adds to ans array
if len(split) == 3:
ans.append(split)
split = []
low = float('-inf')

# Checks lens
if len(split) == 0:
return ans

His solution was so simple 😢This is why I failed my FAANG interviews...

[Onyaga]

This solution is quite trivial i thought it was an easy problem and was racking my head trying to think of a better, O(n) soln. The example literally gives a big hint that the answer will be an arrangement of sorted elements

[ooouuuccchhh]

Me waking up at 7:30 in this winter morning to find the first video as neetcode video

[a_maxed_out_handle_of__chars]

thanks, i knew it had something to do with sorting but couldn't solve further

[nameless]

I didn't the constraint of size 3 and was over complicating by sorting + dp

[sprajosh]

I thought you've already made a video on this question

[worldinsight.]

From the question description, there are 2 condiditions that every array must satisfy. Majority of the solutions cater to the condition of difference of two elements in an array to be <= k. But why is the first condition of Each element of nums should be in exactly one array. skipped over.

Consider the following test case: [2, 2, 2, 2, 3, 3], k = 1. This ends up passing with an output of [[2, 2, 2], [2, 3, 3]]. How is this a valid output when the number 2 is present in both sub-arrays?

[hemanth.alluri]

Honest question: how is this a medium?

[TrickyCat]

@NeetCodeIO


That's a shallow copy, dude:

```python
a = [1]
l1 = [a]
l2 = l1[0:]
l2[0].append(42)

print(a)
print(l1)
print(l2)
```

If the copy was "deep" it would create the separate subcollections (sublists in the case above), but as the example shows, the list (which `a` points to) is being reused

[SanketBhat]

But for me this was the initial approach. But I kept thinking there must be some O(n) solution, but there isn't!!!

[KingApe]

"hella efficient" lmfao. Haven't heard that word in hella long

[youssefb.]

I Could not even understand the problem title