Array Summary

Array
Summary
Publish Date:   2022-06-12

Summary of Array. Methods: Binary Search, Double Pointers, Sliding Window, Simulation.

Binary Search: time complexity: O(n) => O(logn).

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l < r:
            m = l + (r-l) // 2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m 
            else:
                l = m + 1
        return -1

Similar: LeetCode 34 Find First and Last Position of Element in Sorted Array, LeetCode 35 Search Insert Position, LeetCode 69 Sqrt(x), LeetCode 367 Valid Perfect Square.

LeetCode 27 Remove Element

Double Pointers: time complexity: O(n^2) => O(n).

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        l = 0
        r = n-1
        while l <= r:
            if nums[l] == val: # is val
                nums[l], nums[r]= nums[r], nums[l] # switch
                r-=1
            else: # not val
                l+=1
        return l

Similar: LeetCode 26 Remove Duplicates from Sorted Array, LeetCode 283 Move zeros, LeetCode 844 Backspace String Compare, LeetCode 977 Squares of a Sorted Array.

LeetCode 977 Squares of a Sorted Array

Double Pointers: time complexity: O(n^2) => O(n).

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i = 0
        j = len(nums)-1
        res = []
        while i<=j:
            l2 = nums[i]**2
            r2 = nums[j]**2
            if l2 < r2:
                res.append(r2)
                j -= 1
            else:
                res.append(l2)
                i += 1
        return res[::-1]

LeetCode 209 Minimum Size Subarray Sum

Sliding Window: time complexity: O(n^2) => O(n).

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        SUM = 0
        min_res = float('inf')
        slow = 0
        for i in range(len(nums)): # change pointer i
            SUM += nums[i]
            while SUM >= target: # change pointer slow
                min_res = min(min_res, i-slow+1)
                SUM -= nums[slow]
                slow += 1
        return min_res if min_res != float('inf') else 0

Similar: LeetCode 904 Fruit Into Baskets, LeetCode 76 Minimum Window Substring.

LeetCode 59 Spiral Matrix II

Simulation. Time complexity O(nm).

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0]*n for _ in range(n)]
        candidate = [i for i in range(1, n**2+1)]
        
        row1, row2, col1, col2 = 0, n-1, 0, n-1
        while row1 <= row2 and col1 <= col2:
            for col in range(col1, col2+1):
                val = candidate.pop(0)
                res[row1][col] = val
                
            for row in range(row1+1, row2+1):
                val = candidate.pop(0)
                res[row][col2] = val
                
            if row1 < row2 and col1 < col2:
                for col in range(col2-1, col1, -1):
                    val = candidate.pop(0)
                    res[row2][col] = val
                    
                for row in range(row2, row1, -1):
                    val = candidate.pop(0)
                    res[row][col1] = val
                    
            row1 += 1
            row2 -= 1
            col1 += 1
            col2 -= 1
        return res

Similar: LeetCode 54 Spiral Matrix, JZ Offer 29.

Array
  TOC