Array and List

In the following example, we will pay attention to 

• how we split a list
• how we use mod operator % on list size
• how we rotate the elements in the list

Q: Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

For Example

Input: nums = [1,2,3,4,5,6,7], k = 3

Output: [5,6,7,1,2,3,4]

Input: nums = [1,2,3,4,5,6,7], k = 2

Output: [6,7,1,2,3,4,5]

S1:   [1,2,3,4,5,6,7], k = 3.  => [1,2,3,4][5,6,7]  => [5,6,7][1,2,3,4] => [5,6,7,1,2,3,4]

notice k could be larger than length of the list, so we use mod to size it down k % n.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        tmp = nums[:n-k] + nums[n-k:]
        for i in range(n):
            nums[i] = tmp[i]
#O(n) O(n)

S2: create a helper array, move nums[i] to nums[(i+k)%n] 

the % will move the last k element to the first k slot

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        tmp = [0]*n #size n all 0 array
        for i in range(n):
            tmp[(i+k)%n] = nums[i]
        for i in range(n):
            nums[i] = tmp[i]
        #O(n) O(n)

S3: [1,2,3,4,5,6,7], k = 3.  => [7,6,5,4,3,2,1]  => [7,6,5][4,3,2,1] => [5,6,7][1,2,3,4] => [5,6,7,1,2,3,4]

class Solution:
    #[1,2,3,4,5,6,7], k = 3.  => [7,6,5,4,3,2,1]  => [7,6,5][4,3,2,1] => [5,6,7,1,2,3,4]
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        def rotate(l: int, r: int) -> None:
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l,r=l+1,r-1
        rotate(0, n-1)
        rotate(0, k-1)
        rotate(k, n-1)
        #O(n) O(1)



The array problems require hands on. Subtle variance i, i+1, i-1 or >, >=  makes huge difference. Try to work out the following question by yourself.

Q: Two sum of sorted array.
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, 
find two numbers such that they add up to a specific target number. 
Let these two numbers be numbers[index1] and numbers[index2] 
where 1 <= index1 < index2 < numbers length.
Return the indices of the two numbers, index1 and index2, 
added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. 
You may not use the same element twice. Your solution must use only constant extra space.
Example 
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

S1: the solution features the usage of 2 pointers.
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        if n == 2:
            return [1,2]
        l,r = 0,n-1
        while l < r:
            if numbers[l] + numbers[r] == target:
                return [l+1,r+1]
            elif numbers[l] + numbers[r] > target:
                r -= 1
            else:
                l += 1
        return None
        #O(n), O(1)


If we use Two sum solution as a function, we can solve apparently hard problems like 3sum.
Q: 3sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [0,1,1]
Output: []
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
In the following solution, pay attention to 
how does sort help
two pointers
skip duplicates
S1:
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l,r=i+1,n-1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                #print('l='+str(l)+',r='+str(r)+',total+'+str(total))
                if total == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    l+=1
                    while l < r and nums[l]==nums[l-1]:
                        l+=1
                elif total < 0:
                    l+=1
                else:
                    r-=1
        return res
        #O(nn), O(1)


There are many ways of traversal a list, the hard part is to make it clean.

Q: You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

S1:
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(intervals)):
            start = intervals[i][0]
            end = intervals[i][1]
            if start > newInterval[1]:
                res.append(newInterval)
                return res + intervals[i:]
            elif end < newInterval[0]:
                res.append(intervals[i])
            else:
                newInterval = [min(start, newInterval[0]), max(end, newInterval[1])]
        res.append(newInterval)
        return res 
        #O(n), O(1)


Q: