DenCT/test-storage / DSA Notes /Arrays and Hashing.md
DenCT's picture
|
download
raw
14.4 kB
---
tags:
- notes
- array-and-hashing
---
### **Contains Duplicate ([LeetCode](https://leetcode.com/problems/contains-duplicate/description/), [NeetCode](https://neetcode.io/problems/duplicate-integer)) 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**:
```python
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](https://leetcode.com/problems/valid-anagram/description/), [NeetCode](https://neetcode.io/problems/is-anagram)) 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**
```python
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**
```python
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](https://leetcode.com/problems/two-sum/description/)) 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:
```python
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
```
```python
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](https://leetcode.com/problems/group-anagrams/description/)) 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
```python
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](https://leetcode.com/problems/set-matrix-zeroes/description/)) 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.
```python
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.
```python
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**
```python
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](https://leetcode.com/problems/top-k-frequent-elements/description/)) 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.
```python
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.
```python
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
```
```python
## 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.
```python
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.
```python
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](https://leetcode.com/problems/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.
```python
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**:
```python
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.