Shuffle the Array (Constant Space) - Leetcode 1470 - Python

Solving Shuffle the Array Leetcode 1470, today's daily Leetcode problem.

0:00 - Read the problem
0:30 - O(n) Space Solution
1:25 - O(1) Space Solution
7:40 - Coding Explanation

leetcode 1470

#neetcode #leetcode #python

[LEETCODESOLVER-inwz]

the actual problem is easy
but implementing it ate my brain

[santanu]

That was a really smart solution. Never would have thought in this way.

[shejutikarmakar]

Instead of using bit manipulation we can store x, y at the same place using nums[i]*1001+nums[i+n]. Because all the numbers are less than or equal to 1000.Then we will start traversing from end .Will get y part using nums[i]%1001 and x part using nums[i]/1001.

[MP-nyep]

Really smart solution. These daily problems are helping a lot. Thank you

[jammy]

This should be a medium-level problem lol. Definitely not easy (at least for me) to solve this in O(1) space complexity.

[WilcoVerhoef]

It feels a bit cheaty to use 32bit ints while 16bit would've been enough, that's basically hiding an output array in plain sight from the start.

It's even possible to do in place permutations without the assumption that half of the bits are unused; by following the cycles:

for t in 0 to 2n:
s = source(t)
while s < t: s = source(s)
swap(s, t)

def source(t): if t even then t/2 else t/2+n

[kumarc]

interviewers which expect people to solve this in o(1) space are just testing your memory / luck

[CostaKazistov]

Brilliant walkthrough of today's Leetcode challenge. As always.

Question: Why not use `reversed(range(n))` in the for loop instead of (n-1, -1, -1)?
Works the same, doesn't it?

[sionkim]

excellent idea. please keep up daily viedos!

[paras]

Another simple 3 line python code to solve it in O(1) space:
for i in range(n):
nums[ 2 * i + 1 : 2 * i + 1 ]=[nums.pop( n + i )]
return nums
Here, nums[i:i] inserts any iterable (e.g. [2]) at ith index by shifting the rest of the elements right.
However bit operations are computationally much more efficient, whereas here we have to shift elements to insert other elements.

[edenrosales]

Why do you not advertise this channel on your main? I feel like these videos would get more views if I had known that it existed other than getting them randomly recommended to me.

[abdifatahmoh]

Simple solution:


res = []
for i in range(n):
curr_first_half = nums[i]
curr_2nd_half = nums[n + i]
res.append(curr_first_half)
res.append(curr_2nd_half)

return res

[vuejs]

fantastic, at this poit it is more art then code

[harshitpant]

Did not get the part
y = nums[ i ] & (2**10 -1)
I do know that we have to move y back to the end of the list but how is that helping here?

[servantofthelord]

Is this constant space? :
def shuffle(self, nums: List[int], n: int) -> List[int]:
for i in range(n):
nums[i] = (nums[i], nums[i+n])
for i in range(n-1, -1, -1):
nums[2*i], nums[(2*i)+1] = nums[i][0], nums[i][1]
return nums

[satwiktatikonda]

i think creating a array and returning the array won't cause any space complexity because i/p and o/p space are counted right? then first solution is also o(1) correct if I am wrong

[jshaikh]

H
'm sorry if this sounds silly, but when you say 32 bit, does it mean nums[0] is 32 bit, nums [ 1] is 32 bit and so on?
also I didn't really understand the 10 bits part, like how is one array value 10 bits?
Can someone please explain. I feel like I'm either unable to apply the basic concepts here or missing some basic information