Doing LeetCode
with java and python
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
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
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
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
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
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)
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)