Coding Easy: Arrays & Strings
Difficulty: Easy-Medium | Companies: Google, Meta, Amazon, Netflix, Stripe
Two Sum Pattern
from typing import List, Dict
def two_sum(nums: List[int], target: int) -> List[int]:
"""Find two numbers that add up to target.
Time: O(n), Space: O(n)
"""
num_map: Dict[int, int] = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return []
def two_sum_sorted(numbers: List[int], target: int) -> List[int]:
"""Two Sum in sorted array using two pointers.
Time: O(n), Space: O(1)
"""
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
# Test cases
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum_sorted([2, 7, 11, 15], 9)) # [0, 1]
βΉοΈ
The hash map approach trades space for time. For sorted arrays, two pointers gives O(1) space.
Array Manipulation
from typing import List
from collections import Counter
def remove_duplicates(nums: List[int]) -> int:
"""Remove duplicates in-place from sorted array.
Time: O(n), Space: O(1)
"""
if not nums:
return 0
write_index = 1
for read_index in range(1, len(nums)):
if nums[read_index] != nums[read_index - 1]:
nums[write_index] = nums[read_index]
write_index += 1
return write_index
def max_subarray_sum(nums: List[int]) -> int:
"""Find maximum subarray sum (Kadane's algorithm).
Time: O(n), Space: O(1)
"""
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
def rotate_array(nums: List[int], k: int) -> None:
"""Rotate array to the right by k steps.
Time: O(n), Space: O(1)
"""
n = len(nums)
k = k % n
def reverse(start: int, end: int):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
def best_time_to_buy_sell(prices: List[int]) -> int:
"""Find maximum profit from buying and selling once.
Time: O(n), Space: O(1)
"""
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
# Test cases
arr = [1, 1, 2, 2, 3]
new_length = remove_duplicates(arr)
print(arr[:new_length]) # [1, 2, 3]
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(best_time_to_buy_sell([7, 1, 5, 3, 6, 4])) # 5
String Operations
def is_palindrome(s: str) -> bool:
"""Check if string is palindrome (alphanumeric only).
Time: O(n), Space: O(1)
"""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
def reverse_string(s: List[str]) -> None:
"""Reverse string in-place using two pointers.
Time: O(n), Space: O(1)
"""
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
def longest_substring_without_repeating(s: str) -> int:
"""Find length of longest substring without repeating chars.
Time: O(n), Space: O(min(m, n)) where m is charset size
"""
char_index = {}
max_length = 0
start = 0
for end, char in enumerate(s):
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
char_index[char] = end
max_length = max(max_length, end - start + 1)
return max_length
def valid_anagram(s: str, t: str) -> bool:
"""Check if t is an anagram of s.
Time: O(n), Space: O(1) - fixed charset
"""
if len(s) != len(t):
return False
char_count = [0] * 26
for i in range(len(s)):
char_count[ord(s[i]) - ord('a')] += 1
char_count[ord(t[i]) - ord('a')] -= 1
return all(count == 0 for count in char_count)
def group_anagrams(strs: List[str]) -> List[List[str]]:
"""Group strings that are anagrams of each other.
Time: O(n * k log k), Space: O(n * k)
"""
anagram_map = {}
for s in strs:
sorted_key = ''.join(sorted(s))
if sorted_key not in anagram_map:
anagram_map[sorted_key] = []
anagram_map[sorted_key].append(s)
return list(anagram_map.values())
# Test cases
print(is_palindrome("A man, a plan, a canal: Panama")) # True
print(longest_substring_without_repeating("abcabcbb")) # 3
print(valid_anagram("anagram", "nagaram")) # True
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
β οΈ
Always clarify if the string contains Unicode characters. The solution may differ for ASCII-only vs Unicode strings.
Stack and Queue Patterns
from typing import List
from collections import deque
def valid_parentheses(s: str) -> bool:
"""Check if parentheses are valid.
Time: O(n), Space: O(n)
"""
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
def min_stack:
"""Stack that supports getMin() in O(1) time."""
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> int:
if not self.stack:
raise IndexError("Stack is empty")
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self) -> int:
if not self.stack:
raise IndexError("Stack is empty")
return self.stack[-1]
def get_min(self) -> int:
if not self.min_stack:
raise IndexError("Stack is empty")
return self.min_stack[-1]
def daily_temperatures(temperatures: List[int]) -> List[int]:
"""Find number of days until warmer temperature.
Time: O(n), Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
def implement_queue_using_stacks:
"""Queue implementation using two stacks."""
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
self._shift()
return self.stack_out.pop()
def peek(self) -> int:
self._shift()
return self.stack_out[-1]
def empty(self) -> bool:
return not self.stack_in and not self.stack_out
def _shift(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
# Test cases
print(valid_parentheses("()[]{}")) # True
print(valid_parentheses("(]")) # False
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])) # [1,1,4,2,1,1,0,0]
Hash Map Patterns
from typing import List, Dict, Optional
from collections import defaultdict
def ransom_note(magazine: str, ransom: str) -> bool:
"""Check if ransom note can be constructed from magazine.
Time: O(n + m), Space: O(1) - fixed charset
"""
char_count = defaultdict(int)
for char in magazine:
char_count[char] += 1
for char in ransom:
if char_count[char] <= 0:
return False
char_count[char] -= 1
return True
def top_k_frequent(nums: List[int], k: int) -> List[int]:
"""Find k most frequent elements.
Time: O(n), Space: O(n)
"""
count = Counter(nums)
bucket = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
bucket[freq].append(num)
result = []
for i in range(len(bucket) - 1, 0, -1):
for num in bucket[i]:
result.append(num)
if len(result) == k:
return result
return result
def encode_decode_strings:
"""Encode and decode strings using delimiters."""
@staticmethod
def encode(strs: List[str]) -> str:
"""Encode list of strings to single string."""
return ''.join(f"{len(s)}#{s}" for s in strs)
@staticmethod
def decode(s: str) -> List[str]:
"""Decode single string to list of strings."""
result = []
i = 0
while i < len(s):
j = s.index('#', i)
length = int(s[i:j])
result.append(s[j + 1:j + 1 + length])
i = j + 1 + length
return result
def two_array_intersection(nums1: List[int], nums2: List[int]) -> List[int]:
"""Find intersection of two arrays.
Time: O(n + m), Space: O(min(n, m))
"""
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
num_set = set(nums1)
result = []
for num in nums2:
if num in num_set:
result.append(num)
num_set.remove(num)
return result
# Test cases
print(ransom_note("aa", "ab")) # False
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # [1, 2]
encoded = encode_decode_strings.encode(["hello", "world", "python"])
print(encoded) # 5#hello5#world6#python
print(decode(encoded)) # ["hello", "world", "python"]
βΉοΈ
For hash map problems, consider the trade-off between time and space complexity. Sometimes a sorting approach might be more space-efficient.
Sliding Window
from typing import List
def max_average_subarray(nums: List[int], k: int) -> float:
"""Find maximum average of subarray of size k.
Time: O(n), Space: O(1)
"""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k
def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
"""Find length of longest substring with at most k distinct chars.
Time: O(n), Space: O(k)
"""
if k == 0:
return 0
char_count = {}
max_length = 0
start = 0
for end, char in enumerate(s):
char_count[char] = char_count.get(char, 0) + 1
while len(char_count) > k:
left_char = s[start]
char_count[left_char] -= 1
if char_count[left_char] == 0:
del char_count[left_char]
start += 1
max_length = max(max_length, end - start + 1)
return max_length
def minimum_window_substring(s: str, t: str) -> str:
"""Find minimum window in s containing all chars of t.
Time: O(n), Space: O(k) where k is charset size
"""
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
char = s[r]
window_counts[char] = window_counts.get(char, 0) + 1
if char in dict_t and window_counts[char] == dict_t[char]:
formed += 1
while l <= r and formed == required:
char = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[char] -= 1
if char in dict_t and window_counts[char] < dict_t[char]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]
# Test cases
print(max_average_subarray([1, 12, -5, -6, 50, 3], 4)) # 12.75
print(length_of_longest_substring_k_distinct("eceba", 2)) # 3
print(minimum_window_substring("ADOBECODEBANC", "ABC")) # "BANC"
Follow-Up Questions
-
How would you modify Two Sum to find all pairs?
-
Explain the time complexity of Kadane's algorithm.
-
When would you use a hash map over two pointers?
-
How do you handle duplicate elements in array problems?
-
What are the trade-offs between sliding window and two pointers?