Array Hashing Flashcards
Merge Sorted Array
Solved
Easy
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Facebook 87
Amazon 41
Google 14
Microsoft 14
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
p1 = m-1
p2 = n-1
p = len(nums1) - 1
while(p>=0):
if(p2<0):
break
if(p1>=0 and nums1[p1] > nums2[p2]):
nums1[p] = nums1[p1]
p1-=1
else:
nums1[p] = nums2[p2]
p2-=1
p-=1- Group Anagrams
Medium
Companies
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”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
https://leetcode.com/problems/group-anagrams/description/
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
res[tuple(count)].append(s)
return res.values()
O(n), space: O(n*26)
If you want to save space in case words are smaller than 26 all the time and space is at a premium,
sort each string and use that as the key.
That changes the time to n(mLog(m)) where m is avg word length and n is number of entries. Space becomes m*n
- Top K Frequent Elements
Top K Frequent Elements
Solved
Medium
Topics
Companies
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Facebook
58
Amazon
20
https://leetcode.com/problems/top-k-frequent-elements/description/347
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == len(nums):
return nums
counts = Counter(nums)
return heapq.nlargest(k, counts.keys(), counts.get)
using quick select with count frequencies as key.
from collections import Counter
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
counts = Counter(nums)
unique = counts.keys()
def partition(l, r):
if l == r:
return l
pivot = unique[r]
store_idx = l
for i in range(l, r):
if counts[unique[i]] < counts[pivot]:
unique[i], unique[store_idx] = unique[store_idx], unique[i]
store_idx += 1
unique[r], unique[store_idx] = unique[store_idx], unique[r]
return store_idx
def quick_select(k):
k = len(unique) - k
l = 0
r = len(unique) - 1
piv_idx = partition(l, r)
while l < r:
if piv_idx == k:
return
elif piv_idx < k:
l = piv_idx + 1
piv_idx = partition(l, r)
else:
r = piv_idx - 1
piv_idx = partition(l, r)
quick_select(k)
n = len(unique)
return unique[n-k:]- Encode and Decode Strings
Solved
Medium
Topics
Companies
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vector<string> strs) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:
vector<string> decode(string s) {
//... your code
return strs;
}
So Machine 1 does:</string></string>
string encoded_string = encode(strs);
and Machine 2 does:
vector<string> strs2 = decode(encoded_string);
strs2 in Machine 2 should be the same as strs in Machine 1.</string>
Implement the encode and decode methods.
You are not allowed to solve the problem using any serialize methods (such as eval).
https://leetcode.com/problems/encode-and-decode-strings/
class Codec:
def encode(self, strs):
"""Encodes a list of strings to a single string.
:type strs: List[str]
:rtype: str
"""
sent = []
for str in strs:
str = str.replace("/", "//")
str = str.replace("$", "/$")
sent.append(str)
return "$".join(sent)
def decode(self, s):
"""Decodes a single string to a list of strings.
:type s: str
:rtype: List[str]
"""
out = []
i = 0
word = ""
while i < len(s):
if s[i] == "/":
i += 1
elif s[i] == "$":
out.append(word)
word = ""
i += 1
word += s[i]
i += 1
out.append(word)
return out- Product of Array Except Self
Solved
Medium
Topics
Companies
Hint
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
https://leetcode.com/problems/product-of-array-except-self/
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
out = [1] * len(nums)
prev = 1
for i in range(1, len(nums)):
out[i] = out[i-1] * nums[i-1]
suffix = 1
for i in range(len(nums)-1, -1, -1):
out[i] = suffix * out[i]
suffix = suffix * nums[i]
return out- Longest Consecutive Sequence
Medium
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
Amazon
17
Adobe
8
10 min hard cap, O(nLogn) solution.
https://leetcode.com/problems/longest-consecutive-sequence/description/
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
starts = set()
maxlen = 0
nums_set = set(nums)
for n in nums:
if n-1 not in nums_set:
starts.add(n)
for start in starts:
nxt = start
slen = 0
while nxt in nums_set:
slen +=1
nxt += 1
maxlen = max(maxlen, slen)
return maxlen
nLogn, O(n) space
- Remove Element
Easy
Companies
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
https://leetcode.com/problems/remove-element/description
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
insert = 0
idx = 0
while idx < len(nums):
if nums[idx] != val:
nums[idx], nums[insert] = nums[insert], nums[idx]
insert += 1
idx += 1
return insert- Remove Duplicates from Sorted Array
Easy
Companies
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = […]; // Input array
int[] expectedNums = […]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 1
for r in range(1, len(nums)):
if nums[r] != nums[r-1]:
nums[l] = nums[r]
l+= 1
return l- Remove Duplicates from Sorted Array II
Solved
Medium
Topics
Companies
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = […]; // Input array
int[] expectedNums = […]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description
Keep swapping elements with insert till their count is less than or equal to 2. Once a new element is encountered, count goes back to 1, thus swapping continues.
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
insert = 1
count = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
count += 1
else:
count = 1
if count <= 2:
nums[insert] = nums[i]
insert += 1
return insert
this works because if an element is moved to position 3 after checking if position 1 has the same element or not, it is guaranteed it won’t repeat more than 2 times..
<>,1, 1, 2
No matter what is at <> as long as it’s not 2, 2 can safely move one step left and it won’t repeat more than 2 times.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# Initialize an integer k that updates the kth index of the array...
# only when the current element does not match either of the two previous indexes. ...
insert = 0
# Traverse all elements through loop...
for cur_element in nums:
# If the index does not match elements, count that element and update it...
two_before_insert = insert - 2
if insert < 2 or cur_element != nums[two_before_insert]:
nums[insert] = cur_element
insert += 1
return insert
- Best Time to Buy and Sell Stock
Solved
Easy
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
pur = prices[0]
maxp = 0
for price in prices:
pur = min(pur, price)
profit = price - pur
maxp = max(maxp, profit)
return maxp- Best Time to Buy and Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150
Solved
Medium
Topics
Companies
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Each time price falls, reset buy and sell, add the current trade to profit.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
pur = 0
sell = 0
r = 0
maxp = 0
while r < len(prices) - 1:
# find valley first where price is lowest
while r < len(prices) - 1 and prices[r] >= prices[r+1]:
r += 1
pur = r
# find peak where price is highest after the valley of lowest price
while r < len(prices) - 1 and prices[r] < prices[r + 1]:
r += 1
sell = r
profit = prices[sell] - prices[pur]
maxp += profit
return maxp
doing multiple transactions for each high low combo, might not work if question mentions do it in lowest transactions eg transaction has a fee
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxprofit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
maxprofit += prices[i] - prices[i - 1]
return maxprofit
Another approach, monotonic increasing stack like.
# if we never hit a lower price before we finish, we do the final trade outside the loop.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
maxP = 0
dates = []
buy = prices[0]
sell = prices[0]
for i in range(1, len(prices)):
if prices[i] < sell:
maxP += (sell - buy)
buy = prices[i]
sell = prices[i]
else:
sell = prices[i]
if sell == prices[-1]:
maxP += (sell-buy)
return maxP
- Jump Game
Medium
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 105(
Amazon 18
https://leetcode.com/problems/jump-game/
going from front to end we keep updating maximum destination we can reach.
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
i = 0
if len(nums) == 1:
return True
maxdest = 0
for i in range(len(nums)):
if i + nums[i] >= maxdest:
maxdest = i + nums[i]
# we hit a zero thus cant move forward
if maxdest == i:
break
return maxdest >= len(nums) - 1
going from end to start we will keep updating last valid position (posToReach)
class Solution:
def canJump(self, nums: List[int]) -> bool:
finalPos = len(nums) - 1
if finalPos == 0:
return True
posToReach = finalPos
for i in range(finalPos, -1, -1):
stepsNeeded = posToReach - i
if nums[i] >= stepsNeeded:
posToReach = i
if posToReach == 0:
return True
return False
- Jump Game II
https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150
Solved
Medium
Topics
Companies
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n - 1].
https://leetcode.com/problems/jump-game-ii
builds on the jump 1 front to end solution, we keep track of current jump and when we hit it, we increment the counter to record we jumped.
class Solution(object):
def jump(self, nums):
answer = 0
maxjump = 0
prev_jump = 0
for i in range(len(nums) - 1):
jump = i + nums[i]
maxjump = max(jump, maxjump)
if i == prev_jump:
prev_jump = maxjump
answer += 1
return answer
- H-Index
Medium
Topics
Companies
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
Example 1:
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,3,1]
Output: 1
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
https://leetcode.com/problems/h-index/description
reverse sort and if citation is < paper count return paper count
from collections import defaultdict
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
sorted_citation = sorted(citations, reverse=True)
for i in range(len(citations)):
citation_count = sorted_citation[i]
paper_number = i+1
if (citation_count < paper_number):
return i
return paper_number
same as above but uses count sort with ceiling as len of array as the hidx can never be more than the count of all papers..
class Solution(object):
def hIndex(self, citations: List[int]) -> int:
count = [0] * (len(citations) + 1)
for c in citations:
idx = min(len(count)-1, c)
count[idx] += 1
total = 0
papers = 0
for idx in reversed(range(len(count))):
papers += count[idx]
if papers >= idx:
return idx
- Insert Delete GetRandom O(1)
https://leetcode.com/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150
Solved
Medium
Topics
Companies
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Example 1:
Input
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.
main logic here is that you can delete from array at last position in o(1)
so swap element to be deleted to last and pop it
from collections import defaultdict
from random import randrange
class RandomizedSet(object):
def \_\_init\_\_(self):
self.elements = set()
self.filled = []
self.filled_idx = defaultdict(int)
def insert(self, val):
"""
:type val: int
:rtype: bool
"""
present = val in self.elements
if not present:
self.filled.append(val)
self.elements.add(val)
self.filled_idx[val] = len(self.elements)-1
return not present
def remove(self, val):
"""
:type val: int
:rtype: bool
"""
present = val in self.elements
if present:
self.elements.remove(val)
remove_idx = self.filled_idx[val]
self.filled[remove_idx], self.filled[-1] = self.filled[-1], self.filled[remove_idx]
self.filled_idx[self.filled[remove_idx]] = remove_idx
self.filled.pop()
return present
def getRandom(self):
"""
:rtype: int
"""
randomIdx = randrange(0, len(self.filled))
return self.filled[randomIdx]
- Gas Station
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.
Constraints:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
https://leetcode.com/problems/gas-station/editorial/?envType=study-plan-v2&envId=top-interview-150
View a bunch of stops as segments, you set cur segment to zero if the segment’s gas gain drops to 0 because it means it is not as good starting point, so you start at the next gas station and check it
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total_gain = 0
current_gain = 0
start_idx = 0
for idx, (g, c) in enumerate(zip(gas,cost)):
total_gain += (g - c)
current_gain += (g - c)
if current_gain < 0:
current_gain = 0
start_idx = idx + 1
return start_idx if total_gain >= 0 else -1
- Candy
Solved
Hard
Topics
Companies
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
https://leetcode.com/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150
do a forward pass where you compare the left neighbor and then do a right pass where you compare the right neighbor and then for each individual select the maximum of the forward pass and the left pass.
class Solution(object):
def candy(self, ratings):
sum = 0
n = len(ratings)
left2right = [1] * n
right2left = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
left2right[i] = left2right[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
right2left[i] = right2left[i + 1] + 1
for i in range(n):
sum += max(left2right[i], right2left[i])
return sum
- Minimum Adjacent Swaps to Make a Valid Array
Solved
Medium
Topics
Companies: Amazon
Hint
You are given a 0-indexed integer array nums.
Swaps of adjacent elements are able to be performed on nums.
A valid array meets the following conditions:
The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.
Return the minimum swaps required to make nums a valid array.
Example 1:
Input: nums = [3,4,5,5,3,1]
Output: 6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum swaps required to make a valid array.
Example 2:
Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
https://leetcode.com/problems/minimum-adjacent-swaps-to-make-a-valid-array/description/
class Solution(object):
def minimumSwaps(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
minPos = len(nums) + 1
m_num = float(‘inf’)
maxPos = -1
mx_num = float(‘-inf’)
swaps = 0
for i in range(len(nums)):
if nums[i] < m_num:
minPos = i
m_num = nums[i]
if nums[i] >= mx_num:
maxPos = max(maxPos, i)
mx_num = nums[i]
adjustment = 0
if minPos > maxPos:
# they are on the other sides
adjustment = -1
swaps = minPos + ((len(nums) -1) - maxPos) + adjustment
return swaps
- Minimum Number of Keypresses
Solved
Medium
Topics
Companies
Hint
You have a keypad with 9 buttons, numbered from 1 to 9, each mapped to lowercase English letters. You can choose which characters each button is matched to as long as:
All 26 lowercase English letters are mapped to.
Each character is mapped to by exactly 1 button.
Each button maps to at most 3 characters.
To type the first character matched to a button, you press the button once. To type the second character, you press the button twice, and so on.
Given a string s, return the minimum number of keypresses needed to type s using your keypad.
Note that the characters mapped to by each button, and the order they are mapped in cannot be changed.
Example 1:
Input: s = “apple”
Output: 5
Explanation: One optimal way to setup your keypad is shown above.
Type ‘a’ by pressing button 1 once.
Type ‘p’ by pressing button 6 once.
Type ‘p’ by pressing button 6 once.
Type ‘l’ by pressing button 5 once.
Type ‘e’ by pressing button 3 once.
A total of 5 button presses are needed, so return 5.
Example 2:
Input: s = “abcdefghijkl”
Output: 15
Explanation: One optimal way to setup your keypad is shown above.
The letters ‘a’ to ‘i’ can each be typed by pressing a button once.
Type ‘j’ by pressing button 1 twice.
Type ‘k’ by pressing button 2 twice.
Type ‘l’ by pressing button 3 twice.
A total of 15 button presses are needed, so return 15.
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
https://leetcode.com/problems/minimum-number-of-keypresses/description/
from collections import Counter,defaultdict
class Solution(object):
def minimumKeypresses(self, s):
“””
:type s: str
:rtype: int
“””
scount = Counter(s)
heap = []
for key, value in scount.items():
heapq.heappush(heap, (-value, key))
keys = defaultdict(list)
charToKey = {}
idx = 0
keypress = 0
while heap:
_, char = heapq.heappop(heap)
number = (idx % 9 + 1)
idx += 1
keys[number].append(char)
charToKey[char] = number
for char in s:
keypress += (keys[charToKey[char]].index(char) + 1)
return keypress
This solution prevents the last index of by using an array to set the index of the ordinal as key pressed needed (basically every time we go above 9 keys, the order increases by 1
class Solution:
def minimumKeypresses(self, s: str) -> int:
cache = Counter(s)
vals = sorted(cache.items(), key=lambda x: -x[1])
ans = 0
r = key = 1
order = [0] * 26
for k, v in vals:
x = ord(k) - 97
if not order[x]:
order[x] = r
key += 1
if key == 10:
key = 1
r += 1
ans += order[x] * v
return ans
- Valid Word Abbreviation
Solved
Easy (Looks like a medium)
Companies: Facebook 2024
A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.
For example, a string such as “substitution” could be abbreviated as (but not limited to):
"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)
The following are not valid abbreviations:
"s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
"s010n" (has leading zeros)
"s0ubstitution" (replaces an empty substring)
Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Explanation: The word “internationalization” can be abbreviated as “i12iz4n” (“i nternational iz atio n”).
Example 2:
Input: word = “apple”, abbr = “a2e”
Output: false
Explanation: The word “apple” cannot be abbreviated as “a2e”.
Constraints:
1 <= word.length <= 20 word consists of only lowercase English letters. 1 <= abbr.length <= 10 abbr consists of lowercase English letters and digits. All the integers in abbr will fit in a 32-bit integer.
https://leetcode.com/problems/valid-word-abbreviation/description/
Keep two pointers, one i for the main word and j for the abbr
once you encounter a jump in abbr,
make the i pointer jump and then continue comparing chars at i and j.
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
i=0
j=0
while i < len(word) and j < len(abbr):
if abbr[j].isdigit():
if abbr[j] == '0':
return False
jump = ""
while j < len(abbr) and abbr[j].isdigit():
jump += abbr[j]
j+=1
jump = int(jump)
i = i + (jump)
continue
if word[i] != abbr[j]:
return False
i+=1
j+=1
if i == len(word) and j == len(abbr):
return True
else:
return False
- Dot Product of Two Sparse Vectors
Medium
Facebook
Given two sparse vectors, compute their dot product.
Implement class SparseVector:
SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.
Follow up: What if only one of the vectors is sparse?
Example 1:
Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 10 + 03 + 00 + 24 + 3*0 = 8
Example 2:
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 00 + 10 + 00 + 00 + 0*2 = 0
Example 3:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6
Constraints:
n == nums1.length == nums2.length 1 <= n <= 10^5 0 <= nums1[i], nums2[i] <= 100
O(n), O(n)
https://leetcode.com/problems/dot-product-of-two-sparse-vectors/description/
Store vectors as dictionary of keys format.
class SparseVector:
def \_\_init\_\_(self, nums: List[int]):
self.vec = self._to_sparse(nums)
def _to_sparse(self, vec: List[int]):
output = {}
for i, e in enumerate(vec):
if e != 0:
output[i] = e
return output
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
ret = 0
for idx, val in vec.vec.items():
if idx in self.vec:
ret += self.vec[idx] * val
return ret
Slight Optimization, iterate through smaller one
class SparseVector:
def \_\_init\_\_(self, nums: List[int]):
self.vec = self._to_sparse(nums)
def _to_sparse(self, vec: List[int]):
output = {}
for i, e in enumerate(vec):
if e != 0:
output[i] = e
return output
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
small = self.vec
large = vec.vec
if len(large) < len(small):
small = vec.vec
large = self.vec
ret = 0
for idx, val in small.items():
if idx in large:
ret += large[idx] * val
return ret
Less than 10 minutes. 7-8 minutes
O(n), O(n)
- Basic Calculator II
Medium/Hard
Companies: Facebook
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = “ 3/2 “
Output: 1
Example 3:
Input: s = “ 3+5 / 2 “
Output: 5
Constraints:
1 <= s.length <= 3 * 105
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.
Do it in O(1) space and O(n) time
https://leetcode.com/problems/basic-calculator-ii/description/
Evaluate previous operations each time you read a number. The s+='+0' is just a easy way to keep the solution clean. Because we are always looking one operation behind.
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
s = s.replace(' ', '')
def calc(s):
i = 0
cur_num = ''
op = '+'
res = 0
last_num = 0
s += '+0'
while i < len(s):
if s[i] in {'+', '-', '*', '/'}:
op = s[i]
i+=1
continue
elif s[i].isdigit():
while i < len(s) and s[i].isdigit():
cur_num += s[i]
i+=1
cur_num = int(cur_num)
if op == '-':
cur_num = -cur_num
res += last_num
last_num = cur_num
if op == '+':
res += last_num
last_num = cur_num
if op == '*':
last_num = last_num * cur_num
if op == '/':
last_num = int(last_num / (1.0 * cur_num))
cur_num = ''
return res
return calc(s)
Hard question, 20 mins assigned
O(n), space O(1)
- Basic Calculator
Hard
Companies DoorDash, Atlassian
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “1 + 1”
Output: 2
Example 2:
Input: s = “ 2-1 + 2 “
Output: 3
Example 3:
Input: s = “(1+(4+5+2)-3)+(6+8)”
Output: 23
Constraints:
1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.
Do it in O(n) space and time
https://leetcode.com/problems/basic-calculator/description/
When doing current_num we have 2 states:
1. If we have a number
2. If we have open parentheses.
If we have parentheses send idx+1 in to evaluate and once evaluated, return the index+1 and current result. That index will be used to continue evaluations in parent method.
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
def calc(s, i):
cur_num = ''
op = '+'
res = 0
while i < len(s):
if s[i] == ')':
return res, i+1
if s[i] in {'+', '-'}:
op = s[i]
i+=1
else:
if s[i].isdigit():
while i < len(s) and s[i].isdigit():
cur_num += s[i]
i+=1
cur_num = int(cur_num)
elif s[i] == '(':
cur_num, i = calc(s, i+1)
if op == '-':
cur_num = -cur_num
res += cur_num
cur_num = ''
return res
s = s.replace(' ', '')
return calc(s, 0)
- Basic Calculator III
Hard
Companies N/A
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, ‘+’, ‘-‘, ‘*’, ‘/’ operators, and open ‘(‘ and closing parentheses ‘)’. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “1+1”
Output: 2
Example 2:
Input: s = “6-4/2”
Output: 4
Example 3:
Input: s = “2(5+52)/3+(6/2+8)”
Output: 21
Constraints:
1 <= s <= 104
s consists of digits, '+', '-', '*', '/', '(', and ')'.
s is a valid expression.
Needs basic 1+2
https://leetcode.com/problems/basic-calculator-iii/description/
Building on Basic 1 and Basic 2 this is not too difficult but by itself, it might never be asked in interview as it will require a lot of time for someone who has never seen this before.
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
def calc(s, i):
cur_num = ''
last_num = 0
op = '+'
res = 0
while i < len(s):
if s[i] == ')':
return res+last_num, i+1
if s[i] in {'+', '-', '/', '*'}:
op = s[i]
i+=1
else:
if s[i].isdigit():
while i < len(s) and s[i].isdigit():
cur_num += s[i]
i+=1
cur_num = int(cur_num)
elif s[i] == '(':
cur_num, i = calc(s,i+1)
if op == '-':
cur_num = -cur_num
res += last_num
last_num = cur_num
if op == '+':
res += last_num
last_num = cur_num
if op == '/':
last_num = int(last_num / (1.0 * cur_num))
if op == '*':
last_num = last_num * cur_num
cur_num = ''
return last_num + res
s = s.replace(' ', '')
return calc(s, 0)
20 Minutes - Hard
O(n), O(n) space (recursion stack, each call is O(1) by itself)
- Custom Sort String
Medium
Companies: facebook 2024
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
Example 1:
Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation: “a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.
Example 2:
Input: order = “bcafg”, s = “abcd”
Output: “bcad”
Explanation: The characters “b”, “c”, and “a” from order dictate the order for the characters in s. The character “d” in s does not appear in order, so its position is flexible.
Following the order of appearance in order, “b”, “c”, and “a” from s should be arranged as “b”, “c”, “a”. “d” can be placed at any position since it’s not in order. The output “bcad” correctly follows this rule. Other arrangements like “bacd” or “bcda” would also be valid, as long as “b”, “c”, “a” maintain their order.
Constraints:
1 <= order.length <= 26 1 <= s.length <= 200 order and s consist of lowercase English letters. All the characters of order are unique.
10 mins alloted, 15 max
https://leetcode.com/problems/custom-sort-string/
nLog(n) answer (not optimal, interviewer will ask for optimal)
~~~
from collections import defaultdict
class Solution(object):
def customSortString(self, order, s):
“””
:type order: str
:type s: str
:rtype: str
“””
ranks = defaultdict(int)
ranks = {c: i+1 for i, c in enumerate(order)}
idx_s = map(lambda x: (ranks.get(x, 0), x), s)
sorted_s = sorted(idx_s)
return ““.join(map(lambda i: i[1], sorted_s))
~~~
Optimal O(n) Using count/bucket sorting / freq table.
Create a list of buckets with length one greater than the order (the extra is for elements without any order).
each time you encounter a character from s, find its rank and add it to it’s bucket.
After that go through the list of buckets and just create output string.
from collections import defaultdict
class Solution:
def customSortString(self, order: str, s: str) -> str:
rank_d = {c: i+1 for i, c in enumerate(order)}
freq_table = [[""] for _ in range(len(order)+1)]
for c in s:
freq_table[rank_d.get(c, 0)].append(c)
ret = []
for v in freq_table:
ret.extend(v)
return "".join(ret)
O(n) (optimal), O(n) space
- Interval List Intersections
Solved
Medium
Topics
Companies
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Constraints:
0 <= firstList.length, secondList.length <= 1000 firstList.length + secondList.length >= 1 0 <= starti < endi <= 109 endi < starti+1 0 <= startj < endj <= 109 endj < startj+1
10 mins acceptable, 15 max
https://leetcode.com/problems/interval-list-intersections/description/
class Solution(object):
def intervalIntersection(self, firstList, secondList):
"""
:type firstList: List[List[int]]
:type secondList: List[List[int]]
:rtype: List[List[int]]
"""
ret = []
i = 0
j = 0
while i < len(firstList) and j < len(secondList):
# Find the latest start point
start = max(firstList[i][0], secondList[j][0])
# Find the earliest end point
end = min(firstList[i][1], secondList[j][1])
# If they were overlapping then start <= end otherwise not.
if start <= end:
ret.append([start, end])
# keep the one with the latest end to compare against the next interval.
if firstList[i][1] < secondList[j][1]:
i+=1
else:
j += 1
return ret
O(n), O(1) space (not counting return list)
- Merge Intervals
Medium
Companies: Facebook 2024
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104
10 - 15 mins hard cap
https://leetcode.com/problems/longest-consecutive-sequence/description/
Sort them by start.
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
s_intervals = sorted(intervals)
ret = []
for interval in s_intervals:
if not ret:
ret.append(interval)
else:
# next interval starts after previous ends
if interval[0] > ret[-1][1]:
ret.append(interval)
ret[-1][1] = max(interval[1], ret[-1][1])
return ret
O(nLog(n)), O(n)
- Minimum Add to Make Parentheses Valid
Medium
Companies: Facebook 2024
A parentheses string is valid if and only if:
It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".
Return the minimum number of moves required to make s valid.
Example 1:
Input: s = “())”
Output: 1
Example 2:
Input: s = “(((“
Output: 3
Constraints:
1 <= s.length <= 1000
s[i] is either '(' or ')'.
10 min hard cap. O(n) time O(1) space expected.
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
class Solution:
def minAddToMakeValid(self, s: str) -> int:
count_open = 0
count_close = 0
for i, c in enumerate(s):
if c == '(':
count_open += 1
if c == ')':
if count_open > 0:
count_open -= 1
else:
count_close+=1
return count_open + count_close
O(n), O(1) space
- Group Shifted Strings
Solved
Medium
Topics
Companies
Perform the following shift operations on a string:
Right shift: Replace every letter with the successive letter of the English alphabet, where 'z' is replaced by 'a'. For example, "abc" can be right-shifted to "bcd" or "xyz" can be right-shifted to "yza". Left shift: Replace every letter with the preceding letter of the English alphabet, where 'a' is replaced by 'z'. For example, "bcd" can be left-shifted to "abc" or "yza" can be left-shifted to "xyz".
We can keep shifting the string in both directions to form an endless shifting sequence.
For example, shift "abc" to form the sequence: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
You are given an array of strings strings, group together all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
Example 1:
Input: strings = [“abc”,”bcd”,”acef”,”xyz”,”az”,”ba”,”a”,”z”]
Output: [[“acef”],[“a”,”z”],[“abc”,”bcd”,”xyz”],[“az”,”ba”]]
Example 2:
Input: strings = [“a”]
Output: [[“a”]]
Constraints:
1 <= strings.length <= 200 1 <= strings[i].length <= 50 strings[i] consists of lowercase English letters.
10-15 mins Linear Time
https://leetcode.com/problems/group-shifted-strings/description/
If the diff in 2 chars is negative,
eg za and ab are same, the diff is -25,1
there are 26 letters in the alphabet, thus 26 + (-25) = 1
basically it’s to say a and z are 1 apart.
Make a list then convert to tuple.
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strings:
if len(s) == 1:
d[(0)].append(s)
else:
pattern = []
for i in range(1, len(s)):
diff = ord(s[i])-ord(s[i-1])
if diff < 0:
diff = (ord('z')-ord('a')) + diff + 1
pattern.append(diff)
d[tuple(pattern)].append(s)
output = []
for v in d.values():
output.append(v)
return output
- Subarray Sum Equals K
Medium
Companies: Facebook 2024
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 104 -1000 <= nums[i] <= 1000 -107 <= k <= 107
2 Solutions O(n), O(n) space and O(n^2), O(1) space 20 mins for both.
https://leetcode.com/problems/subarray-sum-equals-k/description/
O(n) Solution, O(n) space (recommended to give O(n^2) solution first (the second one) and then this one.
from collections import defaultdict
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
ret = 0
prefixSumStore = defaultdict(int)
prefixSumStore[0] += 1
prefixSum = 0
for n in nums:
prefixSum += n
ret += prefixSumStore[prefixSum-k]
prefixSumStore[prefixSum] += 1
return ret
Constant Space Solution (most likely will ask) if you give the first one as the first solution.
from collections import defaultdict
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
ret = 0
total = 0
for start in range(len(nums)):
total = 0
for end in range(start, len(nums)):
total += nums[end]
if total == k:
ret += 1
return ret
- Product of Two Run-Length Encoded Arrays
Solved
Medium
Topics
Companies
Hint
Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of consecutive repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.
For example, nums = [1,1,1,2,2,2,2,2] is represented by the run-length encoded array encoded = [[1,3],[2,5]]. Another way to read this is “three 1’s followed by five 2’s”.
The product of two run-length encoded arrays encoded1 and encoded2 can be calculated using the following steps:
Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.
Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].
Compress prodNums into a run-length encoded array and return it.
You are given two run-length encoded arrays encoded1 and encoded2 representing full arrays nums1 and nums2 respectively. Both nums1 and nums2 have the same length. Each encoded1[i] = [vali, freqi] describes the ith segment of nums1, and each encoded2[j] = [valj, freqj] describes the jth segment of nums2.
Return the product of encoded1 and encoded2.
Note: Compression should be done such that the run-length encoded array has the minimum possible length.
Example 1:
Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
Output: [[6,6]]
Explanation: encoded1 expands to [1,1,1,2,2,2] and encoded2 expands to [6,6,6,3,3,3].
prodNums = [6,6,6,6,6,6], which is compressed into the run-length encoded array [[6,6]].
Example 2:
Input: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]
Output: [[2,3],[6,1],[9,2]]
Explanation: encoded1 expands to [1,1,1,2,3,3] and encoded2 expands to [2,2,2,3,3,3].
prodNums = [2,2,2,6,9,9], which is compressed into the run-length encoded array [[2,3],[6,1],[9,2]].
Constraints:
1 <= encoded1.length, encoded2.length <= 105
encoded1[i].length == 2
encoded2[j].length == 2
1 <= vali, freqi <= 104 for each encoded1[i].
1 <= valj, freqj <= 104 for each encoded2[j].
The full arrays that encoded1 and encoded2 represent are the same length.
Element Wise Multiplication.
https://leetcode.com/problems/product-of-two-run-length-encoded-arrays/description/
from collections import deque
class Solution(object):
def findRLEArray(self, encoded1, encoded2):
"""
:type encoded1: List[List[int]]
:type encoded2: List[List[int]]
:rtype: List[List[int]]
"""
res = deque()
carry = 0
one, two = encoded1.pop(), encoded2.pop()
while True:
freq = min(one[1], two[1])
prod = one[0] * two[0]
one[1] -= freq
two[1] -= freq
if res and res[0][0] == prod:
res[0][1] += freq
else:
res.appendleft([prod, freq])
if not one[1] and encoded1:
one = encoded1.pop()
if not two[1] and encoded2:
two = encoded2.pop()
elif not two[1] and not one[1]:
break
return res- Valid Number
Solved
Hard
Topics
Companies
Given a string s, return whether s is a valid number.
For example, all the following are valid numbers: “2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”, while the following are not valid numbers: “abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”.
Formally, a valid number is defined using one of the following definitions:
An integer number followed by an optional exponent.
A decimal number followed by an optional exponent.
An integer number is defined with an optional sign ‘-‘ or ‘+’ followed by digits.
A decimal number is defined with an optional sign ‘-‘ or ‘+’ followed by one of the following definitions:
Digits followed by a dot ‘.’.
Digits followed by a dot ‘.’ followed by digits.
A dot ‘.’ followed by digits.
An exponent is defined with an exponent notation ‘e’ or ‘E’ followed by an integer number.
The digits are defined as one or more digits.
Example 1:
Input: s = “0”
Output: true
Example 2:
Input: s = “e”
Output: false
Example 3:
Input: s = “.”
Output: false
Constraints:
1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus ‘+’, minus ‘-‘, or dot ‘.’.
Hint: Follow the rules and simplify the logic.
https://leetcode.com/problems/valid-number/description/
class Solution:
def isNumber(self, s: str) -> bool:
dp = [0]*len(s)
exponent = {'e', 'E'}
sign = {'+', '-'}
if s and s[0] in sign:
s = s[1:]
sign_possible = False
seen_exp = False
seen_dec = False
seen_digit = False
for i, c in enumerate(s):
if c.isdigit():
seen_digit = True
elif c in exponent:
if not seen_digit or seen_exp or i < 1:
return False
else:
seen_exp = True
seen_digit = False
sign_possible = True
elif c == '.':
if seen_exp or seen_dec:
return False
else:
seen_dec = True
elif c in sign:
if not sign_possible or (i > 0 and s[i-1] not in exponent):
return False
else:
return False
return seen_digit
A Bit more intuitive, break the number to 2 parts expnent and decimal, and verify them
left should be valid decimal and right should be valid exponent (if it exists). Split the decimal in two, and then join them to make one number (without decimal), it should have at least one digit and the right split should NOT start with a sign because if left is empty then .+1 will look like +1
class Solution(object):
@staticmethod
def isSignedInteger(s):
if not s:
return False
if s[0] in {'+', '-'}:
s = s[1:]
return Solution.isInteger(s)
@staticmethod
def isInteger(s):
if not s:
return False
for c in s:
if not c.isdigit():
return False
return True
@staticmethod
def isDecimal(s):
if not s:
return False
split = s.split(".")
if len(split) > 2:
return False
left = split[0]
full = left
if len(split) == 2:
right = split[1]
if right and right[0] in {'+', '-'}:
return False
full += right
return Solution.isSignedInteger(full)
@staticmethod
def isExponent(s):
split = s.split("e")
if len(split) > 2:
return False
if len(split) == 2:
return Solution.isDecimal(split[0]) and Solution.isSignedInteger(split[1])
if len(split) == 1:
return Solution.isDecimal(split[0])
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower()
return Solution.isExponent(s)
- Missing Ranges
Easy
Companies: Facebook
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.
Example 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [[2,2],[4,49],[51,74],[76,99]]
Explanation: The ranges are:
[2,2]
[4,49]
[51,74]
[76,99]
Example 2:
Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.
Constraints:
-109 <= lower <= upper <= 109
0 <= nums.length <= 100
lower <= nums[i] <= upper
All the values of nums are unique.
Careful of edge cases
https://leetcode.com/problems/missing-ranges/description/
class Solution(object):
def findMissingRanges(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: List[List[int]]
"""
ranges = []
i = 0
if not nums:
ranges.append([lower, upper])
return ranges
if nums[0] != lower:
ranges.append([lower, nums[0]-1])
for i in range(len(nums)):
if i > 0 and nums[i-1]+1 == nums[i]:
continue
elif i > 0:
r = [ nums[i-1]+1, nums[i]-1]
ranges.append(r)
i+=1
if nums[-1] != upper:
ranges.append([nums[-1] + 1, upper])
return ranges- Verifying an Alien Dictionary
Solved
Easy
Topics
Companies
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.
Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.
Example 1:
Input: words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
Output: true
Explanation: As ‘h’ comes before ‘l’ in this language, then the sequence is sorted.
Example 2:
Input: words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqstuvxyz”
Output: false
Explanation: As ‘d’ comes after ‘l’ in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:
Input: words = [“apple”,”app”], order = “abcdefghijklmnopqrstuvwxyz”
Output: false
Explanation: The first three characters “app” match, and the second string is shorter (in size.) According to lexicographical rules “apple” > “app”, because ‘l’ > ‘∅’, where ‘∅’ is defined as the blank character which is less than any other character (More info).
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are English lowercase letters.
(do the simplest way)
https://leetcode.com/problems/verifying-an-alien-dictionary/
One Liner
avg letter in word: m
len of words: n
len or order: l
n*mLog(m) + l (Its a guess as I do not know how does python sort lists with individual values)
from collections import defaultdict
class Solution(object):
def isAlienSorted(self, words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
order_dict = {c: i for i,c in enumerate(order)}
modified = list(map(lambda word: map(lambda c: order_dict[c], word), words))
return modified == sorted(modified)
Proper
O(m*n + l)
~~~
from itertools import zip_longest
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
order_dict = {c:i for i,c in enumerate(order)}
order_dict[’$’] = -1
# pair of words
for word_a, word_b in zip(words, words[1:]):
for letter_a, letter_b in zip_longest(word_a, word_b, fillvalue='$'):
if order_dict[letter_a] < order_dict[letter_b]:
break
if order_dict[letter_a] > order_dict[letter_b]:
return False
return True ~~~
- Next Permutation
Hard - Impossible without prior algo knowledge.
Companies: Facebook
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 100
If you know you know, otherwise, see answer.
https://leetcode.com/problems/next-permutation/description/
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(n, start, stop):
while start < stop:
n[start], n[stop] = n[stop], n[start]
start += 1
stop -= 1
pivot_idx = -1
n = len(nums)
prev = float('-inf')
for i in range(n-1, -1,-1):
if nums[i] < prev:
pivot_idx = i
break
prev = nums[i]
if pivot_idx == -1:
reverse(nums, 0, len(nums)-1)
return
pivot = nums[pivot_idx]
swap_idx = n-1
for i in range(n-1, pivot_idx, -1):
if nums[i] > pivot:
swap_idx = i
break
nums[swap_idx], nums[pivot_idx] = nums[pivot_idx], nums[swap_idx]
reverse(nums, pivot_idx+1, n-1)
return
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
- Multiply Strings
Solved
Medium
Topics
Companies
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”
Constraints:
1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
https://leetcode.com/problems/multiply-strings/
class Solution:
def multiply(self, num1: str, num2: str) -> str:
def digit(c):
return ord(c) - ord('0')
def multiply_small(number, d):
carry = 0
num = 0
for i, c in enumerate(number[::-1]):
product = digit(c) * digit(d) + carry
cur_digit = product%10
carry = product//10
num = cur_digit * (10**i) + num
if carry:
num = carry * (10**(i+1)) + num
return num
big, small = num1, num2
if len(num1) < len(num2):
big, small = small, big
p = 0
num = 0
for i, c in enumerate(small[::-1]):
num = (10**i) * multiply_small(big, c) + num
p+=1
return str(num)- Contiguous Array
Medium
Companies: Facebook
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Constraints:
1 <= nums.length <= 105
nums[i] is either 0 or 1.
https://leetcode.com/problems/contiguous-array/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days
from itertools import accumulate
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
# Use the sum to track, like how many extra parenthesis to remove
# Negative count means we just need to remove a subarray with that many extra 0's
# We store the first occurance of such a subarray where either 1's or 0's are in excess, this will
# allow us to get longest, i.e to subtract the minimum amount of index.
# 0 0 0 1 0 0 0 1 1 1
# -3 -2 -3 -4 -5 -4 -3 -2
# In the above example at the second last 1, we are 3 zeros extra, we just need to remove the earlist subarray
# with the same excess zeros. The number of 1's will be the same as number of zeros no matter which -3 you choose
# either at idx 2 or 4 that's why we just store it once.
sum_store = {}
count = 0
longest = 0
for i,c in enumerate(nums):
count += c if c else -1
if not count:
longest = i+1
else:
if count in sum_store:
longest = max(longest, i - sum_store[count])
else:
sum_store[count] = i
return longest
O(n), O(n)
- Continuous Subarray Sum
Solved
Medium
Topics
Companies
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
its length is at least two, and
the sum of the elements of the subarray is a multiple of k.
Note that:
A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1
https://leetcode.com/problems/continuous-subarray-sum/description/
Remember here: every number with the same mod with k, will be multiples of k away from each other.
eg 17,23,29,35 , k = 6
they all have mod 5 and all are multiples of 6 away from each other.
Thus update the subarray with the earliest index for a mod, if you find it later, removing that subarray will gurantee multiple of 6 sum as they HAVE to be in multiples of 6 away from each other
thus do accumulate on them, mod them by k and that is your prefix-sum
then it becomes the same as subarray sum = k
~~~
from collections import defaultdict
from itertools import accumulate
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
modmap = defaultdict(int)
modmap[0] = -1 # Replaces # if mod is 0, and i > 0 : return True
mod_prefix_sum = list(map(lambda x: x%k, accumulate(nums)))
for i, mod in enumerate(mod_prefix_sum):
if mod in modmap:
if i-modmap[mod] > 1:
return True
else:
modmap[mod] = i
return False
~~~
- High-Access Employees
Medium
Topics
Companies: Atlassian
You are given a 2D 0-indexed array of strings, access_times, with size n. For each i where 0 <= i <= n - 1, access_times[i][0] represents the name of an employee, and access_times[i][1] represents the access time of that employee. All entries in access_times are within the same day.
The access time is represented as four digits using a 24-hour time format, for example, “0800” or “2250”.
An employee is said to be high-access if he has accessed the system three or more times within a one-hour period.
Times with exactly one hour of difference are not considered part of the same one-hour period. For example, “0815” and “0915” are not part of the same one-hour period.
Access times at the start and end of the day are not counted within the same one-hour period. For example, “0005” and “2350” are not part of the same one-hour period.
Return a list that contains the names of high-access employees with any order you want.
Example 1:
Input: access_times = [[“a”,”0549”],[“b”,”0457”],[“a”,”0532”],[“a”,”0621”],[“b”,”0540”]]
Output: [“a”]
Explanation: “a” has three access times in the one-hour period of [05:32, 06:31] which are 05:32, 05:49, and 06:21.
But “b” does not have more than two access times at all.
So the answer is [“a”].
Example 2:
Input: access_times = [[“d”,”0002”],[“c”,”0808”],[“c”,”0829”],[“e”,”0215”],[“d”,”1508”],[“d”,”1444”],[“d”,”1410”],[“c”,”0809”]]
Output: [“c”,”d”]
Explanation: “c” has three access times in the one-hour period of [08:08, 09:07] which are 08:08, 08:09, and 08:29.
“d” has also three access times in the one-hour period of [14:10, 15:09] which are 14:10, 14:44, and 15:08.
However, “e” has just one access time, so it can not be in the answer and the final answer is [“c”,”d”].
Example 3:
Input: access_times = [[“cd”,”1025”],[“ab”,”1025”],[“cd”,”1046”],[“cd”,”1055”],[“ab”,”1124”],[“ab”,”1120”]]
Output: [“ab”,”cd”]
Explanation: “ab” has three access times in the one-hour period of [10:25, 11:24] which are 10:25, 11:20, and 11:24.
“cd” has also three access times in the one-hour period of [10:25, 11:24] which are 10:25, 10:46, and 10:55.
So the answer is [“ab”,”cd”].
Constraints:
1 <= access_times.length <= 100
access_times[i].length == 2
1 <= access_times[i][0].length <= 10
access_times[i][0] consists only of English small letters.
access_times[i][1].length == 4
access_times[i][1] is in 24-hour time format.
access_times[i][1] consists only of ‘0’ to ‘9’.
https://leetcode.com/problems/high-access-employees/description
from itertools import starmap, groupby
from collections import deque,defaultdict
class Solution:
def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
time_check = defaultdict(deque)
def std_time(mil_time):
mins = int(mil_time[2:])
hrs = int(mil_time[:2])
return mins + (hrs * 60)
entries_sorted = sorted(starmap(lambda emp, t: (emp, std_time(t)), access_times), key=lambda x:(x[0], x[1]))
hae = set()
for emp, time_mins in entries_sorted:
# We already marked this employe High Access, no need for further checks.
if emp in hae:
continue
if emp not in time_check:
time_check[emp].append(time_mins)
continue
else:
while time_check[emp] and time_mins - time_check[emp][0] >= 60:
time_check[emp].popleft()
time_check[emp].append(time_mins)
if len(time_check[emp]) >= 3:
hae.add(emp)
return list(hae)
O(nLog(n)), space O(n)
- Rank Teams by Votes
Medium
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.
The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.
You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.
Return a string of all teams sorted by the ranking system.
Example 1:
Input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
Output: “ACB”
Explanation:
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.
Example 2:
Input: votes = [“WXYZ”,”XYZW”]
Output: “XWYZ”
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.
Example 3:
Input: votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
Output: “ZMNAGUEDSJYLBOPHRQICWFXTVK”
Explanation: Only one voter, so their votes are used for the ranking.
Constraints:
1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.
https://leetcode.com/problems/rank-teams-by-votes
from collections import defaultdict
class Solution(object):
def rankTeams(self, votes):
"""
:type votes: List[str]
:rtype: str
"""
votelen = len(votes[0]) - 1
count = defaultdict(lambda: [0]*len(votes[0]))
for vote in votes:
for i in range(len(vote)):
count[vote[i]][i] += 1
entries = []
for k, v in count.items():
entries.append((v, k))
entries = sorted(entries, reverse=True, key=lambda x: (x[0], -ord(x[1])))
answer = "".join(list(map(lambda e: e[1], entries)))
return answer- Majority Element II
Medium
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
https://leetcode.com/problems/majority-element-ii
from collections import defaultdict
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
counts = defaultdict(int)
for num in nums:
if num not in counts and len(counts) >= 2:
candidates = list(counts.keys())
for k in candidates:
counts[k] -= 1
if counts[k] < 1:
del[counts[k]]
else:
counts[num] += 1
return filter(lambda k: nums.count(k) > len(nums)//3, counts.keys())Subarray with k-distinct elements
(no leetcode)
Return the number of subarrays in the given nums array that have k distinct elements.
nums = [1,2,6,6,3,6,7,1,8] k = 3 k_distinct(nums, k) Output: 9 [1, 2, 6] [1, 2, 6, 6] [2, 6, 6, 3] [2, 6, 6, 3, 6] [6, 6, 3, 6, 7] [6, 3, 6, 7] [3, 6, 7] [6, 7, 1] [7, 1, 8]
from collections import defaultdict
def k_distinct(nums, k):
uniq = {}
l = 0
r = 0
subarr = 0
while r < len(nums):
if nums[r] in uniq:
uniq[nums[r]] += 1
else:
uniq[nums[r]] = 1
if len(uniq) == k:
subarr+=1
print(nums[l:r+1])
elif len(uniq) == k+1:
while len(uniq) == k+1 and l < r:
uniq[nums[l]] -= 1
if uniq[nums[l]] == 0:
del(uniq[nums[l]])
l += 1
if len(uniq) == k+1:
subarr+=1
print(nums[l:r])
if len(uniq) == k:
subarr += 1
print(nums[l:r+1])
r+=1
return subarr- First Missing Positive
Solved
Hard
Topics
Companies
Hint
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
https://leetcode.com/problems/first-missing-positive/description/
Observe the answer has to be in range 1 to n+1 n is len
if we have array of length 3
[1,2,3]
the missing number is 4
[-1,-2,-3] the missing number is 1
[1,99,3] the missing number is 2
[1,2,4] the missing number is 3
it is because you can only fit n numbers in array of length n, so best case you fit all 1 to n the answer is n+1
Solution: Arranges the array in a way where each positive number in the range 1-to-n in its correct location. i.e num-1 i.e 3 will sit at idx 2 (0 indexed)
if the numbers are negative or larger than n, then just ignore then,
Once the swapping is done, return the first number which is not at it’s location, else return n+1 since if all numbers are at their locations then it means the array is complete.
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
for i in range(n):
while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
a, b = nums[i] - 1, i
nums[a], nums[b] = nums[b], nums[a]
for i in range(n):
if nums[i] != i+1:
return i+1
return n+1
