DenCT/test-storage / DSA Notes /Arrays and Hashing.md
DenCT's picture
|
download
raw
14.4 kB
metadata
tags:
  - notes
  - array-and-hashing

Contains Duplicate (LeetCode, NeetCode) EASY

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

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

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

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Solution:

Use a set/dictionary to store the elements of the array. If an element is present already, return True. At the end of loop return False. Code:

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

Valid Anagram (LeetCode, NeetCode) EASY

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.

Input: s = "racecar", t = "carrace"
Output: true

[!info] Time and Space Complexity You should aim for a solution with O(n + m) time and O(1) space, where n is the length of the string s and m is the length of the string t.

Solution:

Brute force

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s, t = sorted(s), sorted(t)
        return s == t

Simply sorting the characters of both the strings and comparing them for equality. It is of a O(nlogn + mlogm) time complexity. Optimal

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_len = len(s)
        t_len = len(t)

        if s_len != t_len:
            return False

        s_map, t_map = {}, {}
        for i in range(s_len):
            s_map[s[i]] = s_map.get(s[i], 0) + 1
            t_map[t[i]] = t_map.get(t[i], 0) + 1
        
        return s_map == t_map

Keep track of the count of character in the strings in s dictionary and return whether they are equal or not.

Two Sum (LeetCode) EASY

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array

Solution:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pairs = {}
        for i in range(len(nums)):
            if nums[i] in pairs:
                return [pairs[nums[i]], i]
            pairs[target - nums[i]] = i
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = dict()
        result = None
        for i, num in enumerate(nums):
            if res is not None and num in res:
                result = [res[num], i]
            else:
                res.update({target - num: i})
        return result

Keep a dictionary to store the target - num and index as key and value pairs. If a number from the list of numbers exist in the dictionary, return it’s index and the index corresponding to that number as key in the dictionary.

Group Anagrams (LeetCode) MEDIUM

Given an array of strings strs, group all anagrams together into sub-lists. 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.

Input: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Input: strs = ["x"]
Output: [["x"]]

[!info] Time and Space Complexity You should aim for a solution with O(m * n) time and O(m) space, where m is the number of strings and n is the length of the longest string.

Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[List[str]] = {}
        for word in strs:
            ref = "".join(sorted(word))
            if ref not in groups:
                groups.update({ref: [word]})
            else:
                groups[ref].append(word)
        return list(groups.values())

Set Matrix Zeros (LeetCode) MEDIUM

Given an m x n matrix of integers matrix, if an element is 0, set its entire row and column to 0's. You must update the matrix in-place. Follow up: Could you solve it using O(1) space?

Input: matrix = [
  [0,1],
  [1,1]
]

Output: [
  [0,0],
  [0,1]
]

Solution:

Brute Force Solution - O(m*n*(m+n))+O(m*n) time complexity

  1. Loop over each cell in the matrix.
  2. If a cell contains 0, loop over the row and column for that cell, i.e. if you are in cell 1, 2, loop over all columns in row 1 and all rows in column 2.
  3. Set all non-zero elements to -1 in the traversing row and column.
  4. Once the traverse is complete, traverse the matrix again and replace all -1 with 0.
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_len, col_len = len(matrix), len(matrix[0])
        for row in range(row_len):
            for col in range(col_len):
                if matrix[row][col] == 0:
                    for _col in range(col_len):
                        if matrix[row][_col] != 0:
                            matrix[row][_col] = -1
                    for _row in range(row_len):
                        if matrix[_row][col] != 0:
                            matrix[_row][col] = -1
        for row in range(row_len):
            for col in range(col_len):
                if matrix[row][col] == -1:
                    matrix[row][col] = 0

Optimized Solution - O(m*n)+O(m*n) time complexity, O(m+n) space complexity

  1. Create two 1-D arrays, one of the length of row and one of the length of column.
  2. Loop over each cell in the matrix.
  3. If a cell contains 0, mark the index in row array with -1 at the row index from the matrix, and same with column array. E.g. if there is a 0 in cell 1,2, mark -1 in 1 index of row array and 2 index of column array
  4. Repeat step 3 for all elements in the matrix.
  5. Once the traverse is complete, traverse the matrix again and replace the cells with 0 if the row index of that cell has -1 in the particular index in row array or column index has -1 in the particular index in column array.
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_, col_ = [0] * len(matrix), [0] * len(matrix[0])
        row_len, col_len = len(matrix), len(matrix[0])

        for row in range(row_len):
            for col in range(col_len):
                if matrix[row][col] == 0:
                    row_[row], col_[col] = -1, -1
        
        for row in range(row_len):
            for col in range(col_len):
                if row_[row] == -1 or col_[col] == -1:
                    matrix[row][col] = 0
  • Best Approach - O(m*n) time complexity, O(1) space complexity
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False

        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True

        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0

        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0

