LeetCode 1470. Shuffle the Array

Solution

link
The logic of this problem is quite simple:

1. treat the given array which is divided at the position n as two parts.
2. use n as the iterator(reduce the cost of For Loop to O(len(array)/2)), then add each element into the result array

I made two submissions to solve this problem, all the lines are the same except one line inside the For Loop , which made a huge difference in the time complexity.

Submissions

• faster than 39.93%:

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        result=[]
        for i in range(n):
            result+=[nums[i],nums[i+n]]
        return result

• faster than 95.78%:

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        result=[]
        for i in range(n):
            result+=[nums[i]]+[nums[i+n]]
        return result

Analysis

result+=[nums[i],nums[i+n]] has the same effect as:

result.extend([nums[i],nums[i+n]])
# O(k),k is the number of elements inside the extending list 

result+=[nums[i]]+[nums[i+n]]has the same effect as:

result.append(nums[i]) # O(1)
result.append(nums[i+1]) # O(1)

I wrote a complement post to this topic:
https://dev.to/effylh/internal-implements-of-list-extend-and-list-append-operations-in-python-4p8j

Summary

We're familiar with those methods, but we still need to pay attention about the time complexity and make the most appropriate choice.
Method Time Complexity:
append() O(1)
insert() O(n)
extend() O(k)