LeetCode Problems: Array
Array in Leetcode
Summary
- As I have been picking up leetcode again since last year, I figured it would be nice if I could record and share my study notes on a blog (that's the main reason this blog exists :)). In this blog, I record questions that examine Array.
- I would like to give credit to Programmer Carl LeetCode Master! Part of the notes and solutions were inspired by the guidebook. If you would like to master leetcode, you should definitely check that out (p.s. you should be able to read Chinese, at least for now lol)
- Array is a very basic data structure. In the interview, the questions that examine arrays are usually not difficult in terms of thinking, but mainly to examine the ability to control the code.
- In other words, the idea seems simple, but it is not easy to find the optimal implementation.
- An array is a collection of data of the same type stored in contiguous memory space.
- In C++, the underlying implementation of a vector is an array, so strictly speaking, a vector is a container but an array.
Important Techniques:
Binary Search
- The Principle of Looping Invariance. We can clearly grasp the various details of the loop only if we adhere to the definition of intervals of the loop.
- Similar Questions: 35, 34, 69, 367
- 704. Binary Search
- My solution: basic binary search
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)
mid = int((r -l) / 2 - 1)
while(l < r):
# print(l,r,mid)
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid
mid = int((r - l) / 2 - 1) + l
return -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)
mid = int((r - l) / 2)
while(l < r):
print(l,r,mid)
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid
mid = int((r - l) / 2) + l
return -1
Two Pointers / Fast & Slow Pointers
- Using a fast pointer and a slow pointer in a for loop to complete the work of two for loops.
- Brute force: O(n^2), Two Pointers: O(n)
- Similar Questions: 283, 26, 203, 844, 977
- 27. Remove Element
- My solution: two pointers (left incremental pointer, right pointer points to the leftmost index that has value other than val)
- Can also be solved using fast & slow pointers
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if len(nums) == 0: return 0
nk = 0
for num in nums:
if num == val: nk += 1
j = len(nums) - 1
while nums[j] == val and j >= 0:
j -= 1
for i in range(len(nums) - nk):
# print(nums)
if nums[i] == val:
t = nums[j]
nums[j] = val
nums[i] = t
j -= 1
while nums[j] == val and j >= 0:
j -= 1
return len(nums) - nk
- 977. Sorted Squares
- My solution (referred to programmercarl Double pointers)
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l, r = 0, len(nums) - 1
res = [0 for _ in range(len(nums))]
for i in range(len(nums)):
nl, nr = nums[l], nums[r]
if nl * nl < nr * nr:
res[len(nums) - i - 1] = nr * nr
r -= 1
else:
res[len(nums) - i - 1] = nl * nl
l += 1
# print(res)
return res
Sliding Window
- The subtlety of the sliding window is to constantly adjust the starting position of the subsequence according to the current subsequence and size. Thus, reducing the time complexity from O(n^2) (brute force) to O(n).
- 209. Minimum Size Subarray Sum
- My first solution (wrong 11/20 cases passed) (sliding broken window :(, basically two pointers but the first pointer should be updated smarter)
class Solution: #(Not working❌)
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if len(nums) == 1:
if nums[0] < target: return 0
else: return 1
i, res, curr = 0, 0, 0
m = float('inf')
while i < len(nums):
# print(l, r, curr, res, m)
curr += nums[i]
res += 1
if curr >= target:
m = min(m, res)
res, curr = 0, 0
i += 1
return 0 if m == float('inf') else m
class Solution: #(Working✅ and O(n) time)
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if len(nums) == 1:
if nums[0] < target: return 0
else: return 1
l, res, curr = 0, 0, 0
m = float('inf')
for r in range(len(nums)):
curr += nums[r]
# sliding the window :)
while curr >= target:
res = r - l + 1
m = min(m, res)
curr -= nums[l]
l += 1
return 0 if m == float('inf') else m
Simulation (循環不變量原則)
- Simulation is commonly examined in questions related to arrays. It does not involve any algorithm, just pure simulation. It examines our ability to control the code.
- 59. Spiral Matrix II (failed to solve at the first time)
- 循環不變量 (important technique, also used in binary search (左開右閉, 左閉右開, 區間的概念))
- Left open right closed interval:
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
nums = [[0] * n for _ in range(n)]
x, y = 0, 0
t, ctr = n // 2, n // 2
c = 1
for offset in range(1, t + 1):
# left to right
for i in range(y, n - offset):
nums[x][i] = c
c += 1
# top to bottom
for i in range(x, n - offset):
nums[i][n-offset] = c
c += 1
# right to left
for i in range(n - offset, y, -1):
nums[n-offset][i] = c
c += 1
# bottom to top
for i in range(n - offset, x, -1):
nums[i][y] = c
c += 1
x += 1
y += 1
if n % 2 != 0:
nums[ctr][ctr] = c
return nums
- 54. Spiral Matrix (related question to 59)
- 循環不變量 (important technique, also used in binary search (左開右閉, 左閉右開, 區間的概念))
- The only difference is that, in this question, we need to consider number of columns and rows.
- offset += 2 since we want to handle the center row/column at last.
class Solution:
def spiralOrder(self, m: List[List[int]]) -> List[int]:
nr, nc = len(m), len(m[0])
if nr == 0 or nc == 0: return []
n = nr * nc
res = [0 for _ in range(n)]
x = y = idx = 0
t, ctr = min(nr, nc) // 2, min(nr, nc) // 2
offset = 1
while t > 0:
for j in range(y, y+nc-offset):
res[idx] = m[x][j]
idx += 1
# print(res)
for i in range(x, x+nr-offset):
res[idx] = m[i][j+1]
idx += 1
# print(res)
for k in range(j+1, y, -1):
res[idx] = m[i+1][k]
idx += 1
# print(res)
for l in range(i+1, x, -1):
res[idx] = m[l][y]
idx += 1
# print(res)
i = j = 0
x += 1
y += 1
offset += 2
t -= 1
if min(nr, nc) % 2 != 0:
if nc > nr:
# fill a row in the center
for i in range(ctr, ctr + nc - nr + 1):
res[idx] = m[ctr][i]
idx += 1
else:
# fill a column in the center
for i in range(ctr, ctr + nr - nc + 1):
res[idx] = m[i][ctr]
idx += 1
return res
Others
- 217. Contains Duplicate
- My solution: sort the array first and look at the neighbour
- Optimal solution: Using set data structure will be optimal (See Solution 2)
class Solution1:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i+1]:
return True
return False
class Solution2:
def containsDuplicate(self, nums: List[int]) -> bool:
s = set()
c = 0
for num in nums:
s.add(num)
c += 1
if len(s) != c:
return True
return False
- 53. Maximum Subarray
- My solution: maintain a dp array to keep track of the largest sum so far (Kadane's Algorithm) and return max(dp) at the end
- Optimal solution: instead of calling max(dp) until the end, create a global maximum variable and update it when looping the array. (See Solution 2)
class Solution1:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i-1] + nums[I])
return max(dp)
class Solution2:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0 for _ in range(len(nums))]
gm = dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i-1] + nums[I])
gm = max(dp[i], gm)
return gm