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