leetcode Flashcards
STATEMENT
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
EXAMPLES
[2, 7, 11, 15], 9 -> [0,1]
CLARIFICATIONS
- What happens when there is no solution? Assume solution exists.
- Can the list be empty? No.
- Is the list sorted? Not necessarily.
COMMENTS
- We can ‘remember’ what we have seen so far in O(n) space complexity using a set.
- Iterate the list and at every step, we can look back and see there is a possible candidate for complement of the current item.
- O(n) time complexity and O(n) space complexity.
- To do without the space complexity, we may have to move to O(n log n) time complexity, by sorting the list
and then using two pointers from start and end.
“””
def twoSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hash_dict = {}
for i in range(len(nums)):
compl = target-nums[i]
if compl in hash_dict:
return [hash_dict[compl], i]
hash_dict[nums[i]] = i
STATEMENT
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all the unique triplets.
CLARIFICATIONS
- Do I return tuple of elements of their indexes? Elements.
- The solution may not exist, right? Yes.
- By unique, you mean, each tuple should be considered as set and then unique set of sets? Yes.
EXAMPLES
[-1, 0, 1, 2, -1, -4] ->
[
[-1, 0, 1],
[-1, -1, 2]
]
COMMENTS
- We can first try to solve the problem for two elements that add up to a given target.
- Then, we can use that function to solve this for each element in the array.
- We have to be extra careful to make the tuples unique.
- First, we would assume the two_sum function exists already and write that later.
- When we find a valid tuple, we need to sort them to ensure the uniqueness.
- We’d accumulate the tuples in a set, but since lists are mutable, they can’t be in a set.
We can make the valid tuple a string joined by a delimiter, say comma.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
nums.sort()
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
l,r = i+1,len(nums)-1
while l0:
r = r-1
else:
ans.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l = l+1
r = r-1
return ans
time - O(n*n)
space- O(n)
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
“””
Do not return anything, modify matrix in-place instead.
“””
is_col = False
R = len(matrix)
C = len(matrix[0])
for i in range(R):
# Since first cell for both first row and first column is the same i.e. matrix[0][0]
# We can use an additional variable for either the first row/column.
# For this solution we are using an additional variable for the first column
# and using matrix[0][0] for the first row.
if matrix[i][0] == 0:
is_col = True
for j in range(1, C):
# If an element is zero, we set the first element of the corresponding row and column to 0
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
# Iterate over the array once again and using the first row and first column, update the elements.
for i in range(1, R):
for j in range(1, C):
if not matrix[i][0] or not matrix[0][j]:
matrix[i][j] = 0
# See if the first row needs to be set to zero as well
if matrix[0][0] == 0:
for j in range(C):
matrix[0][j] = 0
# See if the first column needs to be set to zero as well
if is_col:
for i in range(R):
matrix[i][0] = 0
Time Complexity : O(M \times N)O(M×N)
Space Complexity : O(1)O(1)
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()
Time Complexity: O(NK \log K)O(NKlogK), where NN is the length of strs, and KK is the maximum length of a string in strs. The outer loop has complexity O(N)O(N) as we iterate through each string. Then, we sort each string in O(K \log K)O(KlogK) time.
Space Complexity: O(NK)O(NK), the total information content stored in ans.
class Solution:
def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
ans[tuple(count)].append(s)
return ans.values()
Time Complexity: O(NK)O(NK), where NN is the length of strs, and KK is the maximum length of a string in strs. Counting each string is linear in the size of the string, and we count every string.
Space Complexity: O(NK)O(NK), the total information content stored in ans.
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dict = {}
start = maxl = 0
for i,c in enumerate(s):
if c in dict and start <= dict[c]:
start = dict[c]+1
else:
maxl = max(maxl, i - start +1)
dict[c] = i
return maxl
Time complexity : O(2n) = O(n)O(2n)=O(n). In the worst case each character will be visited twice by ii and jj.
Space complexity : O(min(m, n))O(min(m,n)). Same as the previous approach. We need O(k)O(k) space for the sliding window, where kk is the size of the Set. The size of the Set is upper bounded by the size of the string nn and the size of the charset/alphabet mm.
Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
time: O(n*n)
space: O(n)
Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]
Output: true
Example 2:
Input: [5,4,3,2,1]
Output: false
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
# we can use two thresholds to divide the subsquence length
# everything between threshold1 and threshold2 will form doublets
# everything above threshold2 will form a triplet
# dynamically change these two thresholds
threshold1 = threshold2 = float("inf")
for num in nums:
# lower threshold1
if num <= threshold1:
threshold1 = num
# lower threshold2
elif num <= threshold2:
threshold2 = num
# if greater than both thresholds (note equal doesn't count)
else:
return True
return False
O(n)
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
result = ListNode(0)
result_tail = result
c = 0
while l1 or l2 or c:
lv1 = l1.val if l1 else 0
lv2 = l2.val if l2 else 0
c,o = divmod(lv1+lv2+c,10)
result_tail.next = ListNode(o)
result_tail = result_tail.next
l1 = (l1.next if l1 else None)
l2 = (l2.next if l2 else None)
return result.next
O(n)
Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head:
return head
odd = head # Both of them point at the first node of the target linked list
even = head.next # doesn't matter even there's only one node in the linked list (even will become None)
eHead = even # We have to keep where the even-node list starts
while even and even.next: # won't get in the loop at first if there's only one node in the linked list
# both even and even.next are necessary condition because even might point to None, which has no attribute 'next'
# AND, why these two, small discussion by myself as below
odd.next = odd.next.next
even.next = even.next.next
# After these two ops, odd/even still points at its original place
# Therefore, we move them to the next node repectively
odd = odd.next
even = even.next
odd.next = eHead # the odd pointer currently points at the last node of the odd-node list
return head # We keep the start of the odd-node list in the first of our code
time O(n) space O(1)
Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
# Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ta = headA
tb = headB
al = bl = 0
while ta:
al += 1
ta = ta.next
while tb:
bl += 1
tb = tb.next
ta = headA
tb = headB
if al > bl:
t = al - bl
while t:
ta = ta.next
t -= 1
elif bl > al:
t = bl - al
while t:
tb = tb.next
t -= 1
while ta and tb:
if ta == tb:
return ta
ta = ta.next
tb = tb.next
return None
O(m+n)
O(1)
Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Follow up: Recursive solution is trivial, could you do it iteratively?
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# recursively
def rinorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
#iterative
def inorderTraversal(self, root: TreeNode) -> List[int]:
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
if not root: return []
res, temp, stack, flag=[], [], [root], 1
while stack:
for i in xrange(len(stack)):
node=stack.pop(0)
temp+=[node.val]
if node.left: stack+=[node.left]
if node.right: stack+=[node.right]
res+=[temp[::flag]]
temp=[]
flag*=-1
return res
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans = []
stack = []
queue = []
queue.append(root)
while queue:
t = []
while queue:
i = queue.pop()
t.append(i.val)
if i.left:
stack.append(i.left)
if i.right:
stack.append(i.right)
if t:
ans.append(t)
t = []
while stack:
i = stack.pop()
if i.right:
queue.append(i.right)
if i.left:
queue.append(i.left)
t.append(i.val)
if t:
ans.append(t)
return ans
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if inorder:
i = inorder.index(preorder.pop(0))
root = TreeNode(inorder[i])
root.left = self.buildTree(preorder, inorder[0:i])
root.right = self.buildTree(preorder, inorder[i+1:])
return rootPopulating Next Right Pointers in Each Node
Solution
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Since we are manipulating tree nodes on the same level, it’s easy to come up with
a very standard BFS solution using queue. But because of next pointer, we actually
don’t need a queue to store the order of tree nodes at each level, we just use a next
pointer like it’s a link list at each level; In addition, we can borrow the idea used in
the Binary Tree level order traversal problem, which use cur and next pointer to store
first node at each level; we exchange cur and next every time when cur is the last node
at each level.
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
cur = root
next = root.left
while cur.left :
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
else:
cur = next
next = cur.left
return root
Kth Smallest Element in a BST
Solution
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Example 1:
Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
Time complexity: \mathcal{O}(H + k)O(H+k), where HH is a tree height. This complexity is defined by the stack, which contains at least H + kH+k elements, since before starting to pop out one has to go down to a leaf. This results in \mathcal{O}(\log N + k)O(logN+k) for the balanced tree and \mathcal{O}(N + k)O(N+k) for completely unbalanced tree with all the nodes in the left subtree.
Space complexity: \mathcal{O}(H)O(H) to keep the stack, where HH is a tree height. That makes \mathcal{O}(N)O(N) in the worst case of the skewed tree, and \mathcal{O}(\log N)O(logN) in the average case of the balanced tree.
