Arrays & Hashing - Solutions (Phase 1)

1) Two Sum

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = []
        mp = {}
        for i in range(len(nums)):
            diff = target - nums[i]
            if diff in mp:
                return [mp[diff], i]
            mp[nums[i]] = i
        return []

2) Contains Duplicate

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        res = set()
        for num in nums:
            if num in res:
                return True
            else:
                res.add(num)
        return False

3) Valid Anagram

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        mp = {}
        for i in s:
            if i in mp:
                mp[i] += 1
            else:
                mp[i] = 1
        for i in t:
            if i in mp:
                mp[i] -= 1
            else:
                return False

        for i in mp:
            if mp[i] != 0:
                return False

        return True

4) Group Anagrams

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        grp_anagrams = {}
        for s in strs:
            strd_strs = "".join(sorted(s))
            if strd_strs in grp_anagrams:
                grp_anagrams[strd_strs].append(s)
            else:
                grp_anagrams[strd_strs] = [s]
        return list(grp_anagrams.values())

5) Majority Element

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        mp = {}
        majority = len(nums) / 2
        for i in range(len(nums)):
            if nums[i] in mp:
                mp[nums[i]] += 1
            else:
                mp[nums[i]] = 1
        for k, v in mp.items():
            if v > majority:
                return k

6) Product of Array Except Self

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        ans = [1] * n
        prefix = 1
        for i in range(n):
            ans[i] = prefix
            prefix *= nums[i]
        suffix = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= suffix
            suffix *= nums[i]
        return ans

7) Top K Frequent Elements

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        mp = {}
        for i in range(len(nums)):
            if nums[i] in mp:
                mp[nums[i]] += 1
            else:
                mp[nums[i]] = 1

        sorted_keys = sorted(mp.keys(), key=lambda x: mp[x], reverse=True)
        return sorted_keys[:k]

8) Longest Consecutive Sequence

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_set = set(nums)
        longest_streak = 0

        for num in nums_set:
            if (num - 1) not in nums_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in nums_set:
                    current_num = current_num + 1
                    current_streak = current_streak + 1

                longest_streak = max(longest_streak, current_streak)
        return longest_streak

9) Subarray Sum Equals K

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        prefix_sum = {0: 1}
        cur_sum = 0
        total_subarray = 0

        for num in nums:
            cur_sum += num
            if (cur_sum - k) in prefix_sum:
                total_subarray += prefix_sum[cur_sum - k]
            prefix_sum[cur_sum] = prefix_sum.get(cur_sum, 0) + 1
        return total_subarray

10) First Missing Positive

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                target_idx = nums[i] - 1
                nums[i], nums[target_idx] = nums[target_idx], nums[i]

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1