Algo go to Flashcards
https://leetcode.com/problems/valid-parentheses/
Make a dict with bracket_ref = {“}”:”{“, “]”:”[”, “)”:”(“}
create empty stack
Iterate in str, check if char is not in bracket_ref then append in stack
Else,
check if stack is not empty and char == stack[-1], then continue
else, return False
At the end check if stack is not empty return False, else return True
https://leetcode.com/problems/merge-two-sorted-lists
create new node head and curr is same as head. if compare list1 and list2 val and do curr.next whichever is less. then update that list node to next and curr also next. At end return head.next
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
1) single transaction, Keep in mind that max should come after min, whenever min is updated also update max. Whenver min is update make max = -1
2) multiple transactions, run while loop till u find min number and while loop till max num , find difference and keep track of max diff and keep updating min and max variables in outer while loop
https://leetcode.com/problems/invert-binary-tree/
if root is None:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
Binary search
l = 0
r = len(nums)-1
while l <= r:
mid = (l+r)//2
if target == nums[mid]:
return mid
if target < nums[mid]:
r = mid-1
else:
l = mid+1
return -1
https://leetcode.com/problems/maximum-subarray/
curr_sum = nums[0]
max_till_now = nums[0]
for i in range(1, len(nums)):
curr_sum += nums[i]
curr_sum = max(curr_sum, nums[i])
max_till_now = max(max_till_now, curr_sum)
return max_till_now
https://leetcode.com/problems/insert-interval/description/
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
create empty result list
iterate over input list
check if current element end is less than newInterval start, that means element will
come into the result list.
if current element start is more than newInterval end, that means newinterval is smaller and will come into result list. But update the newInterval variable with current element, bcz that is not appended till now. otherwise, we know there is an overlap, so newInterval start becomes minimum of newInterval start or current element, similarly, end becomes max of the 2.
Continue
at the end remember to append newInterval
Print level order traversal line by line
Do it like normal level order traversal, just add Null after pushing root in the queue.
And while iteration check if Null comes then pop the Null and add Null again in the queue (so that null is added after every level)
OR
Take the length of queue and iterate it that times only.
Zig zag Level order traversal
Take 2 stacks.
add root in S1.
Run while loop on S1 or S2:
check if S1 is not empty, then pop and print and add in S2, first left and then right.
Check if s2 is not empty, then pop and add in S1, first right and then left.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
2 scenarios:
1) if both keys are present mentioned in ques
recursively go to left and right and check if root.key == n1 or root.key == n2, if yes in that case return the root.
After recursion check if left_lca and right_lca both present return root (it will happen when both are in different subtree)
Otherwise return which ever is present( it will happen when one lca is present in same subtree of other lca
2) It is not mandatory that both keys are present
Take a list v =[False, False]
do same as above but also update v list value, if n1 is present v[0] = True, if n2 is present v[1] = True
Now check if v[0] and v[1] are true then return root (case of lca in diff subtrees)
if only v[0] is true, find n2 in its subtree find(left_lca, n2) – left_lca is considered as root
same if only v[1] is true, find n1 in its subtree find(right_lca, n1)
Maximum subarray
https://leetcode.com/problems/maximum-subarray/submissions/919244531/
Take 2 variables curr_sum and curr_max save zero index value in both, start from index one and iterate take current index item and add in curr_sum.
Check if current item is larger than curr_sum then curr_sum = current item otherwise the curr_sum = added part.
for curr_max, check if curr_max is greater or curr_sum
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.
https://leetcode.com/problems/01-matrix/description/
Bcz we have to find nearest cell we will do BFS and not DFS.
Replace all 1s with MAX_VALUE
take a queue and append all the row,col which contains 0, as we have to find the nearest path.
Now we will iterate the queue like we do in BFS and pop the elements from queue and check in all 4 directions if the value of current cell after adding direction is greater than source cell+1. if yes, replace current cell value with source cell+1
https://leetcode.com/problems/balanced-binary-tree/description/
Check if tree is height balanced or not
At each point do recursive call and check if left height minus right height is greater than 1 then return -1 otherwise calculate max(lh,rh)+1 and return
Merge K sorted arrays (not list)
Take min heap and insert -
for i, item in enumerate(arr):
heappush(min_heap,[item[0], i, 0])
keep popping the top of heap and merge in new array and check if the next index of that array exists then insert the next element.
code:
from heapq import heapify, heappush, heappop
def merge_sorted_arrays(arr,k):
min_heap = []
merged_array = []
for i, item in enumerate(arr):
heappush(min_heap,[item[0], i, 0])
while min_heap:
elem = heappop(min_heap)
merged_array.append(elem[0])
if len(arr[elem[1]]) > elem[2]+1:
heappush(min_heap,[arr[elem[1]][elem[2]+1], elem[1], elem[2]+1])
print("res:", merged_array)
arr = [[2, 6, 12, 34], [1, 9, 20, 1000], [23, 34, 90, 2000]]
merge_sorted_arrays(arr, len(arr))
Find median of stream of numbers
https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
We have to maintain two heaps min_heap for maximum side and max_heap for minimum side. so that the top of both heaps can give in median.
Either both heaps can contain equal number of items or max_heap(smaller side) will contain one extra item.
Push in max_heap and pop and push back in min_heap. check length if greater side heap has more elements pop and push back.
check if lengths are different that means there are odd number of elements then print max_heap[0]
else
add and divide by 2 both heaps top
from heapq import heappush, heappop
def find_median(arr, n):
large = []
small = []
for item in arr:
heappush(small, -item)
heappush(large, -heappop(small))
if len(large) > len(small):
heappush(small, -heappop(large))
if len(large) != len(small):
print(-small[0])
else:
print((small[0]+large[0])/2)
if __name__ == ‘__main__’:
arr = [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4]
n = len(arr)
find_median(arr, n)
