diff options
| -rw-r--r-- | 1_array_hashing/contains_duplicate.py | 9 | ||||
| -rw-r--r-- | 1_array_hashing/group_anagram.py | 78 | ||||
| -rw-r--r-- | 1_array_hashing/two_sum.py | 83 |
3 files changed, 167 insertions, 3 deletions
diff --git a/1_array_hashing/contains_duplicate.py b/1_array_hashing/contains_duplicate.py index 142bcca..e437e4f 100644 --- a/1_array_hashing/contains_duplicate.py +++ b/1_array_hashing/contains_duplicate.py @@ -21,17 +21,20 @@ Output: false """ +from typing import List + + class Solution: # 1. brute force - def brute_force(self, nums: list[int]) -> bool: + def brute_force(self, nums: List[int]) -> bool: return False # 2. sorting - def sorting(self, nums: list[int]) -> bool: + def sorting(self, nums: List[int]) -> bool: return False # 3. hashset - def hashset(self, nums: list[int]) -> bool: + def hashset(self, nums: List[int]) -> bool: hs = set() for i in range(len(nums)): if nums[i] in hs: diff --git a/1_array_hashing/group_anagram.py b/1_array_hashing/group_anagram.py new file mode 100644 index 0000000..f302afa --- /dev/null +++ b/1_array_hashing/group_anagram.py @@ -0,0 +1,78 @@ +""" +Question + +Anagram Groups + +Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order. + +An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different. + +Example 1: + +Input: strs = ["act","pots","tops","cat","stop","hat"] + +Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]] + +Example 2: + +Input: strs = ["x"] + +Output: [["x"]] + +Example 3: + +Input: strs = [""] + +Output: [[""]] + +Constraints: + + 1 <= strs.length <= 1000. + 0 <= strs[i].length <= 100 + strs[i] is made up of lowercase English letters. +""" + +from collections import defaultdict +from typing import List + + +class Solution: + def dictionary(self, strs: List[str]) -> List[List[str]]: + res = defaultdict(List) + for s in strs: + count = [0] * 26 + for c in s: + count[ord(c) - ord("a")] += 1 + res[tuple(count)].append(s) + return list(res.values()) + + +case1 = ["act", "pots", "tops", "cat", "stop", "hat"] +case2 = ["x"] +case3 = [""] + +solution = Solution() +print(f" dictionary case1: {solution.dictionary(case1)}") +print(f" dictionary case2: {solution.dictionary(case2)}") +print(f" dictionary case3: {solution.dictionary(case3)}") + + +""" +Solution + +url: https://neetcode.io/problems/anagram-groups +video: https://youtu.be/vzdNOK2oB2E +code: +```dictionary +class Solution: + def groupAnagrams(self, strs: List[str]) -> List[List[str]]: + ans = defaultdict(list) + + for s in strs: + count = [0] * 26 + for c in s: + count[ord(c) - ord("a")] += 1 + ans[tuple(count)].append(s) + return ans.values() +``` +""" diff --git a/1_array_hashing/two_sum.py b/1_array_hashing/two_sum.py new file mode 100644 index 0000000..76ea68d --- /dev/null +++ b/1_array_hashing/two_sum.py @@ -0,0 +1,83 @@ +""" +Question + +Two Integer Sum + +Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j. + +You may assume that every input has exactly one pair of indices i and j that satisfy the condition. + +Return the answer with the smaller index first. + +Example 1: + +Input: +nums = [3,4,5,6], target = 7 + +Output: [0,1] + +Explanation: nums[0] + nums[1] == 7, so we return [0, 1]. + +Example 2: + +Input: nums = [4,5,6], target = 10 + +Output: [0,2] + +Example 3: + +Input: nums = [5,5], target = 10 + +Output: [0,1] + +Constraints: + + 2 <= nums.length <= 1000 + -10,000,000 <= nums[i] <= 10,000,000 + -10,000,000 <= target <= 10,000,000 +""" + + +from typing import List + + +class Solution: + def hashmap(self, nums: List[int], target: int) -> List[int]: + mp = {} + for i, n in enumerate(nums): + diff = target - n + if diff in mp: + return [mp[diff], i] + mp[nums[i]] = i + return [-1, -1] + + +case1 = [3, 4, 5, 6] +target1 = 7 +case2 = [4, 5, 6] +target2 = 10 +case3 = [5, 5] +target3 = 10 + +solution = Solution() +print(f" hashmap case1: {solution.hashmap(case1, target1)}") +print(f" hashmap case2: {solution.hashmap(case2, target2)}") +print(f" hashmap case3: {solution.hashmap(case3, target3)}") + + +""" +Solution + +url: https://neetcode.io/problems/two-integer-sum +video: https://youtu.be/KLlXCFG5TnA +code: +class Solution: + def twoSum(self, nums: List[int], target: int) -> List[int]: + prevMap = {} # val -> index + + for i, n in enumerate(nums): + diff = target - n + if diff in prevMap: + return [prevMap[diff], i] + prevMap[n] = i +""" |