Top K Frequent Elements (Leetcode) MEDIUM

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.

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

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

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array

Solution

Brute Force

  1. Keep a dictionary to store count of each element in the array
  2. Sort the dictionary based on the values/counts from the dictionary, and return the k top counts from the list.
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res = {}
        for num in nums:
            res[num] = res.get(num, 0) + 1
        return [key for key, val in sorted(res.items(), key=lambda x: x[1], reverse=True)][:k]  

Optimized

  1. First, keep a counter for items of the list. This will have all the item and their counts in the list.
  2. Then create an empty list of list, with index being the counts from 0 to n + 1 . This will group the items from the list based on their counts. E.g.: if list is [1,2,4,4,3,3,3] the empty list should finally be [[],[1,2],[4],[3],[]...[]] .
  3. Finally, we need to loop the dictionary from behind and over each list in the dictionary. Append each item into the res list until the size of res list is equal to k.
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = [[] for _ in range(len(nums) + 1)]
        itemCounts = collections.Counter(nums)
        
        for item, count in itemCounts.items():
            counts[count].append(item)
        res = []
        for i in range(len(counts) - 1, 0, -1):
            for item in counts[i]:
                res.append(item)
                if len(res) == k:
                    return res
## Using min-heap
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequency_map = {}
        for num in nums:
            frequency_map[num] = frequency_map.get(num, 0) + 1
        min_heap = []
        for num, frequency in frequency_map.items():
            heapq.heappush(min_heap, (frequency, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return [num for frequency, num in min_heap]

Products of Array Except Self [MEDIUM]

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

[!info] Time and Space complexity Time = O(n); Space = O(n)

Solution

By Division

  1. We start by calculating the product of all elements in the array. While calculating product of elements, zeroes are excluded and the zeroes count is stored in a variable.
  2. Next, the zeroes count is checked. If the zero count is more than ‘one’, the result will be a list of zeroes. A list of length of size of the input array is returned.
  3. If the above case passes, then an array of size of the input array is created, and filled with zeroes.
  4. Loop over the elements of the input array. If the item at current index is non-zero, add the product // num if zero count is < 1 else put 0 to the result array at that index. If the item is zero: put product at the index.
  5. Finally return the result.
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prod = 1
        zero_count = 0
        for num in nums:
            if num != 0:
                prod *= num
            else:
                zero_count += 1
        if zero_count > 1: return [0] * len(nums)
        res = [0] * len(nums)

        for idx, num in enumerate(nums):
            if num:
                res[idx] = prod // num if zero_count < 1 else 0
            else:
                res[idx] = prod 
        return res

Prefix and Post-fix To solve this problem, we can first calculate the product of all elements to the left of each index and store it in a list. Then, we calculate the product of all elements to the right of each index and update the result list accordingly by multiplying it with the previously calculated left product. In this way, each element in the result list will contain the product of all elements except the one at that index.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        # Calculate the left product of each element
        left_product = 1
        for i in range(n):
            result[i] *= left_product
            left_product *= nums[i]
        # Calculate the right product of each element and update the result list
        right_product = 1
        for i in range(n - 1, -1, -1):
            result[i] *= right_product
            right_product *= nums[i]
        return result

Longest Consecutive Sequence MEDIUM

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:
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:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:
Input: nums = [1,0,1,2]
Output: 3

Solution:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_length = 0
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_length = 1
                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1
                max_length = max(max_length, current_length)
        return max_length

NEXT: [[DSA Notes/Two Pointers]]

Xet Storage Details

Size:
14.4 kB
·
Xet hash:
cc2fe0cdabf90bd9fd84b60d11fe3e7a58ed8f5c9280c05397f5e611e4ab2e62

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.