02 — Arrays, Hashing, Two Pointers, Sliding Window#

# SHAPE A: seen-set — "have I encountered this?"
def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False
# O(n) time, O(n) space
# One-liner: return len(set(nums)) != len(nums)
 
# SHAPE B: value → index map — "where did I see this?"
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
 
# SHAPE C: frequency map — "how many times?"
from collections import Counter, defaultdict
def top_k_frequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

# Group Anagrams. Two words are anagrams iff their sorted letters match.
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))        # canonical form — O(k log k)
        groups[key].append(s)
    return list(groups.values())
# O(n * k log k), n = words, k = max word length
 
# Faster key: a 26-length count tuple → O(n*k), no sort
def group_anagrams_fast(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)   # lists aren't hashable — tuple() them
    return list(groups.values())

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:        # x is not the start of a run — skip it
            continue
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

# prefix[i] = sum of nums[0..i-1]
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix
 
# sum(nums[i..j]) inclusive = prefix[j+1] - prefix[i]

# Subarray Sum Equals K — count subarrays summing to k
def subarray_sum(nums, k):
    count = 0
    running = 0
    seen = {0: 1}          # a prefix sum of 0 has occurred once (empty prefix)
    for x in nums:
        running += x
        # if some earlier prefix equals running - k, the subarray between
        # that point and here sums to exactly k
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count
# O(n) time, O(n) space

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    prefix = 1
    for i in range(n):            # out[i] = product of everything LEFT of i
        out[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):  # multiply in everything RIGHT of i
        out[i] *= suffix
        suffix *= nums[i]
    return out
# O(n) time, O(1) extra space (output doesn't count)

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1        # need a bigger sum → move the small side up
        else:
            hi -= 1        # need a smaller sum → move the big side down
    return []
# O(n) time, O(1) space

# Remove duplicates from a sorted array, in place, return new length
def remove_duplicates(nums):
    if not nums: return 0
    write = 1                        # next slot to write into
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write
 
# Move all zeroes to the end, preserve order, in place
def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

def three_sum(nums):
    nums.sort()                       # O(n log n)
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:               # sorted: no way to reach 0 from here
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue                  # skip duplicate anchors
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                # skip duplicates on the left side
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return res
# O(n²) time (n anchors × O(n) scan), O(1) extra space beyond output

def max_area(height):
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        best = max(best, min(height[lo], height[hi]) * (hi - lo))
        if height[lo] < height[hi]:
            lo += 1              # move the SHORTER line inward
        else:
            hi -= 1
    return best

def fixed_window(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]   # add new, drop old
        best = max(best, window_sum)
    return best

def length_of_longest_substring(s):
    last = {}          # char -> most recent index
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1      # jump left past the previous occurrence
        last[c] = right
        best = max(best, right - left + 1)
    return best
# O(n) time, O(min(n, alphabet)) space

def character_replacement(s, k):
    count = {}
    left = 0
    max_freq = 0
    best = 0
    for right, c in enumerate(s):
        count[c] = count.get(c, 0) + 1
        max_freq = max(max_freq, count[c])
        while (right - left + 1) - max_freq > k:     # too many replacements
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

from collections import Counter
 
def min_window(s, t):
    if not s or not t:
        return ""
    need = Counter(t)
    have = {}
    required = len(need)      # distinct chars we must satisfy
    formed = 0                # how many are currently satisfied
    left = 0
    best_len = float('inf')
    best_range = (0, 0)
 
    for right, c in enumerate(s):
        have[c] = have.get(c, 0) + 1
        if c in need and have[c] == need[c]:
            formed += 1
 
        while formed == required:            # valid — try to shrink
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_range = (left, right)
            lc = s[left]
            have[lc] -= 1
            if lc in need and have[lc] < need[lc]:
                formed -= 1                  # no longer valid
            left += 1
 
    return "" if best_len == float('inf') else s[best_range[0]:best_range[1] + 1]
# O(|s| + |t|) time, O(|s| + |t|) space

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()      # indices, values decreasing front→back
    out = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:      # drop indices outside the window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:   # anything smaller than x is useless
            dq.pop()                       # — x is newer AND bigger
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])        # front is always the max
    return out
# O(n) — each index enters and leaves the deque exactly once