Arrays & Hashing

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Arrays & Hashing は最も基本的かつ問題範囲の広い分野です。

1. Contains Duplicate

Problem

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

Input: nums = [1, 2, 3, 3]

Output: true

Example 2:

Input: nums = [1, 2, 3, 4]

Output: false

Solution

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hash_set = set()
        for num in nums:
            if num in hash_set:
                return True
            hash_set.add(num)
        
        return False

2. Valid Anagram

Problem

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

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: s = "racecar", t = "carrace"

Output: true

Example 2:

Input: s = "jar", t = "jam"

Output: false

Solution

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_counter = Counter(s)
        t_counter = Counter(t)

        for c, count in s_counter.items():
            if count != t_counter[c]:
                return False
        
        for c, count in t_counter.items():
            if count != s_counter[c]:
                return False
        
        return True

3. Two Sum

Problem

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.

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # diff(target - num) -> index
        # target = num[i] + num[j] なので、
        # num[j] = target - num[i] となることを利用して効率的に解く
        diff_index_map = {}

        for i, num in enumerate(nums):
            if num in diff_index_map:
                return [diff_index_map[num], i]
            diff_index_map[target - nums[i]] = i

4. Group Anagrams

Problem

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: [[""]]

Solution (optimal)

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if len(strs) <= 1:
            return [strs]
        
        # それぞれの文字のカウントを示したtuple -> オリジナルの文字列
        ascii_words_map = defaultdict(list)

        for word in strs:
            ascii_array = [0] * 26
            for c in word:
                # 文字を0から26の数字に変換
                ascii = ord(c) - ord('a')
                ascii_array[ascii] += 1
            ascii_words_map[tuple(ascii_array)].append(word)
        
        return ascii_words_map.values()

Solution (easier)

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if len(strs) <= 1:
            return [strs]
        
        # sortされた文字列 -> オリジナルの文字列
        sorted_words_map = defaultdict(list)

        for word in strs:
            sorted_words_map[''.join(sorted(word))].append(word)
        
        return sorted_words_map.values()

5. Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Example 1:

Input: nums = [1,2,2,3,3,3], k = 2

Output: [2,3]

Example 2:

Input: nums = [7,7], k = 1

Output: [7]

Solution

from collections import Counter, defaultdict

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 数字 -> 数字の数のマップ
        num_count_map = Counter(nums)

        # 数字の数 -> 数字のリストマップ
        count_num_map = defaultdict(list)

        max_freq_count = 0
        for num, count in num_count_map.items():
            count_num_map[count].append(num)
            max_freq_count = max(max_freq_count, count)
        
        # 最も頻度の高かったカウントからdecrementしていき、
        # 該当する数字をk個resに追加していく
        count = max_freq_count
        res = []
        while count >= 0:
            if count in count_num_map:
                for num in count_num_map[count]:
                    k -= 1
                    res.append(num)
                    if k == 0:
                        return res

            count -= 1        

6. Encode and Decode Strings

Problem

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Please implement encode and decode

Example 1:

Input: ["neet","code","love","you"]

Output:["neet","code","love","you"]

Example 2:

Input: ["we","say",":","yes"]

Output: ["we","say",":","yes"]

Solution

class Solution:

    def encode(self, strs: List[str]) -> str:
        # 4#neet4#code4#love3#you のような形式でencodeする
        res = ''
        for s in strs:
            res += str(len(s)) + '#' + s
        return res

    def decode(self, s: str) -> List[str]:
        res = []
        i = 0
        while i < len(s):
            len_s = ''  # 追加する単語の長さを表す数字を格納
            while s[i] != '#':
                len_s += s[i]
                i += 1
            
            len_i = int(len_s) # intに変換
            res.append(s[i+1:i+len_i+1])
            i = i + len_i + 1
        
        return res

7. Product of Array Except Self

Problem

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Each product is guaranteed to fit in a 32-bit integer.

Follow-up: Could you solve it in O(n)

O(n) time without using the division operation?

Example 1:

Input: nums = [1,2,4,6]

Output: [48,24,12,8]

Example 2:

Input: nums = [-1,0,1,2,3]

Output: [0,-6,0,0,0]

Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_products = [1] * len(nums)
        right_products = [1] * len(nums)

        for i in range(1, len(nums)):
            left_products[i] = left_products[i-1] * nums[i-1]
        
        for i in range(len(nums)-2, -1, -1):
            right_products[i] = right_products[i+1] * nums[i+1]
        
        res = []
        for i in range(len(nums)):
            res.append(left_products[i] * right_products[i])
        
        return res

8. Valid Sudoku

Problem

You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

Each row must contain the digits 1-9 without duplicates.

Each column must contain the digits 1-9 without duplicates.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Example 1:

Input: board =

[["1","2",".",".","3",".",".",".","."],

["4",".",".","5",".",".",".",".","."],

[".","9","8",".",".",".",".",".","3"],

["5",".",".",".","6",".",".",".","4"],

[".",".",".","8",".","3",".",".","5"],

["7",".",".",".","2",".",".",".","6"],

[".",".",".",".",".",".","2",".","."],

[".",".",".","4","1","9",".",".","8"],

[".",".",".",".","8",".",".","7","9"]]

Output: true

Example 2:

Input: board =

[["1","2",".",".","3",".",".",".","."],

["4",".",".","5",".",".",".",".","."],

[".","9","1",".",".",".",".",".","3"],

["5",".",".",".","6",".",".",".","4"],

[".",".",".","8",".","3",".",".","5"],

["7",".",".",".","2",".",".",".","6"],

[".",".",".",".",".",".","2",".","."],

[".",".",".","4","1","9",".",".","8"],

[".",".",".",".","8",".",".","7","9"]]

Output: false

Explanation: There are two 1's in the top-left 3x3 sub-box.

Solution

from collections import defaultdict

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 0~8のrowとそれぞれに存在する数字を追加していく
        row_nums_map = defaultdict(set)

        # 0~8のcolとそれぞれに存在する数字を追加していく
        col_nums_map = defaultdict(set)

        # 0~8のboxとそれぞれに存在する数字を追加していく
        # boxは、row // 3, col // 3 のtupleがキーになる
        box_nums_map = defaultdict(set)

        for r in range(9):
            for c in range(9):
                num = board[r][c]
                if num == '.':
                    continue

                if (num in row_nums_map[r] or
                    num in col_nums_map[c] or
                    num in box_nums_map[(r // 3, c // 3)]
                    ):
                    return False
                
                row_nums_map[r].add(num)
                col_nums_map[c].add(num)
                box_nums_map[(r // 3, c // 3)].add(num)
        
        return True

9. Longest Consecutive Sequence

Problem

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

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element.

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

Example 1:

Input: nums = [2,20,4,10,3,4,5]

Output: 4

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Solution

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

        for num in nums:
            if (num - 1) not in nums_set:
                target_num = num
                count = 0
                while target_num in nums_set:
                    count += 1
                    longest = max(longest, count)
                    target_num += 1
        
        return longest