# LeetCode Algorithm I
## Binary Search
### 704. Binary Search
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 1:
if nums[0] == target: return 0
else: return -1
else:
left, right = 0, len(nums)-1
while left <= right:
mid = int((left + right) / 2)
if nums[mid] == target: return mid
elif nums[mid] > target: right = mid - 1
else: left = mid + 1
return -1
```
### 278. First Bad Version
```python
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
if n == 1:
return 1
else:
left, right = 1, n
bad_version = n
while left <= right:
mid = int((left + right) / 2)
if not isBadVersion(mid):
left = mid + 1
else:
right = mid - 1
return left
```
### 35. Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
**Approach**
discuss in 3 situations
1. length = 1
2. target value is the largest value
3. normal condition, use binary search
```python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if len(nums) == 1:
if nums[0] == target: return 0
else:
result = 0 if nums[0] > target else 1
return result
elif target > nums[-1]: return len(nums)
else:
left, right = 0, len(nums)-1
while left <= right:
mid = int((left + right) / 2)
if nums[mid] == target: return mid
elif nums[mid] > target: right = mid - 1
else: left = mid + 1
return left
```
## Two pointers
### 977. Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
```
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```
**Approach**
Since the array is in non-decreasing order, so the absolute values of left most and right most are bigger than other values
Using two pointers, left and right, compare the absolute value of them, squares the bigger number and put it into "result" array
```python
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
if len(nums) == 1:
return [nums[0]**2]
else:
left, right = 0, len(nums)-1
result = [0 for _ in range(len(nums))]
count = len(nums) - 1
while left <= right:
if abs(nums[left]) >= abs(nums[right]):
result[count] = nums[left]**2
left += 1
else:
result[count] = nums[right]**2
right -= 1
count -= 1
return result
```
### 189. Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
```
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
```
```python
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def swap(nums,l,r):
while l <= r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
return nums
k = k % len(nums)
swap(nums,0,len(nums)-1)
swap(nums,0,k-1)
swap(nums,k,len(nums)-1)
return nums
```
### 283. Move Zeroes
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
```
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
```
**Approach**
Using two pointers, left and right
1. The left pointer is the index where non-zero value put
2. The right pointer is used to scan through the array
```python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, 0
while right <= len(nums)-1:
if nums[right]:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
return nums
```
### 167. Two Sum II - Input Array Is Sorted
```
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
```
```python
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
diff = {}
for i in range(len(numbers)):
if numbers[i] not in diff:
diff[target-numbers[i]] = i
else:
return [min(i+1, diff[numbers[i]]+1), max(i+1, diff[numbers[i]]+1)]
```
### 344. Reverse String
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
```python
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
l, r = 0, len(s) - 1
while l <= r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return s
```
### 557. Reverse Words in a String III
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
```
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
```
**Approach**
Use stack to implement reversing
```python
class Solution:
def reverseWords(self, s: str) -> str:
stack = []
result = ""
for right in range(len(s)):
if s[right] != " ":
stack.append(s[right])
else:
while stack:
result += stack.pop()
result += " "
#since the last word still store in stack
while stack:
result += stack.pop()
return result
```
### 876. Middle of the Linked List
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
count = 0
curr = head
while curr:
count += 1
curr = curr.next
for i in range(int(count/2)):
head = head.next
return head
```
### 19. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
```
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
```
**Approach**
Let the pointer directly points to the next node to achieve the removal
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
count = 0
curr = head
while curr:
count += 1
curr = curr.next
if count == 1:
return None
else:
idx = count - n
if idx == 0:
return head.next
else:
curr = head
i = 0
while curr:
i += 1
if i == idx:
curr.next = curr.next.next
curr = curr.next
return head
```
## Sliding windows
### 3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest
substring without repeating characters.
```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```
**Approach**
Use two pointers, left and right
1. right pointer scan through the string and if the character doesn't appear before, store it
2. Otherwise, we need to move left pointer to delete the existed character
3. Notice that the question is to find "substring", not "subsequence", so the deletion must be continue until the existed character is removed
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
char = set()
left = 0
longest = 0
for right in range(len(s)):
while s[right] in char:
char.remove(s[left])
left += 1
char.add(s[right])
longest = max(longest, right - left + 1)
return longest
```
### 567. Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
```
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
```
**Approach**
Similar with finding anagram, we use two pointers to represent sliding window, if substring of s2 is anagram to s1, it means s2 contains permutation of s1
```python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s2) < len(s1):
return False
s1Count, s2Count = {}, {}
for i in range(len(s1)):
s1Count[s1[i]] = 1 + s1Count.get(s1[i],0)
s2Count[s2[i]] = 1 + s2Count.get(s2[i],0)
if s1Count == s2Count:
return True
left = 0
for right in range(len(s1),len(s2)):
s2Count[s2[right]] = 1 + s2Count.get(s2[right],0)
s2Count[s2[left]] -= 1
if s2Count[s2[left]] == 0:
s2Count.pop(s2[left])
left += 1
if s1Count == s2Count:
return True
return False
```
## Breadth-First Search / Depth-First Search
### 733. Flood Fill
```
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.
```
```python
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
if image[sr][sc] == color:
return image
def dfs(image, r, c, origincolor, newcolor):
if ((r not in range(len(image))) or (c not in range(len(image[0]))) or
(image[r][c] != origincolor)):
return
image[r][c] = newcolor
dfs(image, r+1, c, origincolor, newcolor)
dfs(image, r-1, c, origincolor, newcolor)
dfs(image, r, c+1, origincolor, newcolor)
dfs(image, r, c-1, origincolor, newcolor)
dfs(image, sr, sc, image[sr][sc], color)
return image
```
### 695. Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
**Approach**
Similar with finding the number of islands
Use BFS to find out all the islands, and store the size of them, return the max one
```python
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
Rows, Cols = len(grid), len(grid[0])
visited = set()
Area = []
def bfs(r,c):
area = 1
q = deque()
q.append((r,c))
visited.add((r,c))
while q:
row, col = q.popleft()
directions = [[1,0], [-1,0], [0,1], [0,-1]]
for hor, ver in directions:
r, c = row + hor, col + ver
if (r in range(Rows) and c in range(Cols) and
grid[r][c] == 1 and (r,c) not in visited):
q.append((r,c))
visited.add((r,c))
area += 1
Area.append(area)
for r in range(Rows):
for c in range(Cols):
if (grid[r][c] == 1 and (r,c) not in visited):
bfs(r,c)
return 0 if not Area else max(Area)
```
### 617. Merge Two Binary Trees
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
v1 = root1.val if root1 else 0
v2 = root2.val if root2 else 0
root = TreeNode(v1+v2)
root.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
root.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)
return root
```
### 116. Populating Next Right Pointers in Each Node
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
**Approach**
Use two pointers, curr and nxt
Since it's a full B.T.
1. The next pointer of left child of curr can points to the right child of curr
(curr.left.next = curr.right)
2. update the curr pointer to curr.next
3. If curr.next is Null means that level is finished scaning, and we can move curr and nxt pointer to the next level
4. Otherwise, curr.right.next = curr.next.left
```python
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
curr, nxt = root, root.left if root else None
while curr and nxt:
curr.left.next = curr.right
if curr.next:
curr.right.next = curr.next.left
curr = curr.next
if not curr:
curr = nxt
nxt = curr.left
return root
```
### 542. 01 Matrix
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
```
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
```
**Approach**
https://www.youtube.com/watch?v=wtRT9G42g4g
1. Initiate a result matrix with value -1
2. Let the position with value 0 be the starting node
3. Use the BFS, and if we meet -1, means the value is 1, so we need to increase the value in result matrix
```python
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
Rows, Cols = len(mat), len(mat[0])
res = [[-1 for _ in range(Cols)] for _ in range(Rows)]
q = deque()
for row in range(Rows):
for col in range(Cols):
if mat[row][col] == 0:
q.append((row,col))
res[row][col] = 0
while q:
row, col = q.popleft()
adjacent = [[1,0], [-1,0], [0,1], [0,-1]]
for hor, ver in adjacent:
r = row + hor
c = col + ver
if (r in range(Rows) and c in range(Cols) and res[r][c] == -1):
res[r][c] = res[row][col] + 1
q.append((r,c))
return res
```
### 994. Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
```
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
```
**Approach**
1. Find out the number of fresh oranges and put the rotten oranges into the queue
2. Each round, make the fresh oranges adjacent to rotten one rotten, and put the new rotten oranges into queue
3. Keep track of the number of fresh oranges
```python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
Rows, Cols = len(grid), len(grid[0])
time, fresh = 0, 0
q = deque()
for r in range(Rows):
for c in range(Cols):
if grid[r][c] == 1:
fresh += 1
if grid[r][c] == 2:
q.append((r,c))
adjacent = [[1,0], [-1,0], [0,1], [0,-1]]
while q and fresh > 0:
for i in range(len(q)):
r, c = q.popleft()
for hor, ver in adjacent:
row = r + hor
col = c + ver
if (row in range(Rows) and col in range(Cols) and grid[row][col] == 1):
grid[row][col] = 2
q.append((row,col))
fresh -= 1
time += 1
return time if fresh == 0 else -1
```
## Recursion / Backtracking
### 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if ((not list1) and (not list2)): return list1
if not list1: return list2
if not list2: return list1
result = curr = ListNode()
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
curr = curr.next
list1 = list1.next
else:
curr.next = list2
curr = curr.next
list2 = list2.next
if list1:
curr.next = list1
else:
curr.next = list2
return result.next
```
### 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
prev, curr = None, None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return curr
```
### 77. Combinations
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
```
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
```
**Approach**
https://www.youtube.com/watch?v=q0s6m7AiM7o&t=329s
```python
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def backtracking(start, comb):
if len(comb) == k:
res.append(comb.copy())
return
for layer in range(start, n+1):
comb.append(layer)
backtracking(layer+1, comb)
comb.pop()
backtracking(1,[])
return res
```
### 46. Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
```
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```
```python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def perm(list, i, n):
if i == n:
res.append(list.copy())
for j in range(i, n):
list[i], list[j] = list[j], list[i]
perm(list, i+1, n)
list[i], list[j] = list[j], list[i]
perm(nums, 0, len(nums))
return res
```
### 784. Letter Case Permutation
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. Return the output in any order.
```
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
```
**Approach**
i.e. "ab"
the result of it will be:
1. ab
2. Ab
3. aB
4. AB
First letter "a", we can put lowercase and uppercase into it, then we got "a" and "A"
Second letter "b", we similarly put lowercase and uppercase into "a" and "A", so now we got "ab" "aB" "Ab" "AB"
```python
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
res = [""]
for c in s:
temp = []
if c.isalpha():
for output in res:
temp.append(output + c.lower())
temp.append(output + c.upper())
else:
for output in res:
temp.append(output + c)
res = temp
return res
```
## Dynamic programming
### 70. Climbing Stairs
```python
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: return n
one_step = 1
two_step = 1
for i in range(n-1):
res = one_step + two_step
two_step = one_step
one_step = res
return res
```
### 198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
```
**Approach**
So we can kind of think it reversely
i.e. [2,7,9,3,1]
1. The value of robbing first house is 2
2. The value of robbing second house is max(first house, second house)=7
3. When it comes to the nth house(n>=3), we can either rob the nth house+max(n-2) house or max(n-1)
In this case, the value of robbing the third house is max(9+max[0:0], max[0:1])
```python
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) <= 2:
return max(nums)
money = [nums[0], nums[1]]
for house in range(2,len(nums)):
tmp = max(nums[house] + max(money[0:house-2+1]), max(money[0:house-1+1]))
money.append(tmp)
return money[-1]
```
### 120. Triangle
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
```
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
```
**Approach**
```python
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [0] * (len(triangle) + 1)
#[::-1] means operate reversly, so the row will be [4,1,8,3], [6,5,7] ...
for row in triangle[::-1]:
#enumerate(list) can get the index and value simultaneously
for idx, num in enumerate(row):
dp[idx] = num + min(dp[idx], dp[idx+1])
return dp[0]
```
## Bit Manipulation
### 231. Power of Two
```
Input: n = 16
Output: true
Explanation: 24 = 16
```
**Approach**
If n is power of two, then n AND (n-1) must be 0
```python
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 0: return False
return True if n & (n-1) == 0 else False
```
### 191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
```
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
```
**Approach**
1. Each round we use n%2 to see if the last bit is 1 or 0, and we shift right to check the next bit
2. The second solution is modify n through each round by doing n&(n-1), this operation will decrease the number of 1 once each time
```python
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += n % 2
n = n >> 1
return res
# solution2: a tricky way
# res = 0
# while n:
# res += 1
# n = n & (n-1)
# return res
```
### 190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
```
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
```
**Approach**
1. We need to extract right most bit each round, the way to get the bit is to use logical AND. i.e. 01001 & 1, notice that 1 in this case equals to 00001, so the operation is equals to 01001 & 00001 = 1
2. Each round we right shift n to let the next bit comes to the right most position
3. For result, we use logical OR to change the bit, notice that the result is reversing, so before we do the OR operation, we need to left shift 1 first in order to do the operation in the correct place
```python
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
right_most_bit = (n >> i) & 1
res = res | (right_most_bit << (31 - i))
return res
```
### 136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
```
Input: nums = [4,1,2,1,2]
Output: 4
```
**Approach**
Use the property of XOR(1 if different, 0 if same)
So the pairs of number will be 0 after XOR operation, the final result will be the single one
```python
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = nums[0]
for i in range(1,len(nums)):
res = res ^ nums[i]
return res
```
Sign in with Wallet
Connect another wallet