Day 14 — Practice + Poll

1) Pair With Target Sum (Two Pointers)

Problem: Given a sorted array and a target, return indices (0-based) of two numbers whose sum is the target, or -1 -1 if none.

nums = [1,2,3,4,6], target = 6 → (1,3)  # 2+4

def two_sum_sorted(nums, target):
    i, j = 0, len(nums)-1
    while i < j:
        s = nums[i] + nums[j]
        if s == target: return i, j
        if s < target: i += 1
        else: j -= 1
    return -1, -1

2) Container With Most Water (Two Pointers)

Problem: Given heights, find max area formed between two lines.

def max_area(height):
    i, j, best = 0, len(height)-1, 0
    while i < j:
        h = min(height[i], height[j])
        best = max(best, h * (j - i))
        if height[i] < height[j]: i += 1
        else: j -= 1
    return best

3) Max Sum Subarray of Size K (Sliding Window)

Problem: Return the maximum sum of any contiguous subarray of size k.

def max_sum_subarray_of_size_k(nums, k):
    window = sum(nums[:k]); best = window
    for r in range(k, len(nums)):
        window += nums[r] - nums[r-k]
        best = max(best, window)
    return best

4) Minimum Window Substring (Sliding Window)

Problem: Given strings s and t, return the minimum window of s that contains all characters of t.

from collections import defaultdict

def min_window(s, t):
    if not s or not t: return ""
    need = defaultdict(int)
    for ch in t: need[ch] += 1
    required = len(need); have = 0
    window = defaultdict(int)
    best_len = float('inf'); best = (0, 0)
    left = 0
    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]: have += 1
        while have == required:
            if right-left+1 < best_len:
                best_len = right-left+1; best = (left, right)
            left_ch = s[left]; window[left_ch] -= 1
            if left_ch in need and window[left_ch] < need[left_ch]: have -= 1
            left += 1
    return "" if best_len == float('inf') else s[best[0]:best[1]+1]

5) Fruit Into Baskets (≤ 2 Distinct)

Problem: Longest subarray with at most two distinct integers.

from collections import defaultdict

def total_fruit(nums):
    count = defaultdict(int); left = 0; best = 0
    for right, x in enumerate(nums):
        count[x] += 1
        while len(count) > 2:
            y = nums[left]; count[y] -= 1
            if count[y] == 0: del count[y]
            left += 1
        best = max(best, right-left+1)
    return best

6) Longest Ones After K Flips

Problem: Given a binary array and k, return longest subarray length after flipping at most k zeros.

def longest_ones(nums, k):
    left = 0; zeros = 0; best = 0
    for right, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > k:
            if nums[left] == 0: zeros -= 1
            left += 1
        best = max(best, right-left+1)
    return best

7) Subarray Product < K (positives)

Problem: Count contiguous subarrays with product < k. Assume all numbers > 0; if k ≤ 1, answer is 0.

def num_subarray_product_less_than_k(nums, k):
    if k <= 1: return 0
    prod = 1; left = 0; total = 0
    for right, x in enumerate(nums):
        prod *= x
        while prod >= k:
            prod //= nums[left]
            left += 1
        total += right-left+1
    return total

8) Smallest Subarray With Sum ≥ S (positives)

Problem: Return minimal length of a contiguous subarray with sum ≥ S; return 0 if none.

def min_subarray_len(nums, S):
    left = 0; s = 0; best = float('inf')
    for right, x in enumerate(nums):
        s += x
        while s >= S:
            best = min(best, right-left+1)
            s -= nums[left]
            left += 1
    return 0 if best == float('inf') else best

9) Subarray Sum Equals K (Prefix Sums + Hash)

Problem: Count the number of subarrays whose sum equals k. Works with negatives.

from collections import defaultdict

def subarray_sum(nums, k):
    freq = defaultdict(int); freq[0] = 1
    s = 0; count = 0
    for x in nums:
        s += x
        count += freq[s - k]
        freq[s] += 1
    return count

10) Range Sum Query – Immutable (Prefix Sums)

Problem: Precompute prefix sums to answer sum(l..r) queries in O(1).

class NumArray:
    def __init__(self, nums):
        self.pref = [0]
        for v in nums: self.pref.append(self.pref[-1] + v)
    def sumRange(self, l, r):
        return self.pref[r+1] - self.pref[l]