# Leecode Array

###### tags: `Leetcode`

## 832. Flipping an Image

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

`C++`

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        for (auto &a: A) {
            reverse(a.begin(), a.end());
            for (auto &i: a) {
                i = !i;
            }
        }
        return A;
    }
};

`Python`

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for i in range(len(A)):
            A[i].reverse()
            A[i] = list(map(lambda x: int(not x), A[i]))
        return A

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        return [[i^1 for i in a[::-1]] for a in A]

## 1031. Maximum Sum of Two Non-Overlapping Subarrays

1. 計算 list `A` 的 prefix sum `ps`
2. 利用 `ps` 計算長度為 `L` 與 `M` 的 subarray`sl` 與 `sm`，`sl[i]` 為結尾為 `A[i]` 的 subarray sum
3. 對 `sl` 中的每種 subarray，去找他的前後所有可能的 `sm` 的 subarray

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        ps = A.copy()
        for i in range(1, n):
            ps[i] = ps[i-1] + A[i]
        
        sl, sm = A.copy(), A.copy()
        sl[L-1], sm[M-1] = ps[L-1], ps[M-1]
        for i in range(L, n):
            sl[i] = ps[i] - ps[i-L]
        for i in range(M, n):
            sm[i] = ps[i] - ps[i-M]
        
        res = 0
        for i in range(L-1, n):
            for j in range(M-1, n):
                if j <= i - L or j >= i + M:
                    res = max(sl[i] + sm[j], res)
        
        return res

## 1011. Capacity To Ship Packages Within D Days

binary search

Time Complexity: $O(nlgn)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low, high = max(weights), sum(weights)
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            cur_w, cur_d = 0, 0
            for w in weights:
                if cur_w + w <= mid:
                    cur_w += w
                else:
                    cur_w = w
                    cur_d += 1
            if cur_w > 0:
                cur_d += 1
            if cur_d <= D:
                high = mid - 1
                ans = mid
            else:
                low = mid + 1
        return ans

## 565. Array Nesting

1. 暴力法

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$

:::danger
結果：Time Limit Exceeded
:::

    class Solution:
        def arrayNesting(self, nums: List[int]) -> int:
            n = len(nums)
            max_len = 0
            for k in range(n):
                s = set()
                i = k
                while nums[i] not in s:
                    s.add(nums[i])
                    i = nums[i]
                max_len = max(max_len, len(s))
            return max_len

2. 算過的數加入一個 set，每個數只會經過一次

