Hashmap and set in Python

Posted on Edited on In , Views:

Intro

Hashmap is indexed data structures. A hash map makes use of a hash function to compute an index with a key into an array of buckets or slots. Its value is mapped to the bucket with the corresponding index. The key is unique and immutable. Hash function is the core of implementing a hash map. It takes in the key and translates it to the index of a bucket in the bucket list. Ideal hashing should produce a different index for each key. However, collisions can occur. When hashing gives an existing index, we can simply use a bucket for multiple values by appending a list or by rehashing.

A Set in Python is an unordered collection data type that is iterable, mutable and has no duplicate elements. Set are represented by {} (values enclosed in curly braces). The major advantage of using a set, as opposed to a list, is that it has a highly optimized method for checking whether a specific element is contained in the set. This is based on a data structure known as a hash table. Since sets are unordered, we cannot access items using indexes as we do in lists.

[Leetcode 49] Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

1
2
Input: strs = [""]
Output: [[""]]

Example 3:

1
2
Input: strs = ["a"]
Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        m1 = defaultdict(list)
        for s in strs:
            s1 = ''.join(sorted(s))
            m1[s1].append(s)

        res = []
        for group in m1.values():
            res.append(group)

        return res

[Leetcode 128] Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

1
2
3
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

1
2
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s1 = set(nums)
        longest = 0
        for num in nums:
            # found a new sequence and count its length
            if num - 1 not in s1:
                count = 0
                while True:
                    if num in s1:
                        count += 1
                        num += 1
                    else:
                        break

                # save to longest
                longest = max(longest, count)

        return longest

[Leetcode 138] Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

1
2
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

1
2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

1
2
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        oldToNew = {}

        # copy a new node for each original node
        curr = head
        while curr:
            oldToNew[curr] = Node(curr.val)
            curr = curr.next

        curr = head
        while curr:
            # get() returns None if the key doesn't exist
            oldToNew[curr].next = oldToNew.get(curr.next) 
            oldToNew[curr].random = oldToNew.get(curr.random)
            curr = curr.next

        return oldToNew[head]

[Leetcode 290] Word Pattern

Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

1
2
Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

1
2
Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

1
2
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ‘ ‘.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        m1 = {}
        words = s.split(' ')
        if len(pattern) != len(words):
            return False
        
        # a pattern character can only be mapped to a word. 
        # e.g. if 'dog' is already mapped to 'a', then a different word like 'fish' can't be mapped to 'a'
        mapped = [False] * 26

        for j, word in enumerate(words):
            # get the corresponding letter in the pattern
            letter = pattern[j]
            idx = ord(letter) - ord('a')

            # put new word in map if possible
            if word not in m1:
                if mapped[idx]:
                    return False
                else:
                    m1[word] = letter
                    mapped[idx] = True 

            # check if the already mapped pattern letter equals the current letter
            else:
                if m1[word] != letter:
                    return False

        return True

[Leetcode 380] Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output:
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import random

class RandomizedSet:

    def __init__(self):
        self.nums = [] # for random access
        self.map = {}  # value to index map helps locate the target value in array to be removed

    def insert(self, val: int) -> bool:
        if val in self.map:
            return False

        self.nums.append(val)  # always append to the end of list
        self.map[val] = len(self.nums) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.map:
            return False

        # get the index of target value
        index = self.map[val]

        # swap the target value with the last value in array
        if index != len(self.nums) - 1:
            # replace with the last element
            lastIdx = len(self.nums) - 1
            lastVal = self.nums[lastIdx]
            self.nums[index], self.nums[lastIdx] = lastVal, val
            self.map[lastVal] = index

        # remove the target value from array
        self.nums.pop()

        # remove the target value from map
        del self.map[val]

        return True

    # random access to the array
    def getRandom(self) -> int:
        return self.nums[random.randint(0, len(self.nums) - 1)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

[Leetcode 1657] Determine if Two Strings Are Close

Two strings are considered close if you can attain one from the other using the following operations:

  • Operation 1: Swap any two existing characters.
    For example, abcde -> aecdb
  • Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
    For example, aacabb -> bbcbaa (all a’s turn into b’s, and all b’s turn into a’s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

1
2
3
4
5
Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

1
2
3
Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

1
2
3
4
5
6
Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Constraints:

  • 1 <= word1.length, word2.length <= 105
  • word1 and word2 contain only lowercase English letters.

Solution:

1
2
3
4
5
class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        # e.g. word1="abc", word2="bca" -> Counter({'a': 1, 'b': 1, 'c': 1}) Counter({'b': 1, 'c': 1, 'a': 1})
        c1 , c2 = Counter(word1), Counter(word2)
        return c1.keys() == c2.keys() and sorted(c1.values()) == sorted(c2.values())