238. Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
### Reverse Product List: Time - O(n) / Space - O(n)
import numpy as np
length = len(nums)
tableL = np.ones((length+1, ), dtype="int")
tableR = np.ones((length+1, ), dtype="int")for k in range(length):
tableL[k+1] = tableL[k] * nums[k]
tableR[length-k-2] = tableR[length-k-1] * nums[length-k-1]
return list(tableL * tableR)[:-1]
240. Search a 2D Matrix II
Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
### Brute Force: Time - O(n**2) / Space - O(1)
i = 0
while i < len(matrix):
j = 0
while j < len(matrix[0]):
if matrix[i][j] == target: return True
elif matrix[i][j] > target: break
elif matrix[i][j] < target: j += 1
i += 1
return False### Top-Right: Time - O(n**2) / Space - O(1)
i, j = 0, len(matrix[0])-1
while i < len(matrix) and j >= 0:
if target > matrix[i][j]: i += 1
elif target < matrix[i][j]: j -= 1
else: return True
return False
242. Valid Anagram
Given two strings s and t, write a function to determine if t is an anagram of s.
### Hash Table: Time - O(m+n) / Space - O(1)
timeS = [0] * 26
for char in s:
timeS[ord(char) - ord("a")] += 1timeT = [0] * 26
for char in t:
timeT[ord(char) - ord("a")] += 1
return timeS == timeT### Sorting: Time - O(nlogn) / Space - O(1)
return sorted(s) == sorted(t)
268. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
### Sorting: Time - O(nlogn) / Space - O(1)
nums.sort()
if nums[0] != 0: return 0
if nums[-1] != len(nums): return len(nums)for k in range(len(nums)-1):
if nums[k]+1 != nums[k+1]: return nums[k]+1### HastSet: Time - O(n) / Space - O(n)
nums = set(nums)
for num in range(len(nums)+1):
if num not in nums: return num### Bit Operation: Time - O(n) / Space - O(1)
result = len(nums)
for k, num in enumerate(nums):
result = result ^ k # xor with all possible value
result = result ^ num # xor with appeared value
return result
279. Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
### Breadth First Search: Time - O(nk) / Space - O(n)
### can use set to speed up
squares = []
for k in range(1, int(pow(n, 0.5))+1):
squares.append(k**2)queue = [(n, 0)]
while queue:
num, step = queue.pop(0)
for square in squares:
if num == square: return step+1
if num < square: break
queue.append((num-square, step+1))
return 0
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
### Two Pointer: Time - O(n) / Space - O(1)
ptrOrder = 0
ptrNZero = 0
while ptrOrder < len(nums):
if ptrNZero > len(nums) - 1: nums[ptrOrder] = 0
elif nums[ptrNZero] != 0: nums[ptrOrder] = nums[ptrNZero]
elif nums[ptrNZero] == 0:
while ptrNZero < len(nums)-1:
if nums[ptrNZero] != 0: break
ptrNZero += 1
nums[ptrOrder] = nums[ptrNZero]
ptrOrder += 1
ptrNZero += 1287. Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
### Sorting: Time - O(nlogn) / Space - O(1)
nums.sort()
for k in range(len(nums)-1):
if nums[k] == nums[k+1]: return nums[k]### HashSet: Time - O(n) / Space - O(n)
numset = set()
for num in nums:
if num in numset: return num
numset.add(num)
289. Game of Life
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
### Brute Force with Set: Time - O(mn) / Space - O(mn)
liveset = set()
deadset = set()
direction = [(-1,-1), (-1,0), (-1,1), (0,1), (0,-1), (1,-1), (1,0), (1,1)]
for i in range(len(board)):
for j in range(len(board[0])):
live_neighbors = 0
for k in range(8):
tmp_pos = (i+direction[k][0], j+direction[k][1])
if not 0 <= tmp_pos[0] < len(board) : continue
if not 0 <= tmp_pos[1] < len(board[0]): continue
live_neighbors += board[tmp_pos[0]][tmp_pos[1]]if board[i][j] == 1 and live_neighbors < 2: deadset.add((i,j))
if board[i][j] == 1 and live_neighbors > 3: deadset.add((i,j))
if board[i][j] == 0 and live_neighbors == 3: liveset.add((i,j))for i, j in liveset: board[i][j] = 1
for i, j in deadset: board[i][j] = 0
300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
### Dynamic Programming: Time - O(n**2) / Space - O(n)
import numpy as np
length = len(nums)
table = np.ones((length, ), dtype="int")
for curr in range(length):
for prev in range(curr):
if nums[curr] > nums[prev]: table[curr] = max(table[curr], table[prev]+1)
return np.max(table)322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
### Breadth First Search: Time - O(nk) / Space - O(k)
if amount == 0: return 0count, queue = 0, {amount}
while queue:
temp = set()
count += 1
for amount in queue:
for coin in coins:
if amount == coin: return count
elif amount < coin: continue
elif amount > coin:
temp.add(amount-coin)
queue = temp
return -1### Dynamic Programming: Time - O(n) / Space - O(n)
table = [0] + [10004] * amount
for k in range(1, amount+1):
for coin in coins:
if k - coin < 0: continue
table[k] = min(table[k], table[k - coin] + 1)
if table[amount] == 10004: return -1
if table[amount] != 10004: return table[amount]
324. Wiggle Sort II
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
You may assume the input array always has a valid answer.
### Sorting: Time - O(n) / Space - O(1)
nums.sort()
length = len(nums)
nums[0::2], nums[1::2] = nums[:(length+1)//2][::-1], nums[(length+1)//2:][::-1]
return