Array Summary

• Use two pointer as array's benefice  
• Use hash table may reduce the time complexity from O(n^2) to O(n log n)

 
832. Flipping an Image

class Solution(object):
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        if not A:
            return []

        for i in range(len(A)):
            A[i] = A[i][::-1]
            for j in range(len(A)):
                A[i][j] = 1 ^ A[i][j]

        return A

280. Wiggle Sort

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        for i in range(1, len(nums)):
            if i % 2 == 1 and nums[i] < nums[i - 1] or i % 2 == 0 and nums[i] > nums[i - 1]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]



66. Plus One

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        if not digits:
            return [1]
       
        carry = 0
        for i in reversed(range(len(digits))):
            if i == len(digits) - 1:
                digits[i] += 1
            cur = digits[i] + carry
            carry = cur / 10
            digits[i] = cur % 10
       
        if carry:
            digits.insert(0, carry)
       
        return digits


75. Sort Colors

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # process 0
        red = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                nums[red], nums[i] = nums[i], nums[red]
                red += 1
       
        # process 2
        blue = len(nums) - 1
        for i in reversed(range(len(nums))):
            if nums[i] == 2:
                nums[blue], nums[i] = nums[i], nums[blue]
                blue -= 1

55. Jump Game

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        so_far = 0
        for i in range(len(nums)):
            if i <= so_far:
                so_far = max(so_far, nums[i] + i)
       
        return so_far >= len(nums) - 1
                


26. Remove Duplicates from Sorted Array

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return len(nums)
       
        cur = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[cur] = nums[i]
                cur += 1
       
        return cur


121. Best Time to Buy and Sell Stock

    # Greedy
    def maxProfit_02(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        buy = float('inf')
        res = 0

        for i in range(len(prices)):
            buy = min(buy, prices[i])
            res = max(res, prices[i] - buy)

        return res              

54. Spiral Matrix

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix: return []
        m, n = len(matrix), len(matrix[0])
        dic = ((0,1),(1,0),(0,-1),(-1,0))
        i,j,k, res = 0, 0, 0, []

        res.append( matrix[i][j] )
        matrix[i][j] = 'P'
        for x in range(m*n):
            while 0 <= i + dic[k][0] < m and 0 <= j + dic[k][1] < n \
            and matrix[i + dic[k][0]][j + dic[k][1]] != 'P':
                i += dic[k][0]
                j += dic[k][1]
                res.append( matrix[i][j] )
                matrix[i][j] = 'P'
            k = (k + 1) % 4

        return res48. Rotate Image

     def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        for i in range(len(matrix)):
            for j in range(i + 1, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
            matrix[i].reverse()