Deck 3 Flashcards
Valid anagram
Algorithm:
-check length and return False if unequal
-define counter array for 26 alphabets
-iterate and add 1 in position for char in s, subtract 1 for char in t simultaneously
-iterate through counter and return False if value not 0
-return True
Group anagrams
Idea:
-group the strings into dictionary based on the char counts
Algorithm:
-define answer as defaultdict(list)
-for every string in strs:
-counter = [0] * 26
-for every char in string:
-counter[char] += 1
-end for
-answer[tuple(counter)].append(string)
-end for
-return list(answer.values())
Top k frequent elements
Idea:
One way is to store frequency in a dictionary, then sort it using the frequency and pick first k ones
Second way is using heap
Algorithm:
-declare and define the counts dictionary
-for every entry in dictionary
-push into heap
-if heap length > k, pop from the heap
-end for
-loop k times and pop from heap and append the number to the answer
-return answer
Encode and decode strings
Idea:
-encode along with length and an identifier like “#”
Solution:
1. ENCODE
-initialize result as string
-for every s, append len(s) + “#” + s to the result
-return s
- DECODE
-initialize res and i as [] and 0 respectively
-while i < len(s)
-j = i
-while s[j] != “#”
-j += 1
-end while
-length = int(s[i : j])
-res.append(s[j + 1, j + 1 + length])
-i = j + 1 + length
-end while
-return res
Product of array except self
Idea:
Calculate prefix product and then postfix product
Algorithm:
-prefix = 1 and answer = []
-for every number
-answer.append(prefix) and prefix *= nums[i]
-end for
-postfix = 1
-for every number in reverse
-answer[i] *= postfix and postfix *= nums[i]
-end for
-return answer
Longest consecutive sequence
Idea:
Create a set of the given array and check if the number + 1 is present for the current number. Increase seq length if there is
Algorithm:
-if not nums, return 0
-num_set = set(nums)
-max_seq = 1
-for number in num_set
-if number - 1 not in num_set
-curr_seq = 1
-while (number + 1) in num_set
-curr_seq += 1 and number += 1
-end while
-reassign max_seq
-end if
-end for
-return max_seq
Valid palindrome
Idea:
Start with l and r pointers, and check if the chars are equal
Algorithm:
-init l and r to 0 and len - 1
-while l < r
-while l < r and s[l] not alphanum, l += 1
-while l < r and s[r] not alphanum, r -= 1
-if s[l].lower() != s[r].lower(), return False
-inc l and dec r
-end while
-return True
Container with most water
Idea:
We start with left and right pointers, calculate the max volume while moving them closer based on the height comparison
Algorithm:
-initialize l, r and max_volume
-while l < r
-calculate current volume and reassign max_volume
-if height at l <= r, inc l
-else dec r
-end if else
-end while
-return max_volume
Longest substring without repeating characters
Idea:
Two pointer approach.
One way is to remove the l characters from the set and inc l until there r character is not it it. Then add r char to set and calculate result every iteration
Another way is similar, but we store the position of the r char in map and calculate the length based on that
Solution 1:
-initialize l, charset, max_len
-for r in range length
-while r char not it charset
-remove l char from set
-inc l
-end while
-add r char to set
-reassign max_len
-end for
-return max_len
Solution 2:
-intialize l, charmap, max_len
-for r in range length
-if char at r already in map
-assign l = max(charmap[s[r]] + 1, l)
-end if
-charmap[s[r]] = r
-reassign max_len
-end for
-return max_len
Longest repeating character replacement
Idea:
We maintain a hashmap of frequencies. And we only replace characters within the window which are not the most frequent
Algorithm:
-initialize map, answer and left
-for right in range length
-map[right] += 1
-while (r - l + 1) - max(map.values()) > k:
-dec map[left]
-inc left
-end while
-answer is max between itself and (r - l + 1)
-end for
-return answer
Find minimum in rotated sorted array
Idea:
Standard binary search, we just move the pointers based on if we are in the correctly sorted subarray
Algorithm:
-answer = nums[0]
-init left and right pointers
-while left <= right
-if nums[left] < nums[right]
-answer = max(answer, nums[left])
-break
-end if
-calculate mid
-answer = max(answer, nums[mid])
-if nums[mid] >= nums[left], left = mid + 1
-else, right = mid - 1
-end if else
-end while
-return answer
Search in rotated sorted array
Idea:
Find whether we are in left sorted or right sorted array and based on that, change the left or right pointers
Algorithm:
-initialize left and right pointers
-while left <= right
-mid = (left + right) // 2
-if target is at mid, return mid
-end if
-if left <= mid
-if target > mid or target < left, left = mid + 1
-else right = mid + 1
-end if else
-else
-if target < mid or target > right, right = mid + 1
-else left = mid + 1
-end if else
-end if else
-return -1
Reorder list
Idea:
Use slow and fast pointer to find the middle part of the list
De link that and then reverse the 2nd list
Then merge them
Remove nth node from end of list
-Move a right pointer n times to the right, then move left and right simultaneously till right reaches end. The next of left needs to be removed
Lowest common ancestor of a binary search tree
-If current val is greater than both p and q value, go into left subtree
-if less than both, go into right subtree
-else return current
Kth smallest element in a BST
Idea:
Inorder traversal and then return the kth element
Algorithm:
-init n, stack and curr as 0, [] and root respectively
-while curr or stack:
-while curr, append curr to stack and curr = curr.left
-end while
-curr = stack.pop()
-inc n
-if n = k, return curr.val
-end if
-curr = curr.right
-end while
Construct binary tree from preorder and inorder traversal
Idea:
Find the root index in the inorder traversal, i.e index of first element in preorder and then recursively call the method on the array splits
Algorithm:
-if not preorder or inorder, return None
-end if
-root_index = inorder.index(preorder[0])
-root = Node(preorder[0])
-root.left = call(preorder[1 : root_index + 1], inorder[: root_index])
-root.right = call(preorder[root_index + 1 :], inorder[root_index + 1 :])
-return root
Clone graph
Idea:
Create a map of old to new node and then recursively append the copy of each nodes neighbors
Algorithm:
-define node_map as {}
-define dfs function with node for param as follows
-if node in node_map, return node_map[node]
-end if
-copy = Node(node.val)
-node_map[node] = copy
-for each neighbor of node
-copy.neighbors.append(dfs(neighbor))
-end for
-return copy
-end func
-return dfs(node) if node else return None
Graph valid tree
Idea:
Build an adjacency list. Use a visited set to recursively check for cycles. Valid tree if no cycle and length of set equal to number of nodes (cause disconnected nodes)
Algorithm:
-if not n, return True (coz empty graph is still valid tree)
-build adjacency list in form of dict(i, [neighbors]) and define visited set
-define dfs function with i and prev for param as follows
-if i in visited, return False
-end if
-add i to visited
-for every j in adj[i]:
-if j is prev, continue
-end if
-if not dfs(j, i), return False
-end if
-end for
-return True
-end func
-return dfs(0, -1) AND n == len(visited)
Number of connected components in an undirected graph
Idea:
Use dfs and visited set to track connected nodes for one node
Algorithm:
-if n is 1, return 1
-init number of components as 0, empty visited set and generate adjacency list
-define dfs function with node for param as follows
-for each neighbor in adj list of node
-if neighbor not visited
-add neighbor to visited
-dfs(neighbor)
-end if
-end for
-end func
-for each node in adj list
-if node not in visited
-add node to visited
-inc number of components
-dfs(node)
-end if
-end for
-return number of components`
