2 Leetcodes a day! (running journal) 🚩
19th Aug
“Don’t practice until you get it right. Practice until you can’t get it wrong.”
1. Group Anagrams
-
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
-
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Example 1:
- Input: strs = [“act”,”pots”,”tops”,”cat”,”stop”,”hat”]
- Output: [[“hat”],[“act”, “cat”],[“stop”, “pots”, “tops”]]
# approach:
# make an empty dictionary and start adding the keys as sorted anagrams.
# if two words are anagrams, it will be the same when they are sorted.
# return the values which will be groups of words which are anagrams
class Solution:
def groupAnagrams(self, strs):
table = {} #init dict
for i in strs:
sorted_strs = ''.join(sorted(i))
if sorted_strs not in table:
table[sorted_strs] = []
table[sorted_strs].append(i)
return table.values()
note: the trick here is to use a dictionary and sort the strings and make them keys. then just add anagrams to the existing keys
2. Top K Elements in List
- Given an integer array nums and an integer k, return the k most frequent elements within the array.
- The test cases are generated such that the answer is always unique.
-
You may return the output in any order.
Example 1:
- Input: nums = [1,2,2,3,3,3], k = 2
- Output: [2,3]
#approach:
# make a dictionary count for each value in nums and sort it in descending order.
# return the top k keys
class Solution:
def topKFrequent(self, nums, k):
nums_counter = Counter(nums)
res = []
nums_counter = dict(sorted(nums_counter.items()), key = lambda i:i[1], reverse = True)
for i, v in nums_counter.items():
if len(res) > k:
break
res.append(i)
return res
note: use counter here and sort it. then just return first k values
20th Aug
“It does not matter how slowly you go as long as you do not stop”
3. Product of array discluding self
- Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
- Each product is guaranteed to fit in a 32-bit integer.
-
Follow-up: Could you solve it in O(n) O(n) time without using the division operation?
Example 1:
- Input: nums = [1,2,4,6]
- Output: [48,24,12,8]
# approach:
# keep two pointers l and r.
# iterate the list with l and r.
# keep the product variable and times with each element using r
class Solution:
def productExceptSelf(self, nums):
l = 0
res = []
while l < len(nums):
prod = 1
for r in range(len(nums)):
if l == r:
continue
prod *= nums[r]
res.append(prod)
l += 1
return res
note: Use 2 pointers to iterate over array and calculate the product except when l = r
4. Longest Consecutive Sequence
- Given an array of integers nums, return the length of the longest consecutive sequence of elements.
- A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element.
-
You must write an algorithm that runs in O(n) time.
Example 1:
- Input: nums = [2,20,4,10,3,4,5]
- Output: 4 (Explanation: The longest consecutive sequence is [2, 3, 4, 5].)
#approach:
# make a set of nums list. iterate over the set.
# if previous number does not exist in set then the longest will start from there.
# and while there is i + length element present in the set, the length will increase by 1.
# then longest will simply be the max of length and longest variable.
class Solution:
def longestConsecutive(self, nums):
numsSet = set(nums)
longest = 0
for i in numsSet:
if (i-1) not in numsSet:
length = 1
while (i + length) in numsSet:
length += 1
longest = max(length, longest)
return longest
note: Use a set to remove dups. then just iterate over nums to see if conseq values exist and increment length. keep track of the longest so far
21st Aug
“Continuous improvement is better than delayed perfection.”
5. Two integer sum II
- Given an array of integers numbers that is sorted in non-decreasing order.
- Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.
- There will always be exactly one valid solution.
- Your solution must use O(1)
-
O(1) additional space.
Example 1:
- Input: numbers = [1,2,3,4], target = 3
- Output: [1,2]
# approach:
# usa two pointer approach where first iteration is through the array and second iteration (r) will be in for loop
# then check if element l + element r == target, if so append to new list
# return the new list
class Solution:
def twoSum(self, nums, target):
l = 0
res = []
while l < len(nums):
for r in range(l+1, len(nums)):
if nums[l] + nums[r] == target:
res.append(l+1)
res.append(r+1)
l += 1
return res
note: iterate with two pointers. check if l + r is target and append to new list
6. Max water container
- You are given an integer array heights where heights[i] represents the height of the ith bar.
-
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
Example 1:
- Input: height = [1,7,2,5,4,7,3,6]
- Output: 36
# approach:
# two points with l at starting and r at end. while l < r
# calculate the max area which is length * breadth
# length will be min of height[l] and height[r]. breadth will be (r - l)
# if l < r then increase l else decrease r
class Solution:
def maxArea(self, heights):
l = 0
r = len(heights) - 1
res = 0
while l < r:
res = max(res, min(heights[l], heights[r]) * (r - l))
if heights[l] < heights[r]:
l += 1
elif heights[r] <= heights[l]:
r -= 1
return res
note: need to calculate the area of rectangle which is l * b. that is what res is for. two pointer approach but l is starting and r is end
22nd Aug
“You’ll never change your life until you change something you do daily.”
7. Is Palindrome
- Given a string s, return true if it is a palindrome, otherwise return false.
-
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Example 1:
- Input: s = “Was it a car or a cat I saw?”
- Output: true
- Explanation: After considering only alphanumerical characters we have “wasitacaroracatisaw”, which is a palindrome.
#Approach:
# iterate over the string to see if the characters are alphabets
# check if each character is a number or an alphabet
# if yes, then lower it and add to empty list with lower method
# Finally check if the list and reverse of the list is equal
class Solution:
def isPalindrome(self, s):
new_list = []
for i in s:
if i.isalnum():
new_list.append(i.lower())
if new_list == new_list[::-1]:
ruturn True
return False
note: need to do check if character in string is legit and lower. append to new list and compare reverse with original. palindrome is reverse = original
8. Buy and sell crypto
- You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
- You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.
-
Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Example 1:
- Input: prices = [10,1,5,6,7,1]
- Output: 6 (Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.)
# approach:
# have a variable x which is float('inf')
# iterate over the list and calulate the minimum of x with x and i
# if i > x then calculate profit as the max of profit and i
#
class Solution:
def maxProfit(self, prices):
res = float('inf')
profit = 0
for i in range(len(prices)):
res = min(res, prices[i])
if prices[i] > res:
profit = max(profit, prices[i]-res)
return profit
note: need to buy at lowest and sell at highest. keep track of lowest price and calculate max profit when a high price is encountered
23rd Aug
9. Longest substring without duplicates
- Given a string s, find the length of the longest substring without duplicate characters.
-
A substring is a contiguous sequence of characters within a string.
Example 1:
- Input: s = “zxyzxyz”
- Output: 3 (Explanation: The string “xyz” is the longest without duplicate characters.)
# approach:
# use a set and a l pointer
# iterate over string and check if char is in set. if it is then remove lth character
# add ith char to set
# calculate res as max of res and window which will be i - l + 1
class Solution:
def lengthofLongestSubstring(self, s):
s_set = set()
l = 0
res = 0
for i in range(len(s)):
while s[i] in s_set:
s_set.remove(s[l])
l += 1
s_set.add(s[i])
res = max(res, i - l + 1)
return res
note: use a set. add new character to set, when a duplicate is encountered, then remove previous char. use two pointers. keep track of the max window
10. Longest repeating substring with replacement
- You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.
-
After performing at most k replacements, return the length of the longest substring which contains only one distinct character.
Example 1:
- Input: s = “XYYX”, k = 2
- Output: 4 (Explanation: Either replace the ‘X’s with ‘Y’s, or replace the ‘Y’s with ‘X’s.)
#approach:
# use a dictionary, l pointer and max pointer
# iterate over s to count the number of each character
# calculate max as max of max pointer and char s
# if the window size - max pointer > k then decrease the count of lth char in dictionary
# return window size
class Solution:
def characterReplacement(self, s, k):
count = {}
l = 0
maxD = 0
for i in range(len(s)):
count[s[i]] = 1 + count.get(s[i], 0)
maxD = max(maxD, count[s[i]])
if (i - l + 1) - maxD > k:
count[s[l]] -= 1
l += 1
return (i - l + 1)
note: use a dictionary to count character occurance. calculate max occurance. see if the window size - max occurace > k, means we need to decrease occurance. use two pointers
24th Aug
11. Permutation String
- You are given two strings s1 and s2.
- Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.
-
Both strings only contain lowercase letters.
Example 1:
- Input: s1 = “abc”, s2 = “lecabee”
- Output: true (Explanation: The substring “cab” is a permutation of “abc” and is present in “lecabee”.)
# approach
# create a hashmap with the count of every character in the string s1
# slide a window over string s2 and decrease the counter for chars occured in the window
# if all counters in hashmap get to zero, means we encountered the permutation
class Solution:
def checkInclusion(self, s1, s2):
cntr, w = Counter(s1), len(s1)
for i in range(len(s2)):
if s2[i] in cntr:
cntr[s2[i]] -= 1
if i >= w and s2[i-w] in cntr:
cntr[s2[i-w]] += 1
if all([cntr[i] == 0 for i in cntr]):
return True
return False
note: better understand
12. Minimum Stack
- Design a stack class that supports the push, pop, top, and getMin operations.
- MinStack() initializes the stack object.
- void push(int val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
-
Each function should run in O (1) O(1) time.
Example 1:
- Input: [“MinStack”, “push”, 1, “push”, 2, “push”, 0, “getMin”, “pop”, “top”, “getMin”]
-
Output: [null,null,null,null,0,null,2,1]
Explanation:
- MinStack minStack = new MinStack();
- minStack.push(1);
- minStack.push(2);
- minStack.push(0);
- minStack.getMin(); // return 0
- minStack.pop();
- minStack.top(); // return 2
- minStack.getMin(); // return 1
#approach:
# inititate two lists, one for stack and another for minstack
# for push, append to stack first, then calculate the min, then append to minstack
# for pop, just pop from both
# for top, just return last element from stack
# for getMin, just return last element from minStack
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val):
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self):
self.stack.pop()
self.minStack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.minStack[-1]
note: start with two stacks - one to keep min values and other is normal. when pushing calculate the min and then append to minstack
25th Aug
13. Evaluate reverse polish notation
- You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.
- Return the integer that represents the evaluation of the expression. -The operands may be integers or the results of other operations.
- The operators include ‘+’, ‘-‘, ‘*’, and ‘/’.
-
Assume that division between integers always truncates toward zero.
Example 1:
- Input: tokens = [“1”,”2”,”+”,”3”,”*”,”4”,”-“]
- Output: 5 (Explanation: ((1 + 2) * 3) - 4 = 5)
#approach:
# have an empty stack
# make if conditions for all the operational character and append to stack accordingly
# pop the last two element from the stack first and then append a new element
class Solution:
def evalRPN(self, tokens):
stack = []
for i in tokens:
if i == '+':
stack.append(stack.pop() + stack.pop())
elif i == '-':
a, b = stack.pop(), stack.pop()
stack.append(b-a)
elif i == '*':
stack.append(stack.pop() * stack.pop())
elif i == '/':
c, d = stack.pop(), stack.pop()
stack.append(int(float(d)/c))
else:
stack.append(int(i))
return stack[0]
note: boring question
14. Generate parenthesis
-
You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.
Example 1:
- Input: n = 1
- Output: [”()”]
Example 2:
- Input: n = 3
- Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
#approach:
# use backtracking with two pointers
class Solution:
def generateParenthesis(self, n):
stack = []
res = []
def backtrack(openN, closeN):
if openN == closeN == n: # base case
res.append(''.join(stack))
if openN < n:
stack.append("(")
backtrack(openN+1, closeN)
stack.pop()
if closeN < openN:
stack.append(")")
backtrack(openN, closeN+1)
stack.pop()
backtrack(0,0)
return res
note: use backtracking. need to undertand more
26th Aug
15. Daily temperatures
- You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.
-
Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.
Example 1:
- Input: temperatures = [30,38,30,36,35,40,28]
- Output: [1,4,1,2,1,0,0]
#approach:
# create an array of zeroes which will be equal to the len of temp
# create an empty stack
# iterate with index and value over temp list
# check if current value of element in list is greater than the last value in stack
# if so, then pop value and index from stack
# change the element in array with zeroes for that particular index
# append value and index in stack
class Solution:
def dailyTemperatures(self, temp):
res = [0] * len(temp)
stack = []
for i, v in enumerate(temp):
while stack and v > stack[-1][0]:
stackT, stackInd = stack.pop()
res[stackInd] = i - stackInd
stack.append((v,i))
return res
note: your stack will store the index and value. your res will only store the difference in index. good question
16. Binary search
- You are given an array of distinct integers nums, sorted in ascending order, and an integer target.
- Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.
-
Your solution must run in O(logn) and O(logn) time.
Example 1:
- Input: nums = [-1,0,2,4,6,8], target = 4
- Output: 3
#approach:
# initiate a left and right pointer at 0 and end of list respectively
# check while l < r
# calculate middle element
# check if middle < target, which means we can bring out l pointer forward upto middle
# check if middle > target, which means we can bring down r pointer upto middle
# else we return middle which means the target is found
class Solution:
def search(self, nums, target):
l = 0
r = len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] < target:
l = m + 1
elif nums[m] > target:
r = m - 1
else:
return m
return -1
note: very fundamental.
27th Aug
17. Balanced binary tree
# approach:
# do it recursively with DFS
# return a boolean value and the height
# calculate the balance as the diff between left and right subtree should be less than 1
# balance is only going to be true if left and right subtrees are balanced
class Solution:
def isBalanced(self, root):
def dfs(root):
if not root:
return [True, 0]
left = dfs(root.left)
right = dfs(root.right)
balance = (left[0] and right[0] and
abs(left[1]-right[1]) <= 1)
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
18. Lowest common ancestor of binary search tree
# start with the root as it is always the common ancestor
# left subtree is always going to be less than parent and right subtree is going to be greater than parent
# time complexity will be height of the tree which is usually log(n)
class Solution:
def lowestCommonAncestor(self, root):
cur = root
while cur:
if p.val > cur.val and q.val > cur.val:
cur = cur.right
elif p.val < cur.val and q.val < cur.val:
cur = cur.left
else:
return cur
28th Aug
19. Implement queue using stacks
queue is a FIFO data structure. main operations in queue are push and pop. peek is to return the element in the front. push will be O(1) and pop should be O(n), how to get pop in constant time? peek is technically getting the last element
class Solution:
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x):
self.s1.append(x)
def pop(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self):
return max(len(self.s1), len(self.s2)) == 0
20. Climbing stairs
# two variables shifting n - 1 times. already accounting for the first step during initialization
class Solution:
def climbStairs(self, n):
one, two = 1,1
for i in range(n-1):
tmp = one
one = one + two # number of ways to reach the current step
two = tmp
return one # this contains the number of ways to climb n steps
29th Aug
21. Longest Palindrome
Palindome is a string which is the same when reversed. odd and even length string matters For odd length string, we need a pair of matching pairs and a single character which is not a pair for even length, we need all pairs need to have a hasmap to count the number of chars in string.
class Solution:
def longestPalindrom(self, s):
count = defaultdict(int)
res = 0
for c in s:
count[c] += 1
if count[c] % 2 == 0: #if there is a pair then you increment the result by 2
res += 2
# if the count is odd, then increment the result by 1
for cnt in count.values():
if cnt % 2 == 1:
res += 1
break
return res
22. Reverse Linked list
Have a prev pointer which will be none and then iterate over LL starting from head. point each next pointer to prev node
class Solution:
def reverseList(self, head):
prev = None
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
return prev
note: memorize this
30th Aug
23. max depth of binary tree
Recursively iterate over the tree
class Solution:
def maxDepth(self, root):
if not root:
return 0
return 1 + (self.maxDepth(root.left), self.maxDepth(root.right))
note: easy recursive implementation on left and right subtrees and finding max. don’t forget base case in recursion
24. middle of linked list
Have two pointers slow and fast. iterate over fast until the end of the list which slow incrementing as well. when fast will reach the end slow will reach the middle.
class Solution:
def middleNode(self, head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
note: slow and fast pointers. slow will be in middle when fast reach the end.
31st Aug
25. maximum subarray
can compute every single subarray maintain a current sum variable which will add the element in the array another variable which will maintain the max subarray. it will be initialized to the first array element
class Solution:
def maxSubArray(self, nums):
maxSub = nums[0]
curSum = 0
for i in nums:
if curSum < 0:
curSum = 0
curSum += i
maxSub = max(maxSub, curSum)
return maxSub
note: easy keep a maxsub total and cursum. simply add elements to cursum and calculate max
26. insert intervals
iterate over the lists of list to check whether there is an overlap between previous and current subarray if there is then find the max also need to sort the interval list by start time first and set the prev to the start time of first interval in the loop, append prev to new list (merged)
class Solution:
def insert(self, intervals, newIntervals):
intervals.append(newIntervals)
merged = []
intervals.sort(key=lambda x:x[0])
prev = intervals[0]
for i in intervals[1:]:
if prev[1] >= i[0]: #there is an overlap if this is true
prev[1] = max(prev[1], i[1])
else:
merged.append(prev)
prev = i
merged.append(prev)
return merged
1st Sept
27. binary tree level order traversal BFS
start with a queue with root in it. iterate over the queue to pop the first element and append to level list then append left and right nodes of the tree to the queue
class Solution:
def levelOrder(self, root):
q = [root]
res = []
while q:
level = []
for i in range(len(q)):
node = q.pop(0)
if node:
level.append(node.val)
q.append(node.left)
q.append(node.right)
if level:
res.append(level)
return res
note: memorize this
28. combination sum
each candidate, we’re exploring two possibilities: either we include it in our combination (potentially multiple times) or we don’t. This creates a decision tree that the DFS traverses, building up combinations and backtracking when necessary.
class Solution:
def combinationSum(self, candidates, target):
res = []
def dfs(i, lst, total):
if total == target:
res.append(lst.copy())
return
if i >= len(candidates) or total > target:
return
# Include the current candidate: We append it to lst, update the total, and recurse
lst.append(candidates[i])
dfs(i, lst, total+candidates[i])
# Exclude the current candidate: We move to the next index without changing lst or total
lst.pop()
dfs(i+1, lst, total)
dfs(0, [], 0)
return res
note: in the backtracking function, use 3 variables - i, empty list and total sum so far. then cover including and excluding current candidate possibilities. would be easier to memo
2nd Sept
29. permutations
swapping elements to generate all possible arrangements. time complexity of this algorithm is O(n!)
class Solution:
def permute(self, nums):
res = []
def backtracking(start, end):
#base case
if start == end:
res.append(nums[:])
for i in range(start, end):
nums[i], nums[start] = nums[start], nums[i]
backtracking(start+1, end)
nums[i], nums[start] = nums[start], nums[i]
backtracking(0, len(nums))
return res
30. subsets
making a binary choice (include/exclude) for each element and exploring all paths in the resulting decision tree, we naturally generate all possible subsets of the input list.
class Solution:
def subsets(self, nums):
res = []
subset = []
def dfs(i):
if i == len(nums):
res.append(subset.copy())
return
subset.append(nums[i])
dfs(i + 1)
subset.pop()
dfs(i + 1)
dfs(0)
return res
3rd Sept
31. diameter of binary tree
class Solution:
def diameterofBinaryTree(self, root):
res = [0]
def dfs(root):
if not root:
return -1
left = dfs(root.left)
right = dfs(root.right)
res[0] = max(res[0], left + right + 2) #updates the maximum diameter.
return 1 + max(left, right) #height of the subtree
dfs(root)
return res[0]
32. increasing triplet subsequence
class Solution:
def increasingTriplet(self, nums):
first = second = float('inf')
for i in nums:
if i <= first:
first = i
elif i <= second:
second = i
else:
return True
return False
4th Sept
33. move zeroes
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
non_zero = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[non_zero], nums[i] = nums[i], nums[non_zero]
non_zero += 1
note: keep track of zero, iterate over nums to check non zero elements and swap with zero element to push zeroes ar the end. it should be in place
34. swap nodes in pairs
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = first.next
first.next = second.next
second.next = first
prev.next = second
prev = prev.next.next
return dummy.next
5th Sept
35. Determine if two strings are close
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
if set(word1) == set(word2):
word1_c = Counter(word1)
word2_c = Counter(word2)
return sorted(word1_c.values()) == sorted(word2_c.values())
note: use counter to compare two strings and sort them values
36. Equal rows and cols
#approach
# Iterate through each row
# For each row, compare it with every column
# If a row and column are equal, increment a counter
# Return the final count
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
count = 0
l = 0
for i in range(len(grid)):
for j in range(len(grid)):
if all(grid[i][k] == grid[k][j] for k in range(len(grid))):
count += 1
return count
6th Sept
37. Can place flowers
# approach
# Iterate through the flowerbed
# Check if a flower can be planted
# If yes, plant and increment count
# If count equals n, return true immediately
class Solution:
def canPlaceFlowers(self, flowerbed, n):
if n == 0:
return True
count = 0
for i in range(1, len(flowerbed)-1):
if flowerbed[i-1] == flowerbed[i] == flowerbed[i+1] == 0:
flowerbed[i] = 1
count += 1
if count == n:
return True
return False
note: just check if adjacent values are 0 in flowerbed. if so that is good and increment count
38. Reverse vowels in string
- two pointer
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set('aeiouAEIOU')
l = 0
r = len(s)-1
while l < r:
if s[l] not in vowels:
l += 1
elif s[r] not in vowels:
r -= 1
else:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
print(s)
return ''.join(s)
7th Sept
39. Max number of K pairs
- hashmap
#approach
# Count occurrences of each number in a dictionary
# Iterate through the array once
# For each number, check if its complement (k - num) exists
# Update the count and increment the operations counter
class Solution:
def maxOperations(self, nums, k):
count = Counter(nums)
operations = 0
for num in count:
complement = k - num
if num == complement:
operations += count[num] // 2
elif complement in count:
operations += min(count[num], count[complement])
count[num] = 0
count[complement] = 0
return operations
40. Maximum average subarray I
- sliding window
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
curr_sum = sum(nums[:k])
max_sum = curr_sum
for i in range(1, len(nums) - k + 1):
curr_sum = curr_sum - nums[i-1] + nums[i+k-1]
max_sum = max(max_sum, curr_sum)
return max_sum / k
8th Sept
41. Max number of vowels in a substring of given length
- sliding window
def maxVowels(self, s, k):
vowels = set('aeiou')
count = sum(1 for char in s[:k] if char in vowels)
# print('count', count)
max_count = count
for i in range(k, len(s)):
if s[i-k] in vowels:
count -= 1
if s[i] in vowels:
count += 1
max_count = max(max_count, count)
return max_count
42. max consecutive ones III
- sliding window
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = right = zeros_count = max_length = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros_count += 1
while zeros_count > k:
if nums[left] == 0:
zeros_count -= 1
left += 1
max_length = max(max_length, right - left + 1)
return max_length
9th Sept
43. Longest Subarray of 1’s After Deleting One Element
- sliding window
class Solution:
def longestSubarray(self, nums):
n = len(nums)
left = zeros = ans = 0 #set left to 0
for right in range(n):
if nums[right] == 0: # if we encounter a zero then increment
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
ans = max(ans, right - left + 1 - zeros)
return ans - 1 if ans == n else ans
44. find pivot index
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
left_sum = 0
total_sum = sum(nums)
for r in range(len(nums)):
right_sum = total_sum - left_sum - nums[r]
if left_sum == right_sum:
return r
left_sum += nums[r]
return -1
10th sept
45. coin change
- approach: can we be greedy? what is greedy?
- initiate a dp array
class Solution:
def coinchange(self, coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for a in range(1, amount+1):
for c in coins:
if a - c >= 0:
dp[a] = min(dp[a], 1 + dp[a-c])
return dp[amount] if dp[amount] != amount + 1 else -1
46. Find median in data stream
- Use heap. with a small heap and large heap
class MedianFinder:
def __init__(self):
self.small, self.larrge = [], []
def addNum(self, num):
heapq.heappush(small, -1 * num) # this is max heap
#every num in small heap <= every num in large heap
if (small and large and (-1* self.small[0]) > self.large[0]):
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
#uneven size of both heaps
if len(small) > len(large) + 1:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(large) > len(small) + 1:
val = heapq.heapop(self.large)
heapq.heappush(self.small, -1 * val)
def findMedian(self):
if len(small) > len(large):
return self.small[0]
if len(large) > len(small):
return self.large[0]
return (self.small[0] + self.large[0]) / 2
11th Sept
47. Find min in rotated sorted array
- use two pointers and binary search
class Solution:
def findMin(self, nums):
res = nums[0]
l, r = 0, len(nums)-1
while l <= r:
#if the array is sorted
if nums[l] < num[r]:
res = min(res, nums[l])
break
#if the array is not sorted, then use binary search
m = (l + r)//2
res = min(res, nums[m])
if nums[m] >= nums[l]:
l = m + 1
else:
r = m - 1
return res
48. Meeting rooms
- just need to return a boolean if there is an overlap between start and end times
class Solution:
def canAttendMeetings(self, intervals):
intervals.sort(key=lambda i: i.start)
for i in range(1, len(intervals)):
i1 = intervals[i-1]
i2 = intervals[i]
if i1.end > i2.start:
return False
return True
12th Sept
49. Meeting rooms II
- maintain a variable count to track the number of meetings
- iterate over the intervals to check if meeting has started or ended
- iterate through the end meeting time and then iterate through start meeting time
class Solution:
def minMeetingRooms(self, intervals):
start = sorted([i.start for i in intervals])
end = sorted([i.end for i in intervals])
res, count = 0,0
s, e = 0, 0 #start and end time
while s <len(intervals):
#if start time is less than end time, that means another meeting has started
if start[s] < end[e]:
s += 1
count += 1
# else meeting has ended
else:
e += 1
count -= 1
res = max(res, count)
return res
50. Maximum product subarray
- use DP
- need to make the largest contiguous product in the array
- if we get all positive numbers, just multiple all
- if its all negative, then it depends on the len(nums)
- keep track of the minimum prod subarray too
class Solution:
def maxProduct(self, nums):
res = max(nums)
curMin, curMax = 1,1 #1 is neutral value
for n in nums:
if n == 0:
curMin, curMax = 1,1
continue
#need to keep track of curMax
tmp = curMax * n
#if curMax, curMin is positive or both negative then n
curMax = max(n * curMax, n * curMin, n)
curMin = min(tmp, n * curMin, n)
res = max(res, curMax, curMin)
return res
13th Sept
51. Minimum window substring
class Solution:
def minWindow(self,s,t):
countT, window = {}, {}
for c in t:
#build hasmap with count
countT[c] = 1 + countT.get(c, 0)
have, need = 0, len(countT)
res, resLen = [-1,-1], float('inf')
l = 0
#iterate over s string
for r in range(len(s)):
c = s[r]
window[c] = 1 + window.get(c,0)
if c in countT and window[c] == countT[c]:
have += 1
while have == need:
#update result
if (r - l + 1) < resLen:
res = [l,r]
resLen = (r - l + 1)
# pop from left of our window
window[s[l]] -= 1
#update the have pointer
if s[l] in countT and window[s[l]] < countT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float('inf') else ""
52. Merge intervals
- think of a number line with intervals on it and see if there is an overlap
- sort the intervals based on the start value
- O(nlog(n))
class Solution:
def merge(self, intervals):
intervals.sort(key = lambda i: i[0])
output = [intervals[0]]
for start, end in intervals[1:]:
output[-1][1] ##get the most recent value and it's end value