<jupyter_start><jupyter_text>Hashtable  Pre-run<jupyter_code>from typing import List
from helpers.misc import *<jupyter_output><empty_output><jupyter_text>1 [Two Sum](https://leetcode.com/problems/two-sum/) - E - Google Frequent * [Answer from Huahua](https://www.youtube.com/watch?v=tNtk_rwbaIk)  One Pass HashTable * Runtime: 44 ms, faster than 92.55% of Python3 online submissions for Two Sum.* Memory Usage: 14.1 MB, less than 61.16% of Python3 online submissions for Two Sum.<jupyter_code>class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        '''Given an array of integers, return indices of the two numbers such that they add up to a specific target.'''
        hash = {}   # One-pass growing hash
        for i, num in enumerate(nums):
            if target-num not in hash:
                hash[num] = i
            else:
                return [hash[target-num], i]
        return [0,0]
# test
eq(Solution().twoSum([2, 7, 11, 15], 9), [0, 1])<jupyter_output><empty_output><jupyter_text>15 [3Sum](https://leetcode.com/problems/3sum/) - M * [Answer](https://fizzbuzzed.com/top-interview-questions-1/)  Two Pointer * The Two Pointer trick gives a really nice solution to 3Sum that does not require any extra data structures. It runs really quickly and some interviewers expect this solution.* Runtime: 968 ms, faster than 55.93% of Python3 online submissions for 3Sum.* Memory Usage: 16.2 MB, less than 100.00% of Python3 online submissions for 3Sum.<jupyter_code>class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        '''3Sum using two pointer trick.'''
        ans = []
        nums.sort()
        for l in range(len(nums)-2):
            # avoid same left numbers
            if l > 0 and nums[l] == nums[l-1]:
                continue
            m, r = l+1, len(nums)-1
            while m < r:
                s = nums[l] + nums[m] + nums[r]
                if s == 0:
                    ans.append([nums[l], nums[m], nums[r]])
                    # same left number, different answer, middle number must not be the same.
                    m += 1
                    while m > l+1 and m < r and nums[m] == nums[m-1]:
                        m += 1
                elif s < 0:
                    m += 1
                else:
                    r -= 1
        return ans
# test
eq(Solution().threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]])<jupyter_output><empty_output><jupyter_text>18 [4Sum](https://leetcode.com/problems/4sum/) - M  1 + 3Sum * Runtime: 976 ms, faster than 46.43% of Python3 online submissions for 4Sum.* Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for 4Sum.<jupyter_code>class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        '''4Sum using 3Sum.'''
        def threeSum(nums: List[int], target: int) -> List[List[int]]:
            '''3Sum using two pointer trick.
            
            Assert that nums are already sorted.
            '''
            ans = []
            for l in range(len(nums)-2):
                # avoid same left numbers
                if l > 0 and nums[l] == nums[l-1]:
                    continue
                m, r = l+1, len(nums)-1
                while m < r:
                    s = nums[l] + nums[m] + nums[r]
                    if s == target:
                        ans.append([nums[l], nums[m], nums[r]])
                        # same left number, different answer, middle number must not be the same.
                        m += 1
                        while m < r and nums[m] == nums[m-1]:
                            m += 1
                    elif s < target:
                        m += 1
                    else:
                        r -= 1
            return ans
        nums.sort()
        ans = []
        for l in range(len(nums)-3):
            if l > 0 and nums[l] == nums[l-1]:
                continue
            else:
                for a in threeSum(nums[l+1:], target - nums[l]):
                    a.append(nums[l])
                    ans.append(a)
        return ans
# test
eq(Solution().fourSum([1, 0, -1, 0, -2, 2], 0), [[-1, 1, 2, -2], [0, 0, 2, -2], [0, 0, 1, -1]])<jupyter_output><empty_output><jupyter_text>410 [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/) - H - Google Frequent * [Answer from Huahua](https://www.youtube.com/watch?v=_k-Jb4b7b_0)* DP, Binary Search  560 [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) - M * [Answer from Huahua](https://www.youtube.com/watch?v=mKXIH9GnhgU)* Prefix Sum, Hash Table  136 [Single Number](https://leetcode.com/problems/single-number/) - E   HashTable * Runtime: 84 ms, faster than 85.38% of Python3 online submissions for Single Number.* Memory Usage: 16.4 MB, less than 6.56% of Python3 online submissions for Single Number.<jupyter_code>class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        '''Solving single number problem by hash table.'''
        hash = {}
        for num in nums:
            if num not in hash:
                hash[num] = 0
            hash[num] += 1
        for k in hash:
            if hash[k] == 1:
                return k<jupyter_output><empty_output><jupyter_text>Bit Manipulation (XOR) * If we take `XOR` of zero and some bit, it will return that bit    * `a ⊕ 0 = a`* If we take `XOR` of two same bits, it will return 0    * `a ⊕ a = 0`    * `a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b`* So we can `XOR` all bits together to find the unique number.* Runtime: 80 ms, faster than 95.52% of Python3 online submissions for Single Number.* Memory Usage: 16.4 MB, less than 6.56% of Python3 online submissions for Single Number.<jupyter_code>class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        '''Solving single number problem by bit manipulation (XOR).'''
        ans = 0
        for num in nums:
            ans ^= num
        return ans
# test
eq(Solution().singleNumber([2,2,1]), 1)
eq(Solution().singleNumber([4,1,2,1,2]), 4)<jupyter_output><empty_output><jupyter_text>49 [Group Anagrams](https://leetcode.com/problems/group-anagrams/) - M   Categorize by Sorted String * Runtime: 152 ms, faster than 10.13% of Python3 online submissions for Group Anagrams.* Memory Usage: 17.7 MB, less than 30.19% of Python3 online submissions for Group Anagrams.<jupyter_code>class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        '''Categorize by sorted string.'''
        # key: tuple(sorted(val))
        # val: [val1, val2, ...] that has the same key
        anagram_dict = {}
        for str in strs:
            tup_set_str = tuple(sorted(str))
            if tup_set_str not in anagram_dict:
                anagram_dict[tup_set_str] = []
            anagram_dict[tup_set_str].append(str)
        return list(anagram_dict.values())<jupyter_output><empty_output><jupyter_text>Categorize by Count * Runtime: 220 ms, faster than 5.01% of Python3 online submissions for Group Anagrams.* Memory Usage: 18.8 MB, less than 11.32% of Python3 online submissions for Group Anagrams.<jupyter_code>class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        '''Categorize by alphabet count.'''
        # key: tuple of alphabet count
        # val: [val1, val2, ...] that has the same alphabet count
        anagram_dict = {}
        for str in strs:
            count = [0] * 26
            for ch in str:
                count[ord(ch) - ord('a')] += 1
            tup_count = tuple(count)
            if tup_count not in anagram_dict:
                anagram_dict[tup_count] = []
            anagram_dict[tup_count].append(str)
        return list(anagram_dict.values())
# test
eq(len(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])), 3)<jupyter_output><empty_output><jupyter_text>525 [Contiguous Array](https://leetcode.com/problems/contiguous-array/) - M  Hash Table  * Runtime: 920 ms, faster than 67.15% of Python3 online submissions for Contiguous Array.* Memory Usage: 18.4 MB, less than 16.67% of Python3 online submissions for Contiguous Array.<jupyter_code>class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        map = {}
        map[0] = -1
        maxlen = 0
        count = 0
        for i in range(len(nums)):
            count += 1 if nums[i] == 1 else -1
            if count in map:
                maxlen = max(maxlen, i-map[count])
            else:
                map[count] = i
        return maxlen
# test
eq(Solution().findMaxLength([0,1,0]), 2)
eq(Solution().findMaxLength([0,1,1,0,0,1,0]), 6)
eq(Solution().findMaxLength([0,1,1,0,1,1,1,0]), 4)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12933898499255356, 'fraction_numerical': 0.03287890938251804, 'mean_word_length': 2.1954612005856515, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 50, 'https://': 12, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '244941', 'license': 'MIT', 'n_tokens_mistral': 3043, 'n_tokens_neox': 2782, 'n_words': 867, 'path': 'ipynb/hashtable.ipynb', 'repo_name': 'novate/brosseurs', 'size': '8729'}