Flashcards for "Array & HashMaps"

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        
        unique_elements = set(nums)
        if len(nums)>len(unique_elements):
            return True
        else:
            return False

from typing import List

class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string."""
        DELIMITER = "#"  # Delimiter used to separate length and word
        ans = ""
        for word in strs:
            ans += str(len(word)) + DELIMITER + word
        return ans

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings."""
        result = []
        i = 0
        while i < len(s):
            j = i
            # Find the delimiter to determine the length of the next word.
            while s[j] != "#":
                j += 1
            
            length = int(s[i:j])
            word = s[j + 1 : j + 1 + length]
            result.append(word)
            # Move index i past the current encoded segment.
            i = j + 1 + length
        
        return result

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def char_frequency(word: str) -> tuple:
            """Return a tuple representing the frequency of each letter in the word."""
            freq = [0] * 26  # Only 26 letters in the English alphabet
            for ch in word:
                freq[ord(ch) - ord('a')] += 1
            return tuple(freq)
        
        anagram_groups = defaultdict(list)
        for word in strs:
            key = char_frequency(word)
            anagram_groups[key].append(word)
        
        return list(anagram_groups.values())

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        
        graph=set(nums)

        def dfs(num, graph, visited):

            if num in visited:
                return 0
            
            if num not in graph:
                return 0
            visited.add(num)
            seq=dfs(num+1, graph, visited) + 1
            #visited.remove(num)
            return seq
        
        visited=set()
        max_seq=0
        for num in nums:
            if num-1 not in graph:
                max_seq=max(dfs(num, graph, visited), max_seq)
        
        return max_seq

import heapq
from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        min_heap: list[tuple[int, int]] = []           # (freq, num)

        for num, freq in Counter(nums).items():
            heapq.heappush(min_heap, (freq, num))
            if len(min_heap) > k:                      # keep size ≤ k
                heapq.heappop(min_heap)

        return [num for _, num in min_heap]            # order arbitrary

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        count = defaultdict(int)
        
        # Count the frequency of characters in string s
        for x in s:
            count[x] += 1
        
        # Decrement the frequency of characters in string t
        for x in t:
            count[x] -= 1
        
        # Check if any character has non-zero frequency
        for val in count.values():
            if val != 0:
                return False
        
        return True

class Solution(object):
    def isValidSudoku(self, board):

        row, col= 9, 9

        row_dict=[set() for i in range(row)]
        col_dict=[set() for i in range(col)]
        row_col_dict=[]

        for row_index in range(0,3):
            r=[]
            for col_index in range(0,3):
                r.append(set())
            row_col_dict.append(r)
        
        for r_i in range(row):
            for c_i in range(col):
                c=board[r_i][c_i]
                if c.isdigit():
                    if c in row_dict[r_i] or c in col_dict[c_i] or c in row_col_dict[int(r_i/3)][int(c_i/3)]:
                        return False
                    else:
                        row_dict[r_i].add(c)
                        col_dict[c_i].add(c)
                        row_col_dict[int(r_i/3)][int(c_i/3)].add(c)

        return True