🌱 Phase 1 — Foundations (Days 1–15)

# Build prefix sum
def prefix_sum(nums):
    prefix = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        prefix[i+1] = prefix[i] + nums[i]
    # Sum from l to r (inclusive) = prefix[r+1] - prefix[l]
    return prefix
 
# Subarray sum equals k (use hashmap of prefix sums)
def subarraySum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}  # prefix_sum -> frequency
    for n in nums:
        prefix += n
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

# Two sum in sorted array
def twoSumSorted(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target: return [l+1, r+1]
        elif s < target: l += 1
        else: r -= 1
    return []
 
# 3Sum (sort + two pointer for inner loop)
def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip duplicates
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                result.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0: l += 1
            else: r -= 1
    return result
 
# Valid palindrome
def isPalindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]: return False
        l += 1; r -= 1
    return True

# Fixed window: max sum of k consecutive elements
def maxSumFixedWindow(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # slide
        max_sum = max(max_sum, window_sum)
    return max_sum
 
# Variable window: longest substring without repeating characters
def lengthOfLongestSubstring(s):
    char_set = set()
    l = max_len = 0
    for r in range(len(s)):
        while s[r] in char_set:   # shrink window until valid
            char_set.remove(s[l])
            l += 1
        char_set.add(s[r])
        max_len = max(max_len, r - l + 1)
    return max_len
 
# Variable window with hashmap: minimum window substring
def minWindow(s, t):
    need = {}
    for c in t: need[c] = need.get(c, 0) + 1
    have, total = 0, len(need)
    window = {}
    l = 0
    res = ""
    for r in range(len(s)):
        c = s[r]
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]: have += 1
        while have == total:
            if not res or r - l + 1 < len(res):
                res = s[l:r+1]
            window[s[l]] -= 1
            if s[l] in need and window[s[l]] < need[s[l]]: have -= 1
            l += 1
    return res

# Classic binary search
def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2  # avoid overflow
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1
 
# Find leftmost position
def searchLeft(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] < target: l = mid + 1
        else: r = mid
    return l
 
# Search in rotated sorted array
def searchRotated(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target: return mid
        if nums[l] <= nums[mid]:  # left half is sorted
            if nums[l] <= target < nums[mid]: r = mid - 1
            else: l = mid + 1
        else:                     # right half is sorted
            if nums[mid] < target <= nums[r]: l = mid + 1
            else: r = mid - 1
    return -1
 
# Binary search on answer: minimum capacity to ship packages in D days
def shipWithinDays(weights, days):
    def canShip(capacity):
        ships, cur = 1, 0
        for w in weights:
            if cur + w > capacity:
                ships += 1; cur = 0
            cur += w
        return ships <= days
 
    l, r = max(weights), sum(weights)
    while l < r:
        mid = (l + r) // 2
        if canShip(mid): r = mid
        else: l = mid + 1
    return l

# Custom sort
nums.sort(key=lambda x: (-x[0], x[1]))  # sort by first desc, second asc
 
# Merge intervals
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged
 
# Meeting rooms II (min heap)
import heapq
def minMeetingRooms(intervals):
    intervals.sort()
    heap = []  # end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)