Jun 30, 2024 | sunday 2:14 pm
This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumArray
Try it yourself here!
Problem Statement: In this problem, the goal of the algorithm is for each element in the array, find the product of all the other elements. In other words, 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].
Example: [1, 2, 3, 4] Doing this by handle is simple. For the first index, multiply by 2 * 3 * 4 = 24, for the second index multiply 1 * 3 * 4 = 12, and so on. The final result is [24, 12, 8, 6].
Solution: The first thing that I noticed was in the second index, I had to multiply elements on the left and right side of the index. This led to my intuiton of needing two passes through the array, one in which elements on the left are multiplied and then elements on the right are multiplied. Since I needed two passes through the array, I decided to go for an O(1) space solution with an additional array holding the result.
Algorithm: For designing the two pass algorithm, my approach was to:
Complexity:
def productExceptSelf(self, nums: List[int]) -> List[int]:
ans = [0] * len(nums)
ans[0] = 1
for i in range(1, len(nums)):
ans[i] = ans[i - 1] * nums[i - 1]
R = 1
for i in range(len(nums) -1, -1, -1):
ans[i] *= R
R *= nums[i]
return ans
EasyArray
Try it yourself here!
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
Complexity:
EasyString
Try it yourself here!
def isAnagram(self, s: str, t: str) -> bool:
return collections.Counter(s) == collections.Counter(t)
Complexity:
EasyArray
Try it yourself here!
def twoSum(self, nums: List[int], target: int) -> List[int]:
mp = {}
for i in range(len(nums)):
diff = target - nums[i]
if diff in mp:
return [mp[diff], i]
mp[nums[i]] = i
Complexity:
MediumString
Try it yourself here!
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = defaultdict(list)
for s in strs:
arr = [0] * 26
for c in s:
arr[ord(c) - ord('a')] += 1
mp[tuple(arr)].append(s)
return mp.values()
Complexity:
Time: O(n * c). Where n is the size of the strs array and c is the size of the longest string in the array.
Space: O(n * c). The map storing the anagrams take up n * c space.
MediumArray
Try it yourself here!
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == len(nums):
return nums
count = Counter(nums)
heap = []
for key, val in count.items():
heappush(heap, (val, key))
if len(heap) > k:
heappop(heap) # Ensure heap only contains top k frequent elements
# Extract elements from the heap (only top k frequent elements remain)
res = []
while heap:
res.append(heappop(heap)[1])
# Reverse the result to get elements in descending order of frequency
return res[::-1]
Complexity:
MediumArray
Try it yourself here!
def isValidSudoku(self, board: List[List[str]]) -> bool:
N = 9
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
sqs = [set() for _ in range(N)]
for i in range(N):
for j in range(N):
val = board[i][j]
if val == ".":
continue
if val in rows[i]:
return False
if val in cols[j]:
return False
idx = (i // 3) * 3 + j // 3
if val in sqs[idx]:
return False
sqs[idx].add(val)
rows[i].add(val)
cols[j].add(val)
return True
Complexity:
MediumArray
Try it yourself here!
def longestConsecutive(self, nums: List[int]) -> int:
longestStreak = 0
numSet = set(nums)
for n in numSet:
if n - 1 not in numSet:
curr_streak = 1
while n + 1 in numSet:
curr_streak += 1
n += 1
longestStreak = max(curr_streak, longestStreak)
return longestStreak
Complexity: