Important Questions/Algos Flashcards
Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length. Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:
If S[i] == “I”, then A[i] < A[i+1]
If S[i] == “D”, then A[i] > A[i+1]
Example 1:
Input: “IDID”
Output: [0,4,1,3,2]
def diStringMatch(self, S: str) -> List[int]:
left = right = 0
res = [0]
for i in S:
if i == "I":
right += 1
res.append(right)
else:
left -= 1
res.append(left)
return [i - left for i in res]
You have to try the solution on notebook to understand.
This solution takes high low unlike to other one. The other one goes into negative and then deals with it.
high = len(S)
low = 0
res = []
for i in S:
if i=='I':
res.append(low)
low+=1
else:
res.append(high)
high-=1
res.append(low)
return res
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
# s = set()
# for i in range(len(nums)):
# t = target - nums[i]
# if t in s:
# return [i,nums.index(t)]
# else:
# s.add(nums[i])
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
Given two arrays A and B, the elements of B are distinct, and all elements in B are also in A.
Sort the elements of A such that the relative ordering of items in A are the same as in B. Elements that don’t appear in B should be placed at the end of A in ascending order.
Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
def relativeSortArray(self, A, B):
k = {b: i for i, b in enumerate(B)}
return sorted(A, key=lambda a: k.get(a, 1000 + a))
Every element in B is less than or equal to 1000. This solution uses a genius trick. The get command returns the index stored in dict k iff a exists in it as a key. If a doesn't exist in k, then it returns the default value(default of get function) i.e 1000+a. Now we are sorting as per B which is stored in k as num:index pairs.
So first priority is given to this k. But on second priority, we want basic ascending order. And that second priority is done as 1001,1002,1003....
Let us take an example that a =3,4 both are not in k. Then they will be sorted based on the priority 1003 and 1004. Clearly 1003 is smaller and it will be gain lower sort priority while sorting. It is a complex but very important trick.
1-liner
def relativeSortArray(self, A, B):
return sorted(A, key=(B + sorted(A)).index)
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Input: words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
Output: 6
Explanation:
The strings that can be formed are “cat” and “hat” so the answer is 3 + 3 = 6.
def countCharacters(self, words: List[str], c: str) -> int:
out,char_counter = 0,collections.Counter(c)
for word in words:
word_counter = collections.Counter(word)
included = True
for letter in word_counter:
if word_counter[letter]>char_counter[letter]:
included = False
break
if included:
out = out+len(word)
return out
Note that counter is faster than loops! Hence above approach preferred than making a list of chars and removing elements from it if there’s a match. Since counter works as a hash map, so its faster and should be used.
.Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer. You may return the answer in any order. Example 1: Input: ["bella","label","roller"] Output: ["e","l","l"]
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
a = collections.Counter(A[0])
print(a)
for word in A[1:]:
b = collections.Counter(word)
for i in a:
a[i] = min(a[i],b[i])
print(a)
return a.elements()Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.
Note that elements beyond the length of the original array are not written.
Do the above modifications to the input array in place, do not return anything from your function.
Example 1:
Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
shift = 0
l = len(arr)
for i in range(l):
if arr[i] == 0:
shift += 1
for i in range(l-1, -1, -1):
# put the shifted number in the right spot
if i + shift < l:
arr[i+shift] = arr[i]
# This happens every time
# if we meet a 0, we need to duplicate 0, we do
# this in the same run i.e. both if statements run
if arr[i] == 0:
shift -= 1
if i + shift < l:
arr[i+shift] = 0On a N * N grid, we place some 1 * 1 * 1 cubes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).
Return the total surface area of the resulting shapes. Example 1: Input: [[2]] Output: 10 Example 2: Input: [[1,2],[3,4]] Output: 34 Draw it to understand, then solve. This solution is very very important to understand how to use multiple ifs (not elifs) and how to do things column wise and row wise i.e. how to let columns take care of themselves and rows take care of themselves instead of making the cube take care of all its sides.
n, res = len(grid), 0
for i in range(n):
for j in range(n):
if grid[i][j]:
print(grid[i][j])
res += 2 + grid[i][j] * 4
# This includes all surfaces except the ones in between # the cubes in a single tower
if i:
print(grid[i][j])
res -= min(grid[i][j], grid[i - 1][j]) * 2
# This cares only about the previous tower in a row-wise
# manner i.e. only one side of the tower(west)
if j:
print(grid[i][j])
res -= min(grid[i][j], grid[i][j - 1]) * 2
# This cares only about the previous tower in a column-# wise manner i.e. only one side of the tower(south)
return res
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
for i in range(len(nums)):
x = abs(nums[i])
nums[x-1] = -1*abs(nums[x-1])
return [i+1 for i in range(len(nums)) if nums[i]>0]
Here we pick each number of the array, then we put a minus sign in front of the number represented by our number as index i.e. index=num-1. This way all numbers in array will become negative except for the numbers at the indexes which don’t exist in array.
In given example [4,3,2,7,8,2,3,1], number 5 and 6 don’t exist, hence the index = 5-1 and index = 6-1 i.e the numbers 8 and 2 won’t become negative since no number points to them as index.
We get [-4,-3,-2,-7, 8, 2,-3,-1] after marking.
Given a column title as appear in an Excel sheet, return its corresponding column number. Input: "A" Output: 1 Input: "AB" Output: 28 Input: "ZY" Output: 701
s = list(s)
mul = len(s)-1
result = 0
for letter in s:
result += (ord(letter)-64)*(26**mul)
mul -= 1
return result
**Very important to learn property of dicts and how to replace a counter.
Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
first,count,result,degree = {},{},0,0
for i,num in enumerate(nums):
first.setdefault(num,i)
count[num] = count.get(num,0)+1
if count[num]>degree:
degree = count[num]
result = i-first[num]+1
elif count[num]==degree:
result = min(result,i-first[num]+1)
return resultSay you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
if not prices:
return 0
max_profit, min_price = 0, float('inf')
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
On an 8x8 chessboard, there can be multiple Black Queens and one White King.
Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.
def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
seen, ans = set(map(tuple,queens)), []
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
r, c = king
if dr or dc:
while 0 <= r < 8 > c >= 0:
r += dr
c += dc
if (r, c) in seen:
ans += [[r, c]]
break
return ans
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
Example 1:
Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
ans = 0
while head:
ans = (ans << 1) | head.val
head = head.next
return ans
OR
out = 0
while head:
out = 2*out + head.val
head = head.next
return out
Reveal Cards In Increasing Order
Input: [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation:
We get the deck in the order [17,13,11,2,3,5,7] (this order doesn’t matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom. The deck is now [13,17].
We reveal 13, and move 17 to the bottom. The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.
N = len(deck)
index = collections.deque(range(N))
ans = [None]*N
for card in sorted(deck):
ans[index.popleft()] = card
if index:
index.append(index.popleft())
return ans
# d = collections.deque()
# for x in sorted(deck)[::-1]:
# d.rotate()
# d.appendleft(x)
# return list(d)
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
res = 0
for num in nums:
res ^= num
return res
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
Examples:
Input: S = “a1b2”
Output: [“a1b2”, “a1B2”, “A1b2”, “A1B2”]
res = [’’]
for ch in S:
if ch.isalpha():
res = [i+j for i in res for j in [ch.upper(), ch.lower()]]
else:
res = [i+ch for i in res]
return res
Sieve of Eratosthenes
def SieveOfEratosthenes(n):
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
if (prime[p] == True):
for i in range(p * p, n+1, p):
prime[i] = False
p += 1
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Input: “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
First, I count the number of 1 or 0 grouped consecutively.
For example “0110001111” will be [1, 2, 3, 4].
Second, for any possible substrings with 1 and 0 grouped consecutively, the number of valid substring will be the minimum number of 0 and 1.
For example “0001111”, will be min(3, 4) = 3, (“01”, “0011”, “000111”)
s = [len(i) for i in s.replace(‘01’, ‘0 1’).replace(‘10’, ‘1 0’).split()]
return sum(min(a, b) for a, b in zip(s, s[1:]))
Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
Example 1:
Input: S = “ab#c”, T = “ad#c”
Output: true
Explanation: Both S and T become “ac”.
first = self.build_str(S)
second = self.build_str(T)
return first == second
def build_str(self, S):
stack = []
for char in S:
if char != "#":
stack.append(char)
else:
if stack:
stack.pop()
return "".join(stack)
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
def convert(c):
return ord(c)-ord('0')
x1=x2=0
for i in num1:
x1=x1*10+ convert(i)
for j in num2:
x2=x2*10+convert(j)
x=x1+x2
return str(x)Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: “abab”
Output: True
Explanation: It’s the substring “ab” twice.
for i in xrange(len(s)/2):
if s[:i+1]*(len(s)/(i+1)) == s:
return True
return False
https://leetcode.com/problems/repeated-substring-pattern/discuss/94334/Easy-python-solution-with-explaination
return s in (s+s)[1:-1]
Given an array of characters, compress it in-place.
The length after compression must always be smaller than or equal to the original array.
Every element of the array should be a character (not int) of length 1.
After you are done modifying the input array in-place, return the new length of the array.
Could you solve it using only O(1) extra space?
Example 1:
Input:
[“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output:
Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
walker, runner = 0, 0
while runner < len(chars):
chars[walker] = chars[runner]
count = 1
while runner + 1 < len(chars) and chars[runner] == chars[runner+1]:
runner += 1
count += 1
if count > 1:
for c in str(count):
chars[walker+1] = c
walker += 1
runner += 1
walker += 1
return walker
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: [“flower”,”flow”,”flight”]
Output: “fl”
if not s:
return ""
shortest = min(s,key=len)
for i,x in enumerate(shortest):
for z in s:
if not x==z[i]:
return shortest[:i]
return shortestGiven a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
def is_square(N):
return int(N**.5)**2 == N
return any(is_square(c - a*a)
for a in range(int(c**.5) + 1))
sq = set()
count = int(math.sqrt(c))
# use (count + 1) because first index is 0
for i in range(count + 1):
sq.add(i ** 2)
for n in sq:
if c - n in sq:
return True
return False
Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + … + P_k, where P_i are primitive valid parentheses strings.
Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.
Input: “(()())(())”
Output: “()()()”
Explanation:
The input string is “(()())(())”, with primitive decomposition “(()())” + “(())”.
count,out = 0, []
for i in list(S):
if i==')':
count-=1
if count!=0:
out.append(i)
if i=='(':
count+=1
return ''.join(out)
This Question teaches you that where you write the line in code can make a huge difference. Here count line is in middle, if you change it to top or bottom, the code will break.We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.
Input:
[“900 google.mail.com”, “50 yahoo.com”, “1 intel.mail.com”, “5 wiki.org”]
Output:
[“901 mail.com”,”50 yahoo.com”,”900 google.mail.com”,”5 wiki.org”,”5 org”,”1 intel.mail.com”,”951 com”]
Explanation:
We will visit “google.mail.com” 900 times, “yahoo.com” 50 times, “intel.mail.com” once and “wiki.org” 5 times. For the subdomains, we will visit “mail.com” 900 + 1 = 901 times, “com” 900 + 50 + 1 = 951 times, and “org” 5 times.
counter = collections.Counter()
for cpdomain in cpdomains:
count, *domains = cpdomain.replace(“ “,”.”).split(“.”)
for i in range(len(domains)):
counter[”.”.join(domains[i:])] += int(count)
return [” “.join((str(v), k)) for k, v in counter.items()]
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
# out = []
# d = {}
# for i in range(len(nums2)-1):
# for j in range(i+1,len(nums2)):
# if nums2[j]>nums2[i]:
# d[nums2[i]] = nums2[j]
# break
# print(d)
# for i in nums1:
# out.append(d.get(i,-1))
# return out
greater,stack = {},[]
for n in nums:
while stack and n > stack[-1]:
greater[stack.pop()] = n
stack.append(n)
return [greater[n] if n in greater else -1 for n in findNums]
Note that using stack here decreases the number of times the loop j runs in above code, hence making it faster. It is a very new and important concept!N-ary tree traversal (recursive)
The recursive solution can be made a bit simpler by using the yield and yield from keywords in Python 3.
def traverse_in_postorder(tree):
if tree:
for child in tree.children:
yield from traverse_in_postorder(child)
yield tree.val
To conform with the problem requirement of returning a list, just do list(traverse_in_postorder(root)).
Merge two binary trees using iteration(Stack)
https://leetcode.com/problems/merge-two-binary-trees/solution/
Visit the above for visualisation!
if t1 is None:
return t2
stack = []
stack.append((t1,t2))
while stack:
t = stack.pop()
if t[1] is None:
continue
t[0].val += t[1].val
if t[0].left is None:
t[0].left = t[1].left
else:
stack.append((t[0].left,t[1].left))
if t[0].right is None:
t[0].right = t[1].right
else:
stack.append((t[0].right,t[1].right))
return t1
- Shortest Distance to a Character
Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.
Example 1:
Input: S = “loveleetcode”, C = ‘e’
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
https: //leetcode.com/problems/shortest-distance-to-a-character/discuss/324885/python-easy-‘two-passes’-solution
https: //leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/C%2B%2BJavaPython-2-Pass-with-Explanation
Kinda DP:
def shortestToChar(self, S, C):
n = len(S)
res = [0 if c == C else n for c in S]
for i in range(1, n):
res[i] = min(res[i], res[i - 1] + 1)
for i in range(n - 2, -1, -1):
res[i] = min(res[i], res[i + 1] + 1)
return res
TWO PASS:
indc, dis = float('-inf'), [0] * len(S)
for i in range(len(S)):
if S[i] == C:
indc = i
dis[i] = i - indc
indc = float('inf')
for j in range(len(dis))[::-1]:
if S[j] == C:
indc = j
dis[j] = min(dis[j], indc-j)
return dis
MERGING TWO for STATEMENTS:
def shortestToChar(self, S, C):
n, pos = len(S), -float('inf')
res = [n] * n
for i in list(range(n)) + list(range(n)[::-1]):
if S[i] == C:
pos = i
res[i] = min(res[i], abs(i - pos))
return res
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
costs.sort(key=lambda cost: cost[0] - cost[1])
costs_for_A = sum([cost[0] for cost in costs[:len(costs) // 2]])
costs_for_B = sum([cost[1] for cost in costs[len(costs) // 2:]])
return costs_for_A + costs_for_B
https://leetcode.com/problems/two-city-scheduling/discuss/300784/4-lines-of-Python-with-explanation
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
if not q and not p:
return True
elif not p or not q:
return False
elif p.val!=q.val:
return False
else:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)Find the sum of all left leaves in a given binary tree.
The secsy solution:
if not root: return 0
if root.left and not root.left.left and not root.left.right:
return root.left.val + self.sumOfLeftLeaves(root.right)
return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
My solution:
# def helper(root):
# if root:
# left = helper(root.left)
# if left and (left.left==left.right):
# self.s+=left.val
# helper(root.right)
# return root
# helper(root)
# return self.s
We are given two strings, A and B.
A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = ‘abcde’, then it will be ‘bcdea’ after one shift on A. Return True if and only if A can become B after some number of shifts on A.
Example 1:
Input: A = ‘abcde’, B = ‘cdeab’
Output: true
Example 2:
Input: A = ‘abcde’, B = ‘abced’
Output: false
return len(A) == len(B) and B in A + A
In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.
nodes = collections.defaultdict(list)
queue = [(root,0,0)]
while queue:
node,level,parent = queue.pop(0)
nodes[node.val] = [level,parent]
if node.left:
queue.append((node.left,level+1,node.val))
if node.right:
queue.append((node.right,level+1,node.val))
if nodes[x][0]==nodes[y][0] and nodes[x][1]!=nodes[y][1]:
return True
return False
You can also use a For loop for same levels but this method is more interesting!
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
# if not root: # return [] # res = collections.defaultdict(list) # q = [[root,0]]
# while q:
# node,level = q.pop(0)
# res[level].append(node.val)
# if node.left:
# q.append([node.left,level+1])
# if node.right:
# q.append([node.right,level+1])
# m = max(res)
# out = []
# for i in range(m,-1,-1):
# out.append(res[i])
# return out
Interesting solution: look at res[-] minus thing:
res = []
self.dfs(root, 0, res)
return res
def dfs(self, root, level, res):
if root:
if len(res) < level + 1:
res.insert(0, [])
res[-(level+1)].append(root.val)
print(res)
self.dfs(root.left, level+1, res)
self.dfs(root.right, level+1, res)
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].The hard way: DFS :)
info = []
def dfs(node, depth = 0):
if node:
if len(info) <= depth:
info.append([0, 0])
info[depth][0] += node.val
info[depth][1] += 1
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root)
return [s/float(c) for s, c in info] https://leetcode.com/problems/average-of-levels-in-binary-tree/
Subtree of Another Tree
def isMatch(self, s, t):
if not(s and t):
return s is t
return (s.val == t.val and
self.isMatch(s.left, t.left) and
self.isMatch(s.right, t.right))
def isSubtree(self, s, t):
if self.isMatch(s, t): return True
if not s: return False
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
6
/ \
3 5
\ /
2 0
\
1
def constructMaximumBinaryTree(self, nums):
if not nums:
return
if len(nums) == 1:
return TreeNode(nums[0])
pivot = max(nums)
idx = nums.index(pivot)
ret = TreeNode(pivot)
ret.left = self.constructMaximumBinaryTree(nums[:idx])
ret.right = self.constructMaximumBinaryTree(nums[idx+1:])
return ret
Tricky Solution:
if not nums:
return None
stk = []
last = None
for num in nums:
while stk and stk[-1].val < num:
last = stk.pop()
node = TreeNode(num)
if stk:
stk[-1].right = node
if last:
node.left = last
stk.append(node)
last = None
return stk[0]
https://leetcode.com/problems/maximum-binary-tree/
Sort a matrix diagonally!
n, m = len(mat), len(mat[0])
d = collections.defaultdict(list)
for i in range(n):
for j in range(m):
d[i-j].append(mat[i][j])
for k in d:
d[k].sort(reverse = True)
for i in range(n):
for j in range(m):
mat[i][j] = d[i-j].pop()
return mat
- Construct Binary Search Tree from Preorder Traversal
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Easy n(log(n)) solution:
# def helper(i,j):
# if i==j: return None
# root = TreeNode(A[i])
# mid = bisect.bisect(A,A[i],i+1,j)
# print(mid)
# root.left = helper(i+1,mid)
# root.right = helper(mid,j)
# return root
# return helper(0,len(A))
O(n) solution: complex
i = 0
def bstFromPreorder(self, A: List[int],bound=float(‘inf’)) -> TreeNode:
if self.i == len(A) or A[self.i] > bound:
return None
print(A[self.i],bound)
root = TreeNode(A[self.i])
self.i += 1
root.left = self.bstFromPreorder(A, root.val)
root.right = self.bstFromPreorder(A, bound)
return root
You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.
Backtracking:DFS!
Example 1:
Input: “AAB”
Output: 8
Explanation: The possible sequences are “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”.
res = set()
def dfs(path, t):
if path not in res:
res.add(path)
for i in range(len(t)):
dfs(path+t[i], t[:i] + t[i+1:])
dfs('', tiles)
return len(res)-1
- All Possible Full Binary Trees
A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.
Each node of each tree in the answer must have node.val = 0.
You may return the final list of trees in any order.
def allPossibleFBT(self, N: int ) -> List[TreeNode]:
N -= 1
if N == 0: return [TreeNode(0)]
ret = []
for l in range(1, N, 2):
print('l:',l)
for left in self.allPossibleFBT(l):
print('left:',left)
for right in self.allPossibleFBT(N - l):
print('right:',right)
root = TreeNode(0)
root.left = left
root.right = right
ret += [root]
return ret
Cleaner:
if N == 1: return [TreeNode(0)]
if N & 1 == 0: return []
ans = []
for i in range(1, N, 2):
for left in self.allPossibleFBT(i):
for right in self.allPossibleFBT(N-i-1):
ans.append(TreeNode(0, left, right))
return ans
- The k-th Lexicographical String of All Happy Strings of Length n
A happy string is a string that:
consists only of letters of the set [‘a’, ‘b’, ‘c’].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).
For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
Example 1:
Input: n = 1, k = 3
Output: “c”
Explanation: The list [“a”, “b”, “c”] contains all happy strings of length 1. The third string is “c”.
Example 3:
Input: n = 3, k = 9
Output: “cab”
Explanation: There are 12 different happy string of length 3 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]. You will find the 9th string = “cab”
nextLetter = {‘a’: ‘bc’, ‘b’: ‘ac’, ‘c’: ‘ab’}
q = collections.deque([‘a’, ‘b’, ‘c’])
while len(q[0]) != n:
u = q.popleft()
for v in nextLetter[u[-1]]:
q.append(u + v)
return q[k - 1] if len(q) >= k else ‘’
BRUTE FORCE:
def getHappyString(self, n: int, k: int) -> str:
result = self.listCombinations(n, ‘’)
if k > len(result):
return ‘’
return ‘‘.join(result[k-1])
def listCombinations(self, n, ignoreLetter):
if n == 0:
return [[]]
allLetters = 'abc'
result = []
for letter in allLetters:
if letter == ignoreLetter:
continue
result.extend(map(lambda x: [letter] + x, self.listCombinations(n-1, letter)))
print(result)
return result
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
res, lo = [[nn]], nn
while lo > 1:
lo, hi = lo - len(res), lo
res = [[i for i in range(lo, hi)]] + [list(j) for j in zip(*res[::-1])]
return res
https://leetcode.com/problems/spiral-matrix-ii/discuss/22282/4-9-lines-Python-solutions
A = [[0] * n for _ in range(n)]
i, j, di, dj = 0, 0, 0, 1
for k in range(n*n):
A[i][j] = k + 1
if A[(i+di)%n][(j+dj)%n]:
print(i,j,di,dj)
di, dj = dj, -di
i += di
j += dj
print(A)
return A
Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
res = [0] * (n+1)
res[0] = 1
print(res)
for i in range(1, n+1):
for j in range(i):
res[i] += res[j] * res[i-1-j]
print(res)
return res[n]Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Counter: Count '1's at every bit position
res = 0
for i in range(32):
cnt = 0
for j in range(len(nums)):
n = nums[j]
cnt += n>>i & 1
if cnt % 3:
res = res | 1<<i></i>
