NeetCode/LeetCode: Python Solutions of Arrays & Hashing Problems with Descriptions
This article contains solutions of blind 75 neetcode.io problems with descriptions.
Problem 1: Contains Duplicate
Solution: We will use builtin set data structure of Python.
Set: A set is an unordered collection with no duplicate elements.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
unique_nums = set()
for n in nums:
# check if number is present in hash set
if n in unique_nums:
return True
# add number to set if it is not already present
unique_nums.add(n)
return False
Problem 2: Valid Anagram
Solution: We use dictionary to maintain the character count. If count is equal, this means two strings are anagram
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# If length of s is not equal to t returns False
if len(s) != len(t):
return False
count_s, count_t = {}, {} # empty dictionaries
for i in range(len(s)):
# get the character count in dictionary,
# if not present initialize the count with 1
count_s[s[i]] = 1 + count_s.get(s[i], 0)
count_t[t[i]] = 1 + count_t.get(t[i], 0)
return count_s == count_t
Problem 3: Two Sum
Solution: We will use dictionary to find if target value minus the number is present in array. If present we will return the indices of two numbers
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map_ = {} # value -> index
for i, n in enumerate(nums):
diff = target - n # difference of target and current element
if diff in map_: # if diff is present in dict
# return indices of element equal to diff
# and the current element
return [map_[diff], i]
map_[n] = i # add value and index to map
Problem 4: Group Anagrams
Solution: Use sorted string as a dictionary key to append anagrams
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
grouped_anagrams = {}
for str_ in strs:
# sort the string
s_str_ = "".join(sorted(str_))
# if sorted string key exists append the original string
if s_str_ in grouped_anagrams:
grouped_anagrams[s_str_].append(str_)
else:
# Create a key-value pair with sorted string as key
# and original string as value
grouped_anagrams[s_str_] = [str_]
return list(grouped_anagrams.values())
Problem 5: Product of Array Except Self
Solution: We keep two variable with prefix and suffix array products
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
products = [0]*len(nums)
prefix_prod = 1
suffix_prod = 1
# calculating prefix product
for i, n in enumerate(nums):
products[i] = prefix_prod
prefix_prod *= n
# multiplying prefix product with suffix product
for i in range(len(nums) - 1, -1, -1):
products[i] *= suffix_prod # multiply prefix with suffix
suffix_prod *= nums[i] # multiply suffix with the current element
return products
Problem 6: Longest Consecutive Sequence
Solution: We will use set to hold unique elements, iterate over array and increase the current element value with one, and check its presence in input array. For better understanding see the solution below:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
unique_nums = set(nums)
length = 0
for n in nums:
# starting of a new sequence, if previous
# element is already present it means
# that sequence is covered in below loop
if n - 1 not in unique_nums:
j = n
# keep on increasing the sequence count if it
# is present in inp array
while j in unique_nums:
j += 1
length = max(length, j - n)
return length