-
Two Sum
- Given array & target, return indices of two numbers that sum to target.
- store elements in map, key is number value is index of number in original array nums
- enumerate(list) → [index, object], [i, x], …
def two_sum(nums: List[int], target: int) -> List[int]:
m = {}
for i, x in enumerate(nums):
if target - x in m:
return [m[target - x], i]
m[x] = i
return []
-
Best Time to Buy and Sell Stock
- You are given an array
prices where prices[i] is the price of a given stock on the ith day.
- You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
- Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return
0.
- Track the lowest price seen so far → best buy point so far.
- At each day, compute the profit if you sold TODAY:
- Keep the maximum such profit.
- find lowest num → min(float(’inf’)), x)
- find largest num → max(0, x)
def max_profit(prices: List[int]) -> int:
min_price, max_profit = float('inf'), 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price)
return max_profit
-
Valid Anagram
- Check if two strings are anagrams.
- Anagram → Two strings contain the exact same characters with the exact same frequencies, just possibly in a different order.
Counter class (from collections) creates a hashmap/dictionary where:
- keys = characters
- values = how many times each character appears
def is_anagram(s: str, t:str) -> bool:
return Counter(s) == Counter(t)
-
Remove Duplicates from Sorted Array
- Return new length after removing duplicates in-place.
-
String Compression
- Compress array of chars (e.g.,
aabbccc → a2b2c3).