Documenting Leetcode solving.
Q1
Easy. Array
Use a hashmap to store items value and index ({value: index}). Check if the difference of the target and current item is in the hashmap.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = {}
for i, n in enumerate(nums):
diff = target - n
if diff in map:
return [map[diff], i]
map[n] = i
Q2
Medium. Array
Solution from Neetcode, youtube.com/watch?v=YPTqKIgVk-k
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
freq = [[] for i in range(len(nums) + 1)]
# Count each items frequency
for n in nums:
count[n] = count.get(n, 0) + 1
# Bucket sort, frequency array
for n, c in count.items():
freq[c].append(n)
res = []
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
res.append(n)
if len(res) == k:
return res
Q3
238. Product of Array Except Self
Medium. Array
Left production * right production = output
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
prefix = 1
for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res