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