Time Complexity: $O(n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

    class Solution:
        def arrayNesting(self, nums: List[int]) -> int:
            n = len(nums)
            max_len = 0
            exist = set()
            for k in range(n):
                if k in exist:
                    continue
                i = k
                cur_len = 0
                while nums[i] not in exist:
                    i = nums[i]
                    cur_len += 1
                    exist.add(i)
                max_len = max(max_len, cur_len)
            return max_len

3. 同方法 2，但不使用額外儲存空間

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def arrayNesting(self, nums: List[int]) -> int:
            n = len(nums)
            max_len = 0
            for k in range(n):
                if nums[k] == -1:
                    continue
                i = k
                cur_len = 0
                while nums[i] != -1:
                    temp = nums[i]
                    nums[i] = -1
                    cur_len += 1
                    i = temp
                max_len = max(max_len, cur_len)
            return max_len

## 1052. Grumpy Bookstore Owner

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        n = len(customers)
        ans = 0
        for i in range(n):
            if grumpy[i] == 0 or i < X:
                ans += customers[i]
                
        best_ans = ans
                
        for i in range(1, n-X+1):
            if grumpy[i-1] == 1:
                ans -= customers[i-1]
            if i+X-1 < n and grumpy[i+X-1] == 1:
                ans += customers[i+X-1]
            best_ans = max(ans, best_ans)
                
        return best_ans

## 39. Combination Sum

Backtracking

Time Complexity: $O(2^n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.candidates = candidates
        self.nums = len(self.candidates)
        self.target = target
        self.result = []
        self.combinationSumHelper(0, [], 0)
        return self.result
    
    def combinationSumHelper(self, idx, cur_combination, cur_sum):
        if cur_sum == self.target:
            self.result.append(cur_combination)
        for i in range(idx, self.nums):
            candidate = self.candidates[i]
            if cur_sum + candidate <= self.target:
                self.combinationSumHelper(i, cur_combination+[candidate], cur_sum+candidate)

## 40. Combination Sum II

## 216. Combination Sum III

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.k = k
        self.n = n
        self.ans = []
        self.combinationHelper(0, 0, 0, [])
        return self.ans
    
    def combinationHelper(self, cur_k, cur_n, last_num, arr):
        if cur_k < self.k:
            for i in range(last_num+1, 10):
                if cur_n + i <= self.n:
                    self.combinationHelper(cur_k+1, cur_n+i, i, arr+[i])
        elif cur_n == self.n:
            self.ans.append(arr)

## 766. Toeplitz Matrix

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        M, N = len(matrix), len(matrix[0])
        if M == 1 or N == 1:
            return True
        for i in range(1, M):
            for j in range(1, N):
                if matrix[i][j] != matrix[i-1][j-1]:
                    return False
        return True

## 769. Max Chunks To Make Sorted

Time Complexity: $O(n^2lgn)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, 1
        num_chunks = 0
        while i < n:
            if sorted(arr[i:j]) == [x for x in range(i, j)]:
                num_chunks += 1
                i = j
            j += 1
        return num_chunks

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        cur_max = 0
        num_chunks = 0
        for i, a in enumerate(arr):
            cur_max = max(cur_max, a)
            if i == cur_max:
                num_chunks += 1
        return num_chunks

## 1035. Uncrossed Lines

Longest Common Subsequence (LCS)

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$

:::success
結果：Accepted
:::

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        a, b = len(A), len(B)
        DP = [[0 for j in range(b+1)] for i in range(a+1)]
        for i in range(1, a+1):
            for j in range(1, b+1):
                if A[i-1] == B[j-1]:
                    DP[i][j] = DP[i-1][j-1] + 1
                else:
                    DP[i][j] = max(DP[i-1][j], DP[i][j-1])
        return DP[-1][-1]

## 643. Maximum Average Subarray I

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        n = len(nums)
        s = sum(nums[:k])
        res = s
        for i in range(1, n-k+1):
            s -= nums[i-1]
            s += nums[i+k-1]
            res = max(res, s)
        return res / k

## 287. Find the Duplicate Number

1. Sorting

Time Complexity: $O(nlgn)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            n = len(nums)
            nums.sort()
            for i in range(1, n):
                if nums[i] == nums[i-1]:
                    return nums[i]

2. Set

Time Complexity: $O(n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            s = set()
            for a in nums:
                if a in s:
                    return a
                s.add(a)

3. Binary Search

用 binary search 尋找介於 $[1, n]$ 之間的值 $mid$，計算陣列中小於等於 $mid$ 的數量，若此數量大於 $mid$，代表此值介於 $[1, mid]$ 之間，反之則介於 $[mid+1, n]$ 之間。

Time Complexity: $O(nlgn)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            left, right = 1, len(nums)-1
            while left < right:
                mid = (left + right) // 2
                print(left, mid, right)
                cnt = 0
                for n in nums:
                    if n <= mid:
                        cnt += 1
                if cnt > mid:
                    right = mid
                else:
                    left = mid + 1
            return left

4. Floyd's Cycle Detection Algorithm (Tortoise and Hare Algorithm)

將題目 mapping 成 cycle detection 的問題。

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            tortoise, hare = nums[0], nums[0]
            while True:
                tortoise = nums[tortoise]
                hare = nums[nums[hare]]
                if tortoise == hare:
                    break

            p1, p2 = nums[0], tortoise
            while p1 != p2:
                p1 = nums[p1]
                p2 = nums[p2]
            return p1

## 1010. Pairs of Songs With Total Durations Divisible by 60

Time Complexity: $O(n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainder = [0] * 60
        res = 0
        for t in time:
            remainder[t % 60] += 1
        for i in range(1, 30):
            res += remainder[i] * remainder[60-i]
        res += (remainder[0] * (remainder[0] - 1)) // 2
        res += (remainder[30] * (remainder[30] - 1)) // 2
        return res

## 48. Rotate Image

reverse and transpose

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

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

## 926. Flip String to Monotone Increasing

1. prefix sum

先計算陣列的 prefix sum，接著遍歷整個陣列，對於陣列中的每個位置，計算當此位置左方全為 0 (exclusive)，此位置右方全為 1 時 (inclusive)，需要 flip 多少個 bit。也就是計算此位置左方有多少個 1，右方有多少個 0，相加就是結果，所有可能的結果取最小值即為答案。

Time Complexity: $O(n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

    class Solution:
        def minFlipsMonoIncr(self, S: str) -> int:
            n = len(S)
            ps = [0] * (n + 1)
            for i in range(n):
                ps[i+1] = ps[i] + int(S[i])

            res = 20000
            for i in range(n+1):
                res = min(res, ps[i] + (n - i) - (ps[n] - ps[i]))
            return res

2. Dynamic Programming

## 1014. Best Sightseeing Pair

1. Brute Force

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

:::danger
結果：Time Limit Exceeded
:::

    class Solution:
        def maxScoreSightseeingPair(self, A: List[int]) -> int:
            n = len(A)
            ans = 0
            for i in range(n):
                for j in range(i+1, n):
                    ans = max(ans, A[i] + A[j] + i - j)
            return ans

2. Tracking Max

Time Complexity: $O(n)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def maxScoreSightseeingPair(self, A: List[int]) -> int:
            cur_max, ans = 0, 0
            for a in A:
                ans = max(ans, cur_max + a)
                cur_max = max(cur_max, a) - 1
            return ans

## 729. My Calendar I

1. Brute Force

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

**照順序**

    class MyCalendar:
        def __init__(self):
            self.bookings = [(0, 0), (1e9, 1e9)]

        def book(self, start: int, end: int) -> bool:
            for i, books in enumerate(self.bookings[:-1]):
                if start >= books[1] and end <= self.bookings[i+1][0]:
                    self.bookings.insert(i + 1, (start, end))
                    return True
            return False

**未照順序**

:::success
結果：Accepted
:::

    class MyCalendar(object):
        def __init__(self):
            self.calendar = []

        def book(self, start, end):
            for s, e in self.calendar:
                if s < end and start < e:
                    return False
            self.calendar.append((start, end))
            return True

**兩個 interval (a1, b1) 與 (a2, b2) overlap 的部分為 (max(a1, a2), min(b1, b2))**

:::success
結果：Accepted
:::

    class MyCalendar(object):
    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        for s, e in self.calendar:
            if max(start, s) < min(end, e):
                return False
        self.calendar.append((start, end))
        return True

2. Balanced Tree

:::warning
待補
:::

## 54. Spiral Matrix

一層層模擬

Time Complexity: $O(n)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        
        row_move, col_move = len(matrix) - 1, len(matrix[0]) - 1
        x, y = 0, -1
        output = []
        
        for i in range(col_move + 1):
            y += 1
            output.append(matrix[x][y])
        
        while True:
            if row_move == 0:
                break
            for i in range(1, row_move + 1):
                x += 1
                output.append(matrix[x][y])
            
            row_move -= 1
            
            if col_move == 0:
                break
            for i in range(1, col_move + 1):
                y -= 1
                output.append(matrix[x][y])
            
            col_move -= 1
            
            if row_move == 0:
                break
            for i in range(1, row_move + 1):
                x -= 1
                output.append(matrix[x][y])
            
            row_move -= 1
            
            if col_move == 0:
                break
            for i in range(1, col_move + 1):
                y += 1
                output.append(matrix[x][y])
            
            col_move -= 1
            
        return output

## 59. Spiral Matrix II

層層疊加

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$

:::success
結果：Accepted
:::

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0 for b in range(n)] for a in range(n)]
        row_move, col_move = n - 1, n - 1
        x, y = 0, -1
        val = 0
        
        for i in range(col_move + 1):
            y += 1
            val += 1
            matrix[x][y] = val
        
        while True:
            if row_move == 0:
                break
            for i in range(1, row_move + 1):
                x += 1
                val += 1
                matrix[x][y] = val
            
            row_move -= 1
            
            if col_move == 0:
                break
            for i in range(1, col_move + 1):
                y -= 1
                val += 1
                matrix[x][y] = val
            
            col_move -= 1
                
            if row_move == 0:
                break
            for i in range(1, row_move + 1):
                x -= 1
                val += 1
                matrix[x][y] = val
            
            row_move -= 1
                
            if col_move == 0:
                break
            for i in range(1, col_move + 1):
                y += 1
                val += 1
                matrix[x][y] = val
            
            col_move -= 1
        
        return matrix

## 289. Game of Life

1. normal solution

Time Complexity: $O(mn)$
Space Complexity: $O(mn)$

:::success
結果：Accepted
:::

    class Solution:
        def gameOfLife(self, board: List[List[int]]) -> None:
            m, n = len(board), len(board[0])
            temp = [[0 for b in range(n)] for a in range(m)]
            ops = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

            for i in range(m):
                for j in range(n):
                    neighbor = 0
                    for op in ops:
                        x, y = i + op[0], j + op[1]
                        if x >= 0 and y >= 0 and x < m and y < n:
                            neighbor += board[x][y]
                    if board[i][j] == 1:
                        if neighbor == 2 or neighbor == 3:
                            temp[i][j] = 1
                    elif neighbor == 3:
                        temp[i][j] = 1

            for i in range(m):
                for j in range(n):
                    board[i][j] = temp[i][j]

2. in-place solution

- 若 `board[i][j]` 由 `1` -> `0`，將`board[i][j]`設為`2`
- 若 `board[i][j]` 由 `0` -> `1`，將`board[i][j]`設為`3`

Time Complexity: $O(mn)$
Space Complexity: $O(1)$

:::success
結果：Accepted
:::

    class Solution:
        def gameOfLife(self, board: List[List[int]]) -> None:
            m, n = len(board), len(board[0])
            ops = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

            for i in range(m):
                for j in range(n):
                    neighbor = 0
                    for op in ops:
                        x, y = i + op[0], j + op[1]
                        if x >= 0 and y >= 0 and x < m and y < n:
                            if board[x][y] == 1 or board[x][y] == 2:
                                neighbor += 1
                    if board[i][j] == 1:
                        if neighbor == 2 or neighbor == 3:
                            board[i][j] = 1
                        else:
                            board[i][j] = 2
                    elif neighbor == 3:
                        board[i][j] = 3

            for i in range(m):
                for j in range(n):
                    if board[i][j] >= 2:
                        board[i][j] -= 2

> 當需要 in-place 的解法時，嘗試看看能否用某種轉換方式 $F$ 儲存資料，只要能確保經 $F$ 轉換後的結果與原本是 one-to-one mapping，計算完成後再用 $F^{-1}$ 轉換回來。:smile:

## 718. Maximum Length of Repeated Subarray

動態規劃，`dp[i][j]` 用來表示 `A[i:]` 與 `B[j:]` 的最大重複子陣列的長度。

因為 subarray 一定要連續，因此若前一個數是不是任意一個子序列的成員，就要從 0 開始累計，也因此與 subsequence 不同的是不需考慮 `dp[i+1][j]` 與 `dp[i][j+1]` 的結果。

Time Complexity: $O(mn)$
Space Complexity: $O(mn)$

:::success
結果：Accepted
:::

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        a, b = len(A), len(B)
        dp = [[0 for j in range(b+1)] for i in range(a+1)]
        
        for i in range(a-1, -1, -1):
            for j in range(b-1, -1, -1):
                if A[i] == B[j]:
                    dp[i][j] = dp[i+1][j+1] + 1
        
        return max(max(row) for row in dp)

## 873. Length of Longest Fibonacci Subsequence

動態規劃，以 `DP[(i,j)]` 表示以 `(i, j)` 結尾的費氏數列。

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$

:::success
結果：Accepted
:::

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        DP = {}
        for i in range(n-1):
            for j in range(i+1, n):
                if (A[j] - A[i], A[i]) in DP.keys():
                    DP[(A[i], A[j])] = DP[(A[j] - A[i], A[i])] + 1
                else:
                    DP[(A[i], A[j])] = 2
        ans = max(DP.values())
        return ans if ans > 2 else 0

## 215. Kth Largest Element in an Array (蝦皮)

## 974. Subarray Sums Divisible by K

## 611. Valid Triangle Number

## 978. Longest Turbulent Subarray

## 16. 3Sum Closest

## 792. Number of Matching Subsequences

## 795. Number of Subarrays with Bounded Maximum

## 915. Partition Array into Disjoint Intervals

## 380. Insert Delete GetRandom O(1)

## 90. Subsets II

## 153. Find Minimum in Rotated Sorted Array

## 75. Sort Colors

## 870. Advantage Shuffle

## 105. Construct Binary Tree from Preorder and Inorder Traversal

## 560. Subarray Sum Equals K

## 106. Construct Binary Tree from Inorder and Postorder Traversal

## 73. Set Matrix Zeroes

## 120. Triangle

## 713. Subarray Product Less Than K

## 56. Merge Intervals

## 209. Minimum Size Subarray Sum

## 74. Search a 2D Matrix

## 954. Array of Doubled Pairs

## 34. Find First and Last Position of Element in Sorted Array

## 63. Unique Paths II

## 33. Search in Rotated Sorted Array

## 229. Majority Element II

## 918. Maximum Sum Circular Subarray

## 55. Jump Game

## 1146. Snapshot Array

## 18. 4Sum

## 31. Next Permutation

## 907. Sum of Subarray Minimums

## 15. 3Sum