Leetcode Array

1. Binary Search - 704

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1

        while(left <= right):
            middle = left+(right-left)/2
            if target > nums[middle]:
                left = middle+1
            elif target < nums[middle]:
                right = middle -1
            else:
                return middle
        return -1

How to avoid Overflow problem?

Change middle (left + right)/2 to left + ((right - left) / 2)

Why time limit exceed display?

Don’t put middle outside of while loop.

2. Remove Element - 27

two method can pass leetcode test

1. staight method but need more time, time complexity is O(n^2) because of two for loop.

   class Solution(object):
       def removeElement(self, nums, val):
           size = len(nums)
           i = 0
           while i<size:
           '''before want to use range()
              but it can not be change index flexible
           ''' 
               if val == nums[i]:
                   for j in range(i+1,size):
                       nums[j-1] = nums[j]
                   size-=1
                else i+=1
           return size
   

2. two points method

   use on loop can remove elements depends on two points

   class Solution(object):
       def removeElement(self, nums, val):
           slowIndex = 0
           fastIndex = 0   
           size = len(nums)
           while fastIndex <size:
               if nums[fastIndex] != val:
                   nums[slowIndex] = nums[fastIndex]
                   slowIndex += 1
               fastIndex+=1
           return slowIndex
   

3. Squares of a Sorted Array - 977

## Straight way
class Solution(object):
    def sortedSquares(self, nums):
        newNums = []
        i = 0
        size = len(nums)
        while i<size:
            newNums.append(nums[i]*nums[i])
            i+=1
        return sorted(newNums)

Basic idea for two points way, after square, max num will show up the start and end of array.

class Solution(object):
    def sortedSquares(self, nums):
        k = len(nums)-1
        result = [0]*len(nums)
        i = 0
        j = len(nums)-1
        while i<=j:
            if pow(nums[i],2) < pow(nums[j],2):
                result[k] = pow(nums[j],2)
                j-=1
            else:
                result[k] = pow(nums[i],2)
                i+=1
            k-=1
        return result
                
        

4. Minimum Size Subarray sum - 209

two method can pass leetcode test

1. staight method but need more time, time complexity is O(n^2) because of two for loop. Time limit warning

   class Solution(object):
       def minSubArrayLen(self, target, nums):
           """
           :type target: int
           :type nums: List[int]
           :rtype: int
           """
           lens = len(nums)
           # set the min one is infinite large at start point.
           min_length = float('inf')
   
           for i in range(lens):
               cum_sum = 0
               for j in range(i,lens):
                   cum_sum += nums[j]
                   if cum_sum >= target:
                       min_length = min(min_length, j-i+1)
                       break
           return min_length if min_length != float('inf') else 0
   

2. sliding window (two points)

   Array problem final destination is two points + one loop….

   class Solution(object):
       def minSubArrayLen(self, target, nums):
           """
           :type target: int
           :type nums: List[int]
           :rtype: int
           """
           left = 0
           right = 0
           min_length = float('inf')
           cum_sum = 0
   
           while right < len(nums):
               cum_sum += nums[right]
   
               while cum_sum >= target:
                   min_length = min(min_length,right-left+1)
                   cum_sum -= nums[left]
                   left+=1
               right+=1
           return min_length if min_length!=float('inf') else 0
   

5. Spiral Matrix II - 59