Doing LeetCode
with java and python
1. Two Sum
Time Complexity: O(n) Space Complexity: O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++){
int counterPart = target - nums[i];
if(map.containsKey(counterPart)){
return new int[]{map.get(counterPart), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = {}
for i, num in enumerate(nums):
counterPart = target - num
if counterPart in map:
return [map[counterPart], i]
map[num] = i
22. Generate Parentheses
Backtracking
Step 1: Number of valid sequences. The number of strings generated = C_n. Step 2: Cost per string. Constructing the string in recursion takes O(n) time. So the total time to output all strings = O(C_n * n). Step 3: Recursion overhead. In our case, recursion cost does not increase asymptotically beyond O(C_n * n).
Time Complexity: O(n * C_n) ≈ O(n * 4^n / n^(3/2)) space complexity: O(n)
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
private void backtrack(List<String> result, String currentString, int leftCount, int rightCount, int maxPairs){
if(currentString.length() == maxPairs * 2){
result.add(currentString);
return;
}
if(leftCount < maxPairs){
backtrack(result, currentString + "(", leftCount + 1, rightCount, maxPairs);
}
if(rightCount < leftCount){
backtrack(result, currentString + ")", leftCount, rightCount + 1, maxPairs);
}
}
}
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
self.backtrack(result, "", 0, 0, n)
return result
def backtrack(self, result: List[str], currentString: str, leftCount: int, rightCount: int, maxPairs: int):
if len(currentString) == maxPairs * 2:
result.append(currentString)
return
if leftCount < maxPairs:
self.backtrack(result, currentString + "(", leftCount + 1, rightCount, maxPairs)
if rightCount < leftCount:
self.backtrack(result, currentString + ")", leftCount, rightCount + 1, maxPairs)
Divide and Conquer
Time Complexity: O(4^n / √n) - This is the nth Catalan number Space Complexity: O(n) for recursion stack (O(4^n / √n) for the result)
class Solution {
public List<String> generateParenthesis(int n) {
if (n == 0) return Arrays.asList("");
if(n == 1) return Arrays.asList("()");
List<String> result = new ArrayList<>();
/**
Divide: for each possible split point i, we have:
i pairs inside of the outermost parentheses, e.g., (i pair)
n -1 -1 i pairs after the outermost parentheses
*/
for(int i = 0; i< n; i ++){
List<String> inside = generateParenthesis(i);
List<String> after = generateParenthesis(n - 1 - i);
for(String insideContent: inside){
for(String afterContent: after){
result.add("(" + insideContent + ")" + afterContent);
}
}
}
return result;
}
}
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]
if n == 1:
return ["()"]
result = []
for i in range(0, n):
left = self.generateParenthesis(i)
right = self.generateParenthesis(n -1 - i)
for insideContent in left:
for afterContent in right:
result.append("(" + insideContent + ")" + afterContent)
return result
27
Double points
Time complexity : O(n). Space complexity : O(1).
class Solution {
public int removeElement(int[] nums, int val) {
int answer = 0;
for (int i = 0; i < nums.length; i ++){
if (nums[i] != val){
nums[answer] = nums[i];
answer ++;
}
}
return answer;
}
}
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
answer = 0
for i in range(len(nums)):
if nums[i] != val:
nums[answer] = nums[i]
answer += 1
return answer
35. Search Insert Position
Time complexity : O(logN). Space complexity: O(1)
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
while (left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) return mid;
if(nums[mid] > target) right = mid - 1;
if(nums[mid] < target) left = mid + 1;
}
return left;
}
}
class Solution(object):
def searchInsert(self, nums, target):
left = 0
right = len(nums) - 1
while(left <= right):
mid = left + (right - left)/2
if(nums[mid] == target):
return mid
if (nums[mid] > target):
right = mid - 1
if(nums[mid] < target):
left = mid + 1
return left
46. Permutations
backtrack
Time Complexity: O(n! × n) - there are n! permutations, and each takes O(n) time to copy Space Complexity: O(n) - for the recursion stack and temporary arrays (excluding the result space)
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(result, current, used, nums);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> current, boolean[] used, int[] nums){
if(current.size() == nums.length){
result.add(new ArrayList<>(current));
return;
}
for(int i = 0; i < nums.length; i ++){
if(used[i]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(result, current, used, nums);
used[i] = false;
current.remove(current.size() - 1);
}
}
}
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
current = []
used = [False] * len(nums)
self.backtrack(result, current, used, nums)
return result
def backtrack(self, result: List[List[int]], current: List[int], used: [bool], nums: List[int]) -> None:
if len(current) == len(nums):
result.append(current[:])
return
for i in range(0, len(nums)):
if used[i]:
continue
current.append(nums[i])
used[i] = True
self.backtrack(result, current, used, nums)
current.pop()
used[i] = False
53. Maximum Subarray
Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility.
Brute Force, Time Limit Exceeded
class Solution {
public int maxSubArray(int[] nums) {
int maxSubarray = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int currentSubarray = 0;
for (int j = i; j < nums.length; j++) {
currentSubarray += nums[j];
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
}
return maxSubarray;
}
}
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
result = -math.inf
for i in range(0, len(nums)):
sum = 0
for j in range(i, len(nums)):
sum += nums[j]
result = max(result, sum)
return result
Dynamic Programming, Kadane’s Algorithm
class Solution:
int currentSubarray = nums[0];
int maxSubarray = nums[0];
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
currentSubarray = Math.max(num, currentSubarray + num);
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
return maxSubarray;
}
def maxSubArray(self, nums: List[int]) -> int:
currentSubarray = nums[0]
maxSubarray = nums[0]
for i in range(1, len(nums)):
num = nums[i]
currentSubarray = max(num, currentSubarray + num)
maxSubarray = max(maxSubarray, currentSubarray)
return maxSubarray
Divide and Conquer
74. Search a 2D Matrix
Time complexity : O(log(mn)) since it’s a standard binary search. Space complexity : O(1).
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m == 0) return false;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1;
int midIndex, element;
while(left <= right){
midIndex = left + (right - left)/2;
element = matrix[midIndex / n][midIndex % n];
if(target == element) {
return true;
} else {
if(target > element){
left = midIndex + 1;
} else {
right = midIndex -1;
}
}
}
return false;
}
}
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if(m == 0):
return False
n = len(matrix[0])
left = 0
right = m * n - 1
while(left <= right):
mid = left + (right - left) // 2
element = matrix[mid // n][mid % n]
if(target == element):
return True
elif (target > element):
left = mid + 1
else:
right = mid - 1
return False
77. Combinations
Backtracking
TIME COMPLEXITY: O(C(n,k) * k) where C(n,k) is the binomial coefficient - We generate C(n,k) combinations - Each combination takes O(k) time to copy to result SPACE COMPLEXITY: O(k) for recursion depth and current combination storage
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> currentCombination = new ArrayList<>();
backtrack(result, currentCombination, 1, n, k);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> currentCombination, int start, int n, int k){
if(currentCombination.size() == k){
result.add(new ArrayList<>(currentCombination));
return;
}
for(int i = start; i <= n; i ++){
currentCombination.add(i);
backtrack(result, currentCombination, i + 1, n, k);
currentCombination.remove(currentCombination.size() - 1);
}
}
}
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
currentCombination = []
self.backtrack(result, currentCombination, 1, n, k)
return result
def backtrack(self, result: List[List[int]], currentCombination: List[int], start: int, n: int, k: int) -> None:
if(len(currentCombination)) == k:
result.append(currentCombination[:])
return
for i in range(start, n + 1):
currentCombination.append(i)
self.backtrack(result, currentCombination, i + 1, n, k)
currentCombination.pop()
78. Subsets
Backtrack
Time Complexity: O(2^n × n) - For n elements, there are exactly 2^n subsets - The n factor, each subset must be constructed and added to the result Space Complexity: O(2^n × n) - Store 2^n subsets - Total elements across all subsets = n × 2^(n-1)
Call 1: backtrack([], [], [1,2,3], 0)
├─ Add [] to result → result = [[]]
├─ i=0: current=[1]
│ ├─ Call 2: backtrack([[]], [1], [1,2,3], 1)
│ │ ├─ Add [1] to result → result = [[], [1]]
│ │ ├─ i=1: current=[1,2]
│ │ │ ├─ Call 3: backtrack([[], [1]], [1,2], [1,2,3], 2)
│ │ │ │ ├─ Add [1,2] to result → result = [[], [1], [1,2]]
│ │ │ │ ├─ i=2: current=[1,2,3]
│ │ │ │ │ └─ Call 4: Add [1,2,3] → result = [[], [1], [1,2], [1,2,3]]
│ │ │ │ └─ Backtrack: current=[1,2]
│ │ │ └─ Backtrack: current=[1]
│ │ ├─ i=2: current=[1,3]
│ │ │ └─ Add [1,3] → result = [[], [1], [1,2], [1,2,3], [1,3]]
│ │ └─ Backtrack: current=[1]
│ └─ Backtrack: current=[]
├─ i=1: current=[2]
│ └─ Generates [2], [2,3]
└─ i=2: current=[3]
└─ Generates [3]
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start){
result.add(new ArrayList<>(current));
for(int i = start; i < nums.length; i ++){
current.add(nums[i]);
backtrack(result, current, nums, i + 1);
current.remove(current.size() - 1);
}
}
}
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
current = []
self.backtrack(result, current, nums, 0)
return result
def backtrack(self, result: List[List[int]], current: List[int], nums: List[int], start: int) -> None:
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i])
self.backtrack(result, current, nums, i + 1)
current.pop()
Divid and Conquer
Time Complexity: O(2^n * n) Space Complexity: O(2^n * n)
class Solution {
public List<List<Integer>> subsets(int[] nums) {
return dividAndConquer(nums, 0);
}
private List<List<Integer>> dividAndConquer(int[] nums, int start){
if(start >= nums.length){
List<List<Integer>> list = new ArrayList<>();
list.add(new ArrayList<>());
return list;
}
List<List<Integer>> listWithoutCurrent = dividAndConquer(nums, start + 1);
List<List<Integer>> listWithCurrent = new ArrayList<>();
for(List<Integer> subList: listWithoutCurrent){
List<Integer> newSubList = new ArrayList<>(subList);
newSubList.add(nums[start]);
listWithCurrent.add(newSubList);
}
List<List<Integer>> all = new ArrayList<>();
all.addAll(listWithoutCurrent);
all.addAll(listWithCurrent);
return all;
}
}
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
return self.dividAndConquer(nums, 0)
def dividAndConquer(self, nums: List[int], start: int) -> List[List[int]]:
if start >= len(nums):
return [[]]
listWithoutCurrent = self.dividAndConquer(nums, start + 1)
listWithCurrent = []
for subList in listWithoutCurrent:
newSubList = [nums[start]] + subList
listWithCurrent.append(newSubList)
allList = []
allList.extend(listWithoutCurrent)
allList.extend(listWithCurrent)
return allList
94. Binary Tree Inorder Traversal
Recursive Approach
// todo
Iterating method using Stack
Time complexity: O(n) Space complexity: O(n)
class Solution {
public List<Integer> inorderTraversal(TreeNode startingNode) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
TreeNode curr = startingNode;
while(curr != null || !stack.isEmpty()){
while(curr != null){
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
output.add(curr.val);
curr = curr.right;
}
return output;
}
}
class Solution:
def inorderTraversal(self, startingNode: Optional[TreeNode]) -> List[int]:
output = []
stack = []
curr = startingNode
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
output.append(curr.val)
curr = curr.right
return output
141
Double pointer way
- Time complexity : O(n).
- Space complexity : O(1). We only use two nodes (slow and fast) so the space complexity is O(1).
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
}
}
class Solution(object):
def hasCycle(self, head):
if head is None:
return False
slow = head
fast = head.next
while slow != fast:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next
return True
Hash Table
Time complexity : O(n). We visit each of the n elements in the list at most once. Adding a node to the hash table costs only O(1) time.
Space complexity: O(n). The space depends on the number of elements added to the hash table, which contains at most n elements.
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
ListNode current = head;
while(current != null){
if(nodesSeen.contains(current)) return true;
nodesSeen.add(current);
current = current.next;
}
return false;
}
}
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
nodes_seen = set()
current = head
while current is not None:
if current in nodes_seen:
return True
nodes_seen.add(current)
current = current.next
return False
144 Binary Tree Preorder Traversal
Iterations
Time complexity: we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes, i.e. the size of the tree.
Space complexity: depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is O(N).
class Solution {
public List<Integer> preorderTraversal(TreeNode startingNode) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if(startingNode == null) return output;
stack.add(startingNode);
while(!stack.isEmpty()){
TreeNode node = stack.pollLast();
output.add(node.val);
if(node.right != null) stack.add(node.right);
if(node.left != null) stack.add(node.left);
}
return output;
}
}
class Solution(object):
def preorderTraversal(self, startingNode):
if startingNode is None:
return []
stack = [startingNode]
output = []
while stack:
node = stack.pop()
if node is not None:
output.append(node.val)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return output
145 Binary Tree Postorder Traversal
Single stack iterate
Time complexity: O(n) Space complexity: O(n)
class Solution {
public List<Integer> postorderTraversal(TreeNode currentNode) {
List<Integer> output = new ArrayList<>();
if(currentNode == null) return output;
TreeNode lastProcessedNode = null;
LinkedList<TreeNode> stack = new LinkedList<>();
while(currentNode != null || !stack.isEmpty()){
if(currentNode != null){
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.peek();
if(currentNode.right == null || currentNode.right == lastProcessedNode){
output.add(currentNode.val);
stack.pop();
lastProcessedNode = currentNode;
currentNode = null;
} else {
currentNode = currentNode.right;
}
}
}
return output;
}
}
class Solution:
def postorderTraversal(self, currentNode: Optional[TreeNode]) -> List[int]:
output = []
if currentNode is None:
return output
lastProcessedNode = None
stack = []
while currentNode is not None or len(stack) > 0:
if currentNode is not None:
stack.append(currentNode)
currentNode = currentNode.left
else:
currentNode = stack[-1]
if currentNode.right is None or currentNode.right == lastProcessedNode:
output.append(currentNode.val)
stack.pop()
lastProcessedNode = currentNode
currentNode = None
else:
currentNode = currentNode.right
return output
162. Find Peak Element
Linear Scan
Time complexity : O(n). We traverse the nums array of size n once only. Space complexity : O(1). Constant extra space is used.
public class Solution {
public int findPeakElement(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return nums.length - 1;
}
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
for i in range(len(nums) - 1):
if(nums[i] > nums[i + 1]):
return i
return len(nums) - 1
Recursive Binary Search
Time complexity : O(log2(n)). We reduce the search space in half at every step. Space complexity : O(log2(n)). We reduce the search space in half at every step. Thus, the total search space will be consumed in log2(n) steps.
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
return binarySearch(nums, left, right);
}
private int binarySearch(int[] nums, int left, int right){
if (left == right) return left;
int mid = left + (right - left)/2;
if(nums[mid] > nums[mid + 1]) return binarySearch(nums, left, mid);
if(nums[mid] < nums[mid + 1]) return binarySearch(nums, mid + 1, right);
return -1;
}
}
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
return self.binarySearch(nums, left, right)
def binarySearch(self, nums: List[int], left: int, right: int) -> int:
if(left == right):
return left
mid = left + (right - left)//2
if(nums[mid] > nums[mid + 1]):
return self.binarySearch(nums, left, mid)
else:
return self.binarySearch(nums, mid + 1, right)
iterative binary search
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
}
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while(left < right):
mid = left + (right - left )//2
if(nums[mid] > nums[mid + 1]):
right = mid
else:
left = mid + 1
return left
167. Majority Element
HashMap
Time complexity : O(n) Space complexity : O(n)
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> counter = new HashMap<Integer, Integer>(nums.length);
for(int i = 0; i < nums.length; i ++){
counter.put(nums[i], counter.getOrDefault(nums[i], 0) + 1);
}
return counter.entrySet().stream()
.filter(entry -> entry.getValue() > (nums.length/2))
.findFirst()
.get().getKey();
}
}
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counter = {}
for num in nums:
counter[num] = counter.get(num, 0) + 1
for num, count in counter.items():
if count > len(nums)//2:
return num
Divide and Conquer
Time complexity : O(nlgn) Space complexity : O(lgn)
class Solution {
public int majorityElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
return majorityElementHelper(nums, left, right);
}
private int majorityElementHelper(int[] nums, int left, int right){
if(left == right) return nums[left];
int mid = left + (right - left)/2;
int leftMajority = majorityElementHelper(nums, left, mid);
int rightMajority = majorityElementHelper(nums, mid + 1, right);
if(leftMajority == rightMajority) return leftMajority;
int leftCount = fullRangeCount(nums, leftMajority, left, right);
int rightCount = fullRangeCount(nums, rightMajority, left, right);
return leftCount > rightCount ? leftMajority : rightMajority;
}
private int fullRangeCount(int[] nums, int majorityNumber, int left, int right){
int count = 0;
for(int i = left; i <= right; i ++){
if (majorityNumber == nums[i]) count ++;
}
return count;
}
}
class Solution:
def majorityElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
return self.majortityElementHelper(nums, left, right)
def majortityElementHelper(self, nums: List[int], left: int, right: int) -> int:
if left == right:
return nums[left]
mid = left + (right - left)//2
leftMajority = self.majortityElementHelper(nums, left, mid)
rightMajority = self.majortityElementHelper(nums, mid + 1, right)
if leftMajority == rightMajority:
return leftMajority
leftCount = self.fullRangeCount(nums, leftMajority, left, right)
rightCount = self.fullRangeCount(nums, rightMajority, left, right)
if leftCount > rightCount:
return leftMajority
else:
return rightMajority
def fullRangeCount(self, nums: List[int], majorityNumber: int, left: int, right: int) -> int:
count = 0
for i in range(left, right + 1):
if nums[i] == majorityNumber:
count += 1
return count
200. Number of Islands
DFS
Time Complexity: O(M × N) Space Complexity: O(M × N) (Visited array: M × N booleans)
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int numOfIslands = 0;
boolean[][] visited = new boolean[rows][cols];
for(int i = 0; i <= rows; i ++){
for(int j = 0; j <= cols; j ++){
if(grid[i][j] == '1' && !visited[i][j]){
dfs(grid, visited,i,j,rows,cols );
}
}
}
return numOfIslands;
}
private void dfs(char[][]grid, boolean[][]visited, int row, int col, int rows, int cols){
if(row < 0 || row >= rows || col < 0|| col >= cols || visited[row][col]){
return ;
}
visited[row][col] = true;
dfs(grid, visited, row + 1, col, rows, cols);
dfs(grid, visited, row - 1, col, rows, cols);
dfs(grid, visited, row, col + 1, rows, cols);
dfs(grid, visited, row, col - 1, rows, cols);
}
}
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or len(grid) == 0:
return 0
rows = len(grid)
cols = len(grid[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
numOfIsland = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1" and not visited[i][j]:
numOfIsland += 1
self.dfs(grid, visited, i, j, rows, cols)
return numOfIsland
def dfs(self, grid: List[List[str]], visited: List[List[bool]], row: int, col: int, rows: int, cols: int):
if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == "0" or visited[row][col]:
return
visited[row][col] = True
self.dfs(grid, visited, row + 1, col, rows, cols)
self.dfs(grid, visited, row - 1, col, rows, cols)
self.dfs(grid, visited, row, col + 1, rows, cols)
self.dfs(grid, visited, row, col - 1, rows, cols)
203
LinkedList
Time complexity: O(N), it’s one pass solution. Space complexity: O(1), it’s a constant space solution.
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode prev = dummyNode;
ListNode curr = head;
while(curr != null){
if(curr.val == val){
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return dummyNode.next;
}
}
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(-1)
dummy.next = head
prev = dummy
curr = head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next
205
LinkedList
Iterative approach
Time complexity : O(n). Space complexity : O(1).
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while(curr):
nextTemp = curr.next
curr.next = prev
prev = curr
curr = nextTemp
return prev
206. Reverse Linked List
Iterative
Time complexity : O(n). Space complexity : O(1).
class Solution {
public ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while(current != null){
ListNode tempNext = current.next;
current.next = previous;
previous = current;
current = tempNext;
}
return previous;
}
}
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
previous = None
current = head
while(current):
tempNext = current.next
current.next = previous
previous = current
current = tempNext
return previous
Recursive
Time complexity : O(n). Space complexity : O(n).
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pointer = reverseList(head.next);
head.next.next = head;
head.next = null;
return pointer;
}
}
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if(not head) or (not head.next):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
209. Minimum Size Subarray Sum
Sliding window
Time complexity: O(n). - the right pointer right can move n times and the left pointer left can move also n times in total. - The inner loop is not running n times for each iteration of the outer loop. A sliding window guarantees a maximum of 2n window iterations. It averages out to O(1) when you consider the entire runtime of the algorithm. Space complexity: O(1).
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int right = 0;
int sumOfCurrentWindow = 0;
int result = Integer.MAX_VALUE;
for(right = 0; right < nums.length; right ++){
sumOfCurrentWindow += nums[right];
while(sumOfCurrentWindow >= target){
result = Math.min(result, right - left + 1);
sumOfCurrentWindow -= nums[left ++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
right = 0
sumOfCurrentWindow = 0
result = float('inf')
for right in range(0, len(nums)):
sumOfCurrentWindow += nums[right]
while(sumOfCurrentWindow >= target):
result = min(result, right - left + 1)
sumOfCurrentWindow -= nums[left]
left += 1
return result if result != float('inf') else 0
215. Kth Largest Element in an Array
use heap
Given n as the length of nums,Time complexity: O(n⋅logk), Because our heap is limited to a size of k, operations cost at most O(logk). We iterate over nums, performing one or two heap operations at each iteration.
Space complexity: O(k)
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> topK = new PriorityQueue();
for(int num: nums){
topK.add(num);
if(topK.size() > k){
topK.remove();
}
}
return topK.peek();
}
}
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
topK = []
for num in nums:
heapq.heappush(topK, num)
if len(topK) > k:
heapq.heappop(topK)
return topK[0]
217
HashMap
Time complexity: O(n). Space complexity: O(n).
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> result = new HashSet<>(nums.length);
for(int i = 0; i< nums.length; i++){
if(result.contains(nums[i])){
return true;
}
result.add(nums[i]);
}
return false;
}
}
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
283
array
Space Complexity : O(1). Only constant space is used.
Time Complexity: O(n).
class Solution {
public void moveZeroes(int[] nums) {
int lastNotZeroIndex = 0;
for (int i = 0; i < nums.length; i ++){
if(nums[i] != 0){
nums[lastNotZeroIndex] = nums[i];
lastNotZeroIndex ++;
}
}
for(int i = lastNotZeroIndex; i < nums.length; i ++){
nums[i] = 0;
}
}
}
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
lastNoZeroIndex = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[lastNoZeroIndex] = nums[i]
lastNoZeroIndex += 1
for i in range(lastNoZeroIndex, len(nums)):
nums[i] = 0
344. Reverse String
Double pointers
Time complexity : O(N) to swap N/2 element. Space complexity : O(1), it’s a constant space solution.
class Solution {
public void reverseString(char[] s) {
int start = 0;
int end = s.length - 1;
while(start < end){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start ++;
end --;
}
}
}
class Solution:
def reverseString(self, s: List[str]) -> None:
start = 0
end = len(s) - 1
while(start < end):
tmp = s[start]
s[start] = s[end]
s[end] = tmp
start += 1
end -= 1
389
HashMap
Time Complexity: O(N), Space Complexity: O(1). The problem states string s and string t have lowercase letters. Thus, the total number of unique characters and eventually buckets in the hash map possible are just 26.
class Solution {
public char findTheDifference(String s, String t) {
HashMap<Character, Integer> counter = new HashMap(s.length());
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
counter.put(ch, counter.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
int occr = counter.getOrDefault(ch, 0);
if(occr == 0){
return t.charAt(i);
}
counter.put(ch, --occr);
}
return ' ';
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
counter = Counter(s)
for ch in t:
if ch not in counter or counter[ch] ==0:
return ch
counter[ch] -= 1
485
Time Complexity: O(N), where N is the number of elements in the array.
Space Complexity: O(1). We do not use any extra space.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0;
int max = 0;
for(int i = 0; i< nums.length; i ++){
if(nums[i] == 1){
count ++;
} else {
max = Math.max(max, count);
count = 0;
}
}
return Math.max(max, count);
}
}
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
count = max_count = 0
for num in nums:
if num == 1:
count += 1
else:
max_count = max(max_count, count)
count = 0
return max(max_count, count)
509. Fibonacci Number
Recursion
Time complexity: O(2^N) Space complexity: O(N) it’s usually not recommended.
- Exponential time complexity.
- The number of calls roughly doubles each step → time complexity ≈ O(2^n).
- For n = 30, that’s already over 2 million calls.
- For n = 50, it’s over 20 billion calls
- Repeated work.
- To compute fib(5), you calculate fib(3) multiple times.
- fib(5) → fib(4) + fib(3)
- fib(4) also needs fib(3) again.
- Stack overflow risk We need space proportional to N to account for the max size of the stack, in memory. This stack keeps track of the function calls to fib(N). This has the potential to be bad in cases that there isn’t enough physical memory to handle the increasingly growing stack, leading to a StackOverflowError.
- Better alternatives
class Solution {
public int fib(int n) {
if(n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
}
class Solution(object):
def fib(self, n):
if(n <= 1):
return n
return self.fib(n - 1) + self.fib(n - 2)
Iterative bottom-up approach
Time complexity: O(N) Space complexity: O(1)
class Solution {
public int fib(int N) {
if (N <= 1) {
return N;
}
int current = 0;
int prev1 = 1;
int prev2 = 0;
for (int i = 2; i <= N; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
}
class Solution:
def fib(self, n: int) -> int:
if(n <= 1):
return n
current = 0
previous1 = 1
previous2 = 0
for i in range(2, n + 1):
current = previous1 + previous2
previous2 = previous1
previous1 = current
return current
687. Longest Univalue Path
Depth-First Search
Time complexity: O(N) Space complexity: O(N)
class Solution {
private int longestPath = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return longestPath;
}
private int dfs(TreeNode node){
if(node == null) return 0;
int leftLengthSoFar = dfs(node.left);
int rightLengthSoFar = dfs(node.right);
int leftPath = 0;
int rightPath = 0;
if(node.left != null && node.left.val == node.val){
leftPath = leftLengthSoFar + 1;
}
if(node.right != null && node.right.val == node.val){
rightPath = rightLengthSoFar + 1;
}
longestPath = Math.max(longestPath, leftPath + rightPath);
return Math.max(leftPath, rightPath);
}
}
class Solution:
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
longestPath = 0
def dfs(node: TreeNode) -> int:
nonlocal longestPath
if not node:
return 0
leftLengthSoFar = dfs(node.left)
rightLengthSoFar = dfs(node.right)
leftPath = 0
rightPath = 0
if node.left and node.left.val == node.val:
leftPath = leftLengthSoFar + 1
if node.right and node.right.val == node.val:
rightPath = rightLengthSoFar + 1
longestPath = max(longestPath, leftPath + rightPath)
return max(leftPath, rightPath)
dfs(root)
return longestPath
704. Binary Search
Find the Exact Value
Let n be the size of the input array nums.
Time complexity: O(logn)
nums is divided into half each time. In the worst-case scenario, we need to cut nums until the range has no element, and it takes logarithmic time to reach this break condition. Space complexity: O(1)
During the loop, we only need to record three indexes, left, right, and mid, they take constant space.
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) return mid;
if(nums[mid] < target) left = mid + 1;
if(nums[mid] > target) right = mid - 1;
}
return -1;
}
}
class Solution(object):
def search(self, nums, target):
left = 0
right = len(nums) - 1
while(left <= right):
mid = left + (right-left)/2
if(nums[mid] == target):
return mid
elif(nums[mid] > target):
right = mid - 1
else:
left = mid + 1
return -1
705. Design hashset
use linkedList
Complexity Analysis
Time Complexity: O(K/N), where N is the number of all possible values and K is the number of predefined buckets, which is 769.
Assuming that the values are evenly distributed, thus we could consider that the average size of bucket is O(K/N)
Since for each operation, in the worst case, we would need to scan the entire bucket, hence the time complexity is O(K/N)
Space Complexity: O(K+M) where K is the number of predefined buckets, and M is the number of unique values that have been inserted into the HashSet
class MyHashSet {
private final Bucket[] bucketArray;
private final int keyRange;
public MyHashSet() {
keyRange = 769;
bucketArray = new Bucket[keyRange];
for(int i = 0; i < keyRange; i ++){
bucketArray[i] = new Bucket();
}
}
private int hash(int key){
return key%keyRange;
}
public void add(int key) {
int bucketIndex = hash(key);
bucketArray[bucketIndex].insert(key);
}
public void remove(int key) {
int bucketIndex = hash(key);
bucketArray[bucketIndex].delete(key);
}
public boolean contains(int key) {
int bucketIndex = hash(key);
return bucketArray[bucketIndex].exists(key);
}
}
class Bucket {
private final LinkedList<Integer> container;
public Bucket(){
container = new LinkedList<Integer>();
}
public void insert(Integer key){
int index = container.indexOf(key);
if(index == -1){
container.addFirst(key);
}
}
public void delete (Integer key){
container.remove(key);
}
public boolean exists(Integer key){
int index = container.indexOf(key);
return (index != -1);
}
}
class MyHashSet(object):
def __init__(self):
"""
initialise data structure
"""
self.keyRange = 769
self.bucketArray = [Bucket() for i in range(self.keyRange)]
def _hash(self, key):
return key%self.keyRange
def add(self, key):
bucketIndex = self._hash(key)
self.bucketArray[bucketIndex].insert(key)
def remove(self, key):
bucketIndex = self._hash(key)
self.bucketArray[bucketIndex].delete(key)
def contains(self, key):
bucketIndex = self._hash(key)
return self.bucketArray[bucketIndex].exists(key)
class Node:
def __init__(self, value, nextNode=None):
self.value = value
self.next = nextNode
class Bucket:
def __init__(self):
# a pseudo head
self.head = Node(0)
def insert(self, newValue):
if not self.exists(newValue):
newNode = Node(newValue, self.head.next)
self.head.next = newNode
def delete(self, value):
prev = self.head
curr = self.head.next
while curr is not None:
if curr.value == value:
prev.next = curr.next
return
prev = curr
curr = curr.next
def exists(self, value):
curr = self.head.next
while curr is not None:
if curr.value == value:
return True
curr = curr.next
return False
Binary Search Tree (BST) as Bucket
// todo
881.
Double pointers
Time Complexity: O(NlogN), where N is the length of people. Space Complexity: O(logN). Some extra space is used when we sort people in place.
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int light = 0;
int heavy = people.length - 1;
int answer = 0;
while (light <= heavy){
answer ++;
if(people[light] + people[heavy] <= limit){
light ++;
}
heavy --;
}
return answer;
}
}
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
i,j = 0, len(people) -1
ans = 0
while i <= j:
ans += 1
if people[i] + people[j] <= limit:
i += 1
j -= 1
return ans;
933.
Queue
Time Complexity: O(1) The main time complexity of our ping() function lies in the loop, which in the worst case would run 3000 iterations to pop out all outdated elements, and in the best case a single iteration. Therefore, for a single invocation of ping() function, its time complexity is O(3000)=O(1). Space Complexity: O(1)
As we estimated before, the maximal size of our sliding window is 3000, which is a constant.
class RecentCounter {
private final LinkedList<Integer> timeWindow;
public RecentCounter(){
this.timeWindow = new LinkedList<Integer>();
}
public int ping(int t){
this.timeWindow.addLast(t);
while(timeWindow.getFirst() < t - 3000){
timeWindow.removeFirst();
}
return timeWindow.size();
}
}
class RecentCounter:
def __init__(self):
self.time_window = deque()
def ping(self, t: int) -> int:
self.time_window.append(t)
while(self.time_window[0] < t - 3000):
self.time_window.popleft()
return len(self.time_window)
938. range Sum of BST
DFS
Time Complexity: Worst Case: O(n) - wide range or unbalanced tree Space Complexity: Worst Case: O(n) - skewed BST becomes linked list
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
return dfs(root, low, high);
}
private int dfs(TreeNode currentNode, int low, int high){
int sum = 0;
if (currentNode == null) return sum;
int val = currentNode.val;
if(val >= low && val <= high) sum += val;
if(val > low) sum += dfs(currentNode.left, low, high);
if(val < high) sum += dfs(currentNode.right, low, high);
return sum;
}
}
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
return self.dfs(root, low, high)
def dfs(self, currentNode: TreeNode, low: int, high: int) -> int:
sum = 0
if not currentNode:
return sum
currentVal = currentNode.val
if low <= currentVal <= high:
sum += currentVal
if currentVal > low :
sum += self.dfs(currentNode.left, low, high)
if currentVal < high :
sum += self.dfs(currentNode.right, low, high)
return sum
1456. Maximum Number of Vowels in a Substring of Given length
Sliding window
Time complexity: O(n) Space complexity: O(1)
class Solution {
public int maxVowels(String s, int k) {
Set<Character> vowels = Set.of('a','e','i','o','u');
int result = 0;
for(int i = 0; i < k; i ++){
if(vowels.contains(s.charAt(i))) {
result ++;
}
}
int answer = result;
for(int i = k; i < s.length(); i ++){
result += vowels.contains(s.charAt(i))? 1: 0;
result -= vowels.contains(s.charAt(i-k))? 1: 0;
answer = Math.max(answer, result);
}
return answer;
}
}
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = {'a', 'e','i','o','u'}
count = 0
for i in range(k):
count += int(s[i] in vowels)
answer = count
for i in range(k, len(s)):
count += int(s[i] in vowels)
count -= int(s[i - k] in vowels)
answer = max(answer, count)
return answer