Own Daily Challenge Flashcards
Sort Integers by The Number of 1 Bits
You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.
Return the array after sorting it.
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]
class Solution:
def sortByBits(self, arr: List[int]) -> List[int]:
def customSortKey(num):
count = bin(num).count("1")
return (count, num)
arr.sort(key = customSortKey)
return arrLowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
if root == p or root == q:
return root
#Potential ancestor anchors
leftNode = self.lowestCommonAncestor(root.left, p, q)
rightNode = self.lowestCommonAncestor(root.right, p, q)
if leftNode and rightNode:
return root
#Both on same side. Whatever one we found first (the one that fired the root == p or root = q condition first) is the ancestor
if leftNode:
return leftNode
if rightNode:
return rightNode
#O(n) #NOT O(H) because that is for BST. You can make determination of going left vs right. In binary tree case, need to go everywhere.
#O(h)
Maximum Product of Two Elements in an Array
Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)(nums[j]-1).
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 34 = 12.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
#Track two biggest values
biggest, secondBiggest = 0, 0
for n in nums:
if n > biggest:
secondBiggest = biggest
biggest = n
else:
#If not greater than biggest, at least it can be second biggest still.
secondBiggest = max(secondBiggest, n)
return (biggest - 1) * (secondBiggest - 1)
#O(n)
#O(1)Maximum Difference Between Node and Ancestor
Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
res = 0
def dfs(root, curMin, curMax):
nonlocal res
if not root:
return
#The idea is that we want to compare the current root node (child) to a previous ancestor.
#We check both combinations.. smallest ancestor - root.val, biggest ancestor - root.val
#On first execution, res is 0 since root.
#On subsequent iterations, minAncestor and maxAncestor will change as we move on to subsequent children deeper.
res = max(res, abs(curMax - root.val), abs(curMin - root.val))
dfs(root.left, min(curMin, root.val), max(curMax, root.val))
dfs(root.right, min(curMin, root.val), max(curMax, root.val))
dfs(root, root.val, root.val)
return res
#O(n)
#O(h)
Leaf-Similar Trees
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def dfs(root, res):
if not root:
return
if not root.left and not root.right:
res.append(root.val)
return
dfs(root.left, res)
dfs(root.right, res)
res1 = []
res2 = []
dfs(root1, res1)
dfs(root2, res2)
return res1 == res2
#O(n)
#O(n)
Determine if String Halves Are Alike
You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.
Two strings are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Notice that s contains uppercase and lowercase letters.
Return true if a and b are alike. Otherwise, return false.
Input: s = “textbook”
Output: false
Explanation: a = “text” and b = “book”. a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.
class Solution:
def halvesAreAlike(self, s: str) -> bool:
vowels = set(["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"])
i, j = 0, len(s) // 2
s1Count, s2Count = 0, 0
#Even length!
while j < len(s):
c1, c2 = s[i], s[j]
if c1 in vowels:
s1Count += 1
if c2 in vowels:
s2Count += 1
i += 1
j += 1
return s1Count == s2Count
#O(n)
#O(1) #for vowels. 2 pointers avoids the string creationsUnique Number of Occurrences
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
counts = Counter(arr)
return len(set(counts.values())) == len(counts.keys())
#O(n)
#O(n)Set Mismatch
You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
You are given an integer array nums representing the data status of this set after the error.
Find the number that occurs twice and the number that is missing and return them in the form of an array.
Input: nums = [1,2,2,4]
Output: [2,3]
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
counts = Counter(nums)
missing, dupe = -1, -1
n = len(nums)
for i in range(1, n + 1):
if i not in counts:
missing = i
elif counts[i] == 2:
dupe = i
return [dupe, missing]
#O(n)
#O(n)
Maximum Length of a Concatenated String with Unique Characters
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Input: arr = [“un”,”iq”,”ue”]
Output: 4
Explanation: All the valid concatenations are:
- “”
- “un”
- “iq”
- “ue”
- “uniq” (“un” + “iq”)
- “ique” (“iq” + “ue”)
Maximum length is 4.
Example 2:
class Solution:
def maxLength(self, arr: List[str]) -> int:
charSet = set()
res = 0
def overlap(charSet, s):
prev = set()
for c in s:
if c in charSet or c in prev:
return True
prev.add(c)
return False
def dfs(i):
nonlocal res
if i == len(arr):
res = max(res, len(charSet))
return
#include i
if not overlap(charSet, arr[i]):
curS = arr[i]
for c in curS:
charSet.add(c)
dfs(i + 1)
for c in curS:
charSet.remove(c)
#Don't include i
dfs(i + 1)
dfs(0)
return res
#O(2 ^ n * m) #number of words, m avg length of word.
#O(nm) #number of words is the height. each avg length of m added to charSet.
Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Notes:
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.
Input
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
class MyQueue:
def \_\_init\_\_(self):
self.s1 = []
self.s2 = [] #represents the actual queue basically
def push(self, x: int) -> None:
self.s1.append(x)
def pop(self) -> int:
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self) -> int:
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self) -> bool:
return not self.s1 and not self.s2
#O(1) per operation basically. If have to take O(N) operation due to s2 empty, then we do that. But since there are N elements an 2N operations (each elt pushed popped once), amortized O(1) per op
#O(n) space for two stacks
Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()Flood Fill
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.
You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.
Return the modified image after performing the flood fill.
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
ROWS, COLS = len(image), len(image[0])
visit = set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
startingColor = image[sr][sc]
def dfs(r, c):
if r < 0 or r == ROWS or c < 0 or c == COLS or image[r][c] != startingColor or (r, c) in visit:
return
visit.add((r, c))
image[r][c] = color
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
dfs(neiR, neiC)
dfs(sr, sc)
return image
#O(mn)
#O(mn)
Divide Array Into Arrays With Max Difference
You are given an integer array nums of size n and a positive integer k.
Divide the array into one or more arrays of size 3 satisfying the following conditions:
Each element of nums should be in exactly one array.
The difference between any two elements in one array is less than or equal to k.
Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.
Input: nums = [1,3,4,8,7,9,3,5,1], k = 2
Output: [[1,1,3],[3,4,5],[7,8,9]]
Explanation: We can divide the array into the following arrays: [1,1,3], [3,4,5] and [7,8,9].
The difference between any two elements in each array is less than or equal to 2.
Note that the order of elements is not important.
class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
nums.sort()
res = []
for i in range(0, len(nums), 3):
if nums[i + 2] - nums[i] <= k:
res.append(nums[i: i + 3])
else:
return []
return res
#O(n log n)
#O(n) for resCount Nodes Equal to Average of Subtree
Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.
Note:
The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
A subtree of root is a tree consisting of root and all of its descendants.
Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation:
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.
# 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 averageOfSubtree(self, root: TreeNode) -> int:
res = 0
#returns the sum, and num nodes in subtree
def dfs(root):
nonlocal res
if not root:
return 0, 0
#if leaf
if not root.left and not root.right:
res += 1
return root.val, 1
leftSum, leftCount = dfs(root.left)
rightSum, rightCount = dfs(root.right)
totalCount = leftCount + rightCount + 1
totalSum = leftSum + rightSum + root.val
avg = totalSum // totalCount
if avg == root.val:
res += 1
return totalSum, totalCount
dfs(root)
return res
#O(n)
#O(h)
Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1’s in the array.
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
l = 0
res = 0
for r in range(len(nums)):
if nums[r] == 0:
l = r + 1
else:
res = max(res, r - l + 1)
return res
#O(n)
#O(1)
Sort Characters By Frequency
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Example 1:
Input: s = “tree”
Output: “eert”
Explanation: ‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:
Input: s = “cccaaa”
Output: “aaaccc”
Explanation: Both ‘c’ and ‘a’ appear three times, so both “cccaaa” and “aaaccc” are valid answers.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:
Input: s = “Aabb”
Output: “bbAa”
Explanation: “bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.
class Solution:
def frequencySort(self, s: str) -> str:
# counts = Counter(s)
# maxHeap = [(-count, c) for c, count in counts.items()]
# heapq.heapify(maxHeap)
# res = []
# while maxHeap:
# count, c = heapq.heappop(maxHeap)
# res.append(c * -count)
# return "".join(res)
#O(n) + 26 log 26 for the heap
#O(n) for counter, then O(26) for heap
counts = Counter(s)
# freqs = [[] for i in range(len(s) + 1)]
buckets = defaultdict(list)
for c, count in counts.items():
buckets[count].append(c)
res = []
for i in range(len(s), -1, -1):
for c in buckets[i]:
res.append(i * c)
return "".join(res)
# #Bucket sort solution
# #O(n) for counter, then O(n) for actually finding and sorting decreasingly.
# #O(n) for the array. worst cases can be [[.........], [], [], []]
#Pretty much the same thing as the freqs thing you usually do.
