Python Arrays,
from index 0 to O(log n).

Python has no native fixed-size array type for general use — the built-in list is the workhorse. Use list comprehensions to avoid the classic shared-reference bug.

# Literal
a = [1, 2, 3, 4, 5]

# Repeated value (safe for immutables)
zeros = [0] * 5                     # [0, 0, 0, 0, 0]

# List comprehension (preferred for anything computed)
squares = [i * i for i in range(5)] # [0, 1, 4, 9, 16]

# From range / generator
nums = list(range(10))

# array module (typed, memory-efficient, C-style)
from array import array
typed = array('i', [1, 2, 3])       # 'i' = signed int

Indexing is O(1) because lists are backed by contiguous pointer arrays. Negative indices count from the end.

a = [10, 20, 30, 40, 50]
first, last = a[0], a[-1]           # 10, 50
a[1] = 99                           # update in place -> [10, 99, 30, 40, 50]

# Safe access with default
def get(arr, i, default=None):
    return arr[i] if 0 <= i < len(arr) else default

print(get(a, 10, -1))               # -1, no IndexError

Slicing a[start:stop:step] always returns a NEW list. Omit either bound to go to the start/end; negative step reverses.

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a[2:5]      # [2, 3, 4]
a[:3]       # [0, 1, 2]
a[7:]       # [7, 8, 9]
a[::2]      # [0, 2, 4, 6, 8]   every other element
a[::-1]     # reversed copy, does NOT mutate a
a[-3:]      # last 3 elements

# Slice assignment can grow/shrink the list
a[1:3] = [100, 200, 300]  # replaces 2 elements with 3

Know the complexity of each mutator: append/pop-at-end are amortized O(1); insert/pop-at-front are O(n) because everything shifts.

a = [1, 2, 3]
a.append(4)          # [1, 2, 3, 4]        O(1) amortized
a.insert(0, 0)        # [0, 1, 2, 3, 4]     O(n) - shifts everyone right
a.extend([5, 6])      # [0,1,2,3,4,5,6]     O(k)
a.remove(3)            # removes FIRST value 3, O(n)
last = a.pop()          # remove & return last, O(1)
first = a.pop(0)         # remove & return index 0, O(n)
a.clear()                 # empty the list, O(n)

The #1 beginner bug: `b = a` does NOT copy, it aliases. Use slicing/list()/copy() for shallow copies and copy.deepcopy for nested structures.

a = [1, 2, 3]
b = a               # ALIAS - mutating b mutates a!
b.append(4)
print(a)             # [1, 2, 3, 4]  <- surprise

c = a[:]              # shallow copy - new outer list
c = list(a)            # same effect
c = a.copy()

# Nested lists need deepcopy or the inner lists still alias
import copy
grid = [[0, 0], [0, 0]]
grid_copy = copy.deepcopy(grid)

NEVER build a 2D array with `[[0]*cols]*rows` — that repeats the SAME inner list reference `rows` times. Use a list comprehension instead.

rows, cols = 3, 4

# WRONG - all rows alias the same list
bad = [[0] * cols] * rows
bad[0][0] = 1
print(bad)   # [[1,0,0,0],[1,0,0,0],[1,0,0,0]]  every row changed!

# RIGHT - fresh list per row
grid = [[0] * cols for _ in range(rows)]
grid[0][0] = 1
print(grid)  # only row 0 changes

# 3D
cube = [[[0] * cols for _ in range(rows)] for _ in range(2)]

`str.split()` and `str.join()` are the two workhorses for moving between arrays and strings; both run in linear time.

s = "the quick brown fox"
words = s.split()                 # ['the', 'quick', 'brown', 'fox']
back = " ".join(words)             # "the quick brown fox"

digits = list("12345")              # ['1','2','3','4','5']
nums = [int(c) for c in "12345"]     # [1,2,3,4,5]
joined_nums = "".join(map(str, [1,2,3]))  # "123"

Lean on built-ins — they're implemented in C and almost always faster than a hand-rolled Python loop.

a = [5, 3, 8, 1, 9, 2]
sum(a)                 # 28
min(a); max(a)          # 1, 9
sorted(a)                # [1,2,3,5,8,9]  new list, stable sort
sorted(a, reverse=True)   # descending
sum(x for x in a if x % 2 == 0)  # sum of evens = 14
max(a, key=lambda x: -x)          # min via key trick

`enumerate` avoids the anti-pattern `for i in range(len(a)): a[i]`. Supports a custom start index.

a = ["a", "b", "c"]
for i, v in enumerate(a):
    print(i, v)          # 0 a / 1 b / 2 c

for i, v in enumerate(a, start=1):
    print(i, v)           # 1 a / 2 b / 3 c

pos = {v: i for i, v in enumerate(a)}   # value -> index map

`zip` pairs up multiple arrays and stops at the shortest one. Great for element-wise operations without index bookkeeping.

names = ["a", "b", "c"]
scores = [90, 85, 77]
for n, s in zip(names, scores):
    print(n, s)

# Element-wise sum of two arrays
a, b = [1, 2, 3], [10, 20, 30]
summed = [x + y for x, y in zip(a, b)]   # [11, 22, 33]

# Transpose a matrix
matrix = [[1, 2, 3], [4, 5, 6]]
transposed = [list(row) for row in zip(*matrix)]

Star expressions let you peel off the head/tail of an array without slicing manually.

first, *middle, last = [1, 2, 3, 4, 5]
# first=1, middle=[2,3,4], last=5

a, b, *rest = [1, 2, 3, 4]
# a=1, b=2, rest=[3,4]

def total(*nums):     # collects args into a tuple
    return sum(nums)
total(1, 2, 3)          # unpacks a call site: total(*[1,2,3])

Choosing the right container matters for interview follow-ups: deque gives O(1) pops from both ends; NumPy gives vectorized math on fixed-type data.

from collections import deque
import array as arr

py_list = [1, 2, 3]              # general purpose, dynamic, heterogeneous
typed_arr = arr.array('i', [1, 2, 3])  # homogeneous, compact, still O(n) insert
dq = deque([1, 2, 3])              # O(1) append/pop at BOTH ends
dq.appendleft(0); dq.popleft()

# NumPy: contiguous, vectorized, but a separate import - mention if asked
# import numpy as np
# np.array([1, 2, 3]) * 2   ->  vectorized, no Python-level loop

Single pass, track a running streak and reset to 0 on a zero.

def findMaxConsecutiveOnes(nums):
    best = cur = 0
    for n in nums:
        cur = cur + 1 if n == 1 else 0
        best = max(best, cur)
    return best

The naive O(n^2) baseline before the hash-map optimization shown in the Hashing section — good to state out loud in an interview before optimizing.

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Use a write pointer `k`: whenever the current value isn't the target, copy it forward and advance k.

def removeElement(nums, val):
    k = 0
    for n in nums:
        if n != val:
            nums[k] = n
            k += 1
    return k   # nums[:k] is the answer

Since the array is sorted, duplicates are adjacent. Keep a slow pointer for the last unique value written.

def removeDuplicates(nums):
    if not nums:
        return 0
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return k

Simulate elementary-school addition from the last digit, propagating carry; if every digit was 9, prepend a 1.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

Classic index-as-hash-set trick: for each value v, negate the element at index v-1 to mark it seen; unmarked positions are the missing numbers.

def findDisappearedNumbers(nums):
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] > 0:
            nums[idx] *= -1
    return [i + 1 for i, n in enumerate(nums) if n > 0]

Same write-pointer pattern as Remove Element, then fill the remaining tail with zeros in one more pass.

def moveZeroes(nums):
    k = 0
    for n in nums:
        if n != 0:
            nums[k] = n
            k += 1
    for i in range(k, len(nums)):
        nums[i] = 0

The elegant O(1)-space solution: reverse the whole array, then reverse each of the two segments separately.

def rotate(nums, k):
    n = len(nums)
    k %= n
    def reverse(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1; r -= 1
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

Maintain a candidate and a counter; the majority element (appears > n/2 times) always survives the cancellation process.

def majorityElement(nums):
    candidate, count = None, 0
    for n in nums:
        if count == 0:
            candidate = n
        count += 1 if n == candidate else -1
    return candidate

A hash set catches duplicates in one pass; short-circuit as soon as a repeat is found.

def containsDuplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False
    # one-liner alt: return len(nums) != len(set(nums))

Because the array is sorted, start pointers at both ends: if the sum is too big, shrink from the right; too small, grow from the left.

def twoSum(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]   # 1-indexed
        elif s < target:
            l += 1
        else:
            r -= 1
    return []

Sort first, then fix one number and run the two-pointer 2Sum on the rest. Skip duplicate values at every level to avoid repeat triplets.

def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return res

Same skeleton as 3Sum, but track the running closest sum instead of collecting exact matches.

def threeSumClosest(nums, target):
    nums.sort()
    best = nums[0] + nums[1] + nums[2]
    n = len(nums)
    for i in range(n - 2):
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if abs(s - target) < abs(best - target):
                best = s
            if s == target:
                return s
            elif s < target:
                l += 1
            else:
                r -= 1
    return best

Generalize 3Sum by fixing two numbers with nested loops, then two-pointer the remainder. Prune with duplicate skipping and bounds checks.

def fourSum(nums, target):
    nums.sort()
    n, res = len(nums), []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            l, r = j + 1, n - 1
            while l < r:
                s = nums[i] + nums[j] + nums[l] + nums[r]
                if s == target:
                    res.append([nums[i], nums[j], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                elif s < target:
                    l += 1
                else:
                    r -= 1
    return res

Start with the widest container. Always move the pointer at the SHORTER line inward — moving the taller one can never improve the area.

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

Track running max height from each side. Whichever side has the smaller max determines how much water the current column traps.

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

Skip non-alphanumeric characters from both ends while comparing lowercase letters.

def isPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1; r -= 1
    return True

Swap from both ends toward the middle — the textbook in-place reversal.

def reverseString(s):
    l, r = 0, len(s) - 1
    while l < r:
        s[l], s[r] = s[r], s[l]
        l += 1; r -= 1

Three pointers (low, mid, high) partition the array into 0s, 1s, and 2s in a single pass without counting sort.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Negative numbers become large positives when squared, so the biggest squares live at the extremes. Fill the result array from the back.

def sortedSquares(nums):
    n = len(nums)
    res = [0] * n
    l, r = 0, n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[l]) > abs(nums[r]):
            res[i] = nums[l] ** 2
            l += 1
        else:
            res[i] = nums[r] ** 2
            r -= 1
    return res

Merge from the BACK of nums1 (which has extra trailing space) so you never overwrite un-read values.

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]; i -= 1
        else:
            nums1[k] = nums2[j]; j -= 1
        k -= 1

Two pointers walking forward: advance the source pointer every step, and the pattern pointer only on a match.

def isSubsequence(s, t):
    i = 0
    for c in t:
        if i < len(s) and s[i] == c:
            i += 1
    return i == len(s)

Fixed-size window: compute the first window's sum, then slide by subtracting the outgoing element and adding the incoming one.

def findMaxAverage(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best / k

Variable-size window: grow the right edge to accumulate sum, then shrink from the left while the sum still meets the target.

def minSubArrayLen(target, nums):
    l = total = 0
    best = float('inf')
    for r, n in enumerate(nums):
        total += n
        while total >= target:
            best = min(best, r - l + 1)
            total -= nums[l]
            l += 1
    return best if best != float('inf') else 0

Track the last index of each character; when a repeat appears inside the window, jump the left edge past its previous occurrence.

def lengthOfLongestSubstring(s):
    last_seen = {}
    l = best = 0
    for r, c in enumerate(s):
        if c in last_seen and last_seen[c] >= l:
            l = last_seen[c] + 1
        last_seen[c] = r
        best = max(best, r - l + 1)
    return best

Expand right until the window covers all of t's characters, then greedily shrink left while it still covers, recording the smallest valid window.

from collections import Counter
def minWindow(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    l = start = end = 0
    for r, c in enumerate(s, 1):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        if missing == 0:
            while need[s[l]] < 0:
                need[s[l]] += 1
                l += 1
            if end == 0 or r - l < end - start:
                start, end = l, r
            need[s[l]] += 1
            missing += 1
            l += 1
    return s[start:end]

Maintain a monotonic decreasing deque of INDICES. The front is always the max of the current window; pop stale indices from the back and expired ones from the front.

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()   # indices, values decreasing
    res = []
    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] <= n:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

A fixed window the size of s1; compare 26-length frequency counts (or use a `matches` counter) as the window slides across s2.

from collections import Counter
def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    need, window = Counter(s1), Counter(s2[:len(s1)])
    if need == window:
        return True
    for i in range(len(s1), len(s2)):
        window[s2[i]] += 1
        left = s2[i - len(s1)]
        window[left] -= 1
        if window[left] == 0:
            del window[left]
        if window == need:
            return True
    return False

Same fixed-window frequency-matching idea as Permutation in String, but collect every starting index instead of stopping at the first match.

from collections import Counter
def findAnagrams(s, p):
    res = []
    if len(p) > len(s):
        return res
    need, window = Counter(p), Counter(s[:len(p)])
    if window == need:
        res.append(0)
    for i in range(len(p), len(s)):
        window[s[i]] += 1
        left = s[i - len(p)]
        window[left] -= 1
        if window[left] == 0:
            del window[left]
        if window == need:
            res.append(i - len(p) + 1)
    return res

Allow up to k zeros inside the window; shrink from the left whenever the zero count exceeds k.

def longestOnes(nums, k):
    l = zeros = best = 0
    for r, n in enumerate(nums):
        if n == 0:
            zeros += 1
        while zeros > k:
            if nums[l] == 0:
                zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Window is valid when (window length - count of most frequent char) <= k, meaning k replacements can fix the rest.

from collections import defaultdict
def characterReplacement(s, k):
    counts = defaultdict(int)
    l = best = max_freq = 0
    for r, c in enumerate(s):
        counts[c] += 1
        max_freq = max(max_freq, counts[c])
        while (r - l + 1) - max_freq > k:
            counts[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Baseline satisfaction = customers on non-grumpy minutes. Then slide a window of size `minutes` to find the best extra gain from suppressing grumpiness.

def maxSatisfied(customers, grumpy, minutes):
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
    window = sum(customers[i] for i in range(minutes) if grumpy[i])
    best = window
    for i in range(minutes, len(customers)):
        if grumpy[i]:
            window += customers[i]
        if grumpy[i - minutes]:
            window -= customers[i - minutes]
        best = max(best, window)
    return base + best

When the window product first drops below k, EVERY subarray ending at r and starting anywhere from l to r is valid — that's (r - l + 1) new subarrays.

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    l = count = 0
    product = 1
    for r, n in enumerate(nums):
        product *= n
        while product >= k:
            product //= nums[l]
            l += 1
        count += r - l + 1
    return count

Really "longest subarray with at most 2 distinct values" in disguise — track a small frequency map and shrink when a 3rd type appears.

from collections import defaultdict
def totalFruit(fruits):
    count = defaultdict(int)
    l = best = 0
    for r, f in enumerate(fruits):
        count[f] += 1
        while len(count) > 2:
            count[fruits[l]] -= 1
            if count[fruits[l]] == 0:
                del count[fruits[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Precompute cumulative sums once; each range query then becomes a single O(1) subtraction.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i, n in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + n

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

While scanning, track how many times each prefix sum has occurred. If (current_sum - k) was seen before, those earlier prefixes mark valid subarrays ending here.

from collections import defaultdict
def subarraySum(nums, k):
    count = defaultdict(int)
    count[0] = 1
    running = res = 0
    for n in nums:
        running += n
        res += count[running - k]
        count[running] += 1
    return res

Two passes without division: first fill each slot with the product of everything to its LEFT, then multiply in the running product of everything to its RIGHT.

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n
    left = 1
    for i in range(n):
        res[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

The pivot is where left-sum equals total-sum-minus-left-sum-minus-current. Compute total first, then walk left to right tracking a running left sum.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, n in enumerate(nums):
        if left == total - left - n:
            return i
        left += n
    return -1

The literal definition of a prefix sum — useful as the mental model for every problem in this section.

def runningSum(nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return nums

Key insight: if two prefix sums share the same remainder mod k, the subarray between them is divisible by k. Store the FIRST index each remainder appears.

def checkSubarraySum(nums, k):
    seen = {0: -1}
    running = 0
    for i, n in enumerate(nums):
        running += n
        r = running % k if k != 0 else running
        if r in seen:
            if i - seen[r] >= 2:
                return True
        else:
            seen[r] = i
    return False

A difference array turns "add x passengers over a range" into two O(1) point updates; the final prefix sum reconstructs capacity at every stop.

def carPooling(trips, capacity):
    diff = [0] * 1001
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num
    cur = 0
    for d in diff:
        cur += d
        if cur > capacity:
            return False
    return True

Same difference-array trick as Car Pooling but for generic "add val to range [l, r]" updates, then prefix-sum once at the end.

def getModifiedArray(length, updates):
    diff = [0] * (length + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    res = [0] * length
    cur = 0
    for i in range(length):
        cur += diff[i]
        res[i] = cur
    return res

Extend prefix sums to 2D with inclusion-exclusion: subtract both overlapping strips and add back the double-subtracted corner.

def build_2d_prefix(matrix):
    rows, cols = len(matrix), len(matrix[0])
    P = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            P[r+1][c+1] = matrix[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
    return P

def region_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Sort by start time, then walk through merging any interval that overlaps with the last one kept.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    res = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= res[-1][1]:
            res[-1][1] = max(res[-1][1], end)
        else:
            res.append([start, end])
    return res

Sort strings with a custom comparator: a should come before b if (a+b) > (b+a) as strings.

from functools import cmp_to_key
def largestNumber(nums):
    strs = list(map(str, nums))
    strs.sort(key=cmp_to_key(lambda a, b: -1 if a + b > b + a else 1))
    result = "".join(strs)
    return "0" if result[0] == "0" else result

A min-heap of size k gives O(n log k); Quickselect (Hoare partition) averages O(n) by only recursing into the half containing the answer.

import heapq
def findKthLargest_heap(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)
    return heap[0]

import random
def findKthLargest_quickselect(nums, k):
    target = len(nums) - k
    def partition(l, r):
        pivot = nums[random.randint(l, r)]
        nums[l], nums[nums.index(pivot, l, r+1)] = nums[nums.index(pivot, l, r+1)], nums[l]
        store = l
        for i in range(l + 1, r + 1):
            if nums[i] < pivot:
                store += 1
                nums[i], nums[store] = nums[store], nums[i]
        nums[l], nums[store] = nums[store], nums[l]
        return store
    l, r = 0, len(nums) - 1
    while True:
        p = partition(l, r)
        if p == target:
            return nums[p]
        elif p < target:
            l = p + 1
        else:
            r = p - 1

Implementing merge sort by hand is a common "build a sort from scratch" ask — divide, recursively sort halves, merge.

def sortArray(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = sortArray(nums[:mid])
    right = sortArray(nums[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged

You don't need a full sort: walk once and swap adjacent pairs whenever the required zig-zag pattern (< at even i, > at odd i) is violated.

def wiggleSort(nums):
    for i in range(len(nums) - 1):
        if (i % 2 == 0 and nums[i] > nums[i + 1]) or \
           (i % 2 == 1 and nums[i] < nums[i + 1]):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

Sort citations descending; the H-index is the largest i such that citations[i] >= i+1.

def hIndex(citations):
    citations.sort(reverse=True)
    h = 0
    for i, c in enumerate(citations):
        if c >= i + 1:
            h = i + 1
        else:
            break
    return h

Since all three arrays are sorted, walk three pointers together and advance whichever points to the smallest value.

def arraysIntersection(arr1, arr2, arr3):
    i = j = k = 0
    res = []
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        if arr1[i] == arr2[j] == arr3[k]:
            res.append(arr1[i])
            i += 1; j += 1; k += 1
        else:
            m = min(arr1[i], arr2[j], arr3[k])
            if arr1[i] == m: i += 1
            if arr2[j] == m: j += 1
            if arr3[k] == m: k += 1
    return res

Selection-sort idea using only "flip the first k elements": for each size from n down to 2, flip the max to the front, then flip it into place.

def pancakeSort(arr):
    res = []
    def flip(k):
        arr[:k] = arr[:k][::-1]
    for size in range(len(arr), 1, -1):
        i = arr.index(size)
        if i == size - 1:
            continue
        if i != 0:
            flip(i + 1)
            res.append(i + 1)
        flip(size)
        res.append(size)
    return res

The template every other binary-search problem builds on: shrink [lo, hi] by comparing the midpoint to the target.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

A "lower bound" search: when the loop ends, `lo` is exactly the first index where target could be inserted to keep the array sorted.

def searchInsert(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

At every midpoint, one half is guaranteed to be normally sorted — determine which half that is, then decide whether the target lies in it.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:          # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Compare mid to the right end: if nums[mid] > nums[hi], the minimum is to the right; otherwise it's at mid or to the left.

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Run two separate binary searches: one biased to find the leftmost match, one biased to find the rightmost match.

def searchRange(nums, target):
    def bound(is_left):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (is_left and nums[mid] == target):
                hi = mid
            else:
                lo = mid + 1
        return lo
    left = bound(True)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = bound(False) - 1
    return [left, right]

Rows are sorted and the first element of each row is greater than the last of the previous row, so the whole grid behaves like ONE sorted array — binary search it with index math.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // cols][mid % cols]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Binary search on the ANSWER (eating speed), not the array. For a candidate speed, check feasibility in O(n); shrink the speed range accordingly.

import math
def minEatingSpeed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

Same "binary search on the answer" template as Koko: search over possible ship capacities, checking feasibility with a greedy day-count simulation.

def shipWithinDays(weights, days):
    def days_needed(cap):
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Move toward the side that's still ascending — a peak is guaranteed to exist in that direction because the array's edges are treated as -infinity.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[mid + 1]:
            hi = mid
        else:
            lo = mid + 1
    return lo

Binary search on the VALUE range [1, n]: count how many array elements are <= mid. If that count exceeds mid, the duplicate lies in the lower half.

def findDuplicate(nums):
    lo, hi = 1, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        count = sum(1 for n in nums if n <= mid)
        if count > mid:
            hi = mid
        else:
            lo = mid + 1
    return lo

Store each visited value's index; before inserting, check if its complement is already in the map — turns the O(n^2) brute force into one pass.

def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

Sorted letters (or a 26-count tuple) form a canonical key — all anagrams share the same key and land in the same bucket.

from collections import defaultdict
def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Put every value in a set. Only start counting a sequence from numbers that have no predecessor (n-1 not in set) — that guarantees each element is visited O(1) times total.

def longestConsecutive(nums):
    num_set = set(nums)
    best = 0
    for n in num_set:
        if n - 1 not in num_set:
            length = 1
            while n + length in num_set:
                length += 1
            best = max(best, length)
    return best

Count frequencies, then bucket sort by frequency (index = frequency, up to n) for a true O(n) solution — avoids the O(n log n) of a general sort.

from collections import Counter
def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res
    return res

Use the array itself as a hash set: place each value v (1 <= v <= n) at index v-1 via cyclic swaps, then scan for the first index whose value doesn't match.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Same sign-flipping index trick as "Find All Numbers Disappeared": negate the slot at index |v|-1; if it's already negative, v is a duplicate.

def findDuplicates(nums):
    res = []
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] < 0:
            res.append(abs(n))
        else:
            nums[idx] *= -1
    return res

Combine index-marking (to find the duplicate) with sum arithmetic (expected sum minus actual sum gives the missing number).

def findErrorNums(nums):
    n = len(nums)
    dup = -1
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            dup = abs(x)
        else:
            nums[idx] *= -1
    actual_sum = sum(abs(x) for x in nums)
    missing = n * (n + 1) // 2 - (actual_sum - dup)
    return [dup, missing]

Combine a list (for O(1) random access) with a hashmap (value -> index). To delete in O(1), swap the target with the LAST element before popping.

import random
class RandomizedSet:
    def __init__(self):
        self.data = []
        self.idx = {}

    def insert(self, val):
        if val in self.idx:
            return False
        self.idx[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val):
        if val not in self.idx:
            return False
        last_val = self.data[-1]
        i = self.idx[val]
        self.data[i] = last_val
        self.idx[last_val] = i
        self.data.pop()
        del self.idx[val]
        return True

    def getRandom(self):
        return random.choice(self.data)

Two hashmaps enforce a strict one-to-one character mapping in BOTH directions, preventing many-to-one collisions.

def isIsomorphic(s, t):
    map_st, map_ts = {}, {}
    for a, b in zip(s, t):
        if a in map_st and map_st[a] != b:
            return False
        if b in map_ts and map_ts[b] != a:
            return False
        map_st[a] = b
        map_ts[b] = a
    return True

Count every value's frequency, then for each distinct value check if value+1 exists — their combined counts form a harmonious subsequence.

from collections import Counter
def findLHS(nums):
    count = Counter(nums)
    best = 0
    for n in count:
        if n + 1 in count:
            best = max(best, count[n] + count[n + 1])
    return best

Track four shrinking boundaries (top, bottom, left, right) and peel the matrix layer by layer: right, down, left, up.

def spiralOrder(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                res.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

Rotating 90 deg clockwise = transpose the matrix, then reverse each row. Both steps are in-place.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Use the first row and first column as storage for "this row/col should be zeroed" flags instead of an extra data structure. Handle the first row/col's own flag separately.

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row_zero:
        matrix[0] = [0] * cols
    if first_col_zero:
        for r in range(rows):
            matrix[r][0] = 0

Flood-fill DFS/BFS from every unvisited land cell, sinking the whole connected island as you go so it's never counted twice.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Backtracking DFS from every cell that matches the first letter; mark visited cells temporarily and restore them on backtrack.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        temp, board[r][c] = board[r][c], '#'
        found = (dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or
                 dfs(r,c+1,i+1) or dfs(r,c-1,i+1))
        board[r][c] = temp
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

One hash set per row, column, and 3x3 box catches any duplicate the moment it's seen — single pass over the board.

def isValidSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val == '.':
                continue
            b = (r // 3) * 3 + c // 3
            if val in rows[r] or val in cols[c] or val in boxes[b]:
                return False
            rows[r].add(val); cols[c].add(val); boxes[b].add(val)
    return True

Start at the TOP-RIGHT corner. If the value is too big, move left; if too small, move down — eliminates a row or column each step.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    r, c = 0, cols - 1
    while r < rows and c >= 0:
        if matrix[r][c] == target:
            return True
        elif matrix[r][c] > target:
            c -= 1
        else:
            r += 1
    return False

Build a 2D prefix-sum table once, then answer every block-sum query in O(1) using inclusion-exclusion with clamped bounds.

def matrixBlockSum(mat, k):
    rows, cols = len(mat), len(mat[0])
    P = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            P[r+1][c+1] = mat[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
    res = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            r1, c1 = max(0, r - k), max(0, c - k)
            r2, c2 = min(rows - 1, r + k), min(cols - 1, c + k)
            res[r][c] = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
    return res

Flip the logic: DFS from every 'O' touching the border and mark it safe, then flip every remaining unmarked 'O' — those are the truly surrounded ones.

def solve(board):
    if not board:
        return
    rows, cols = len(board), len(board[0])
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'S'
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    for r in range(rows):
        dfs(r, 0); dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c); dfs(rows - 1, c)
    for r in range(rows):
        for c in range(cols):
            board[r][c] = 'O' if board[r][c] == 'S' else 'X' if board[r][c] == 'O' else board[r][c]

The generation twin of Spiral Matrix I: same four-boundary peel, but WRITE increasing numbers instead of reading them.

def generateMatrix(n):
    matrix = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    num = 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            matrix[top][c] = num; num += 1
        top += 1
        for r in range(top, bottom + 1):
            matrix[r][right] = num; num += 1
        right -= 1
        for c in range(right, left - 1, -1):
            matrix[bottom][c] = num; num += 1
        bottom -= 1
        for r in range(bottom, top - 1, -1):
            matrix[r][left] = num; num += 1
        left += 1
    return matrix

The DP recurrence collapses to O(1) space: at each element, decide whether to extend the previous subarray or start fresh.

def maxSubArray(nums):
    best = cur = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

A negative number can flip the smallest product into the largest, so track BOTH a running max and running min at every step.

def maxProduct(nums):
    best = cur_max = cur_min = nums[0]
    for n in nums[1:]:
        candidates = (n, cur_max * n, cur_min * n)
        cur_max, cur_min = max(candidates), min(candidates)
        best = max(best, cur_max)
    return best

Classic "take or skip" DP: at each house, either rob it (+ best up to two houses back) or skip it (best up to the previous house).

def rob(nums):
    prev, cur = 0, 0
    for n in nums:
        prev, cur = cur, max(cur, prev + n)
    return cur

The O(n log n) trick: maintain a `tails` array where tails[i] is the smallest possible tail of an increasing subsequence of length i+1; binary search where each new value fits.

import bisect
def lengthOfLIS(nums):
    tails = []
    for n in nums:
        i = bisect.bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n
    return len(tails)

Each cell's path count is the sum of the cell above and the cell to the left — collapse the 2D DP table to a single rolling row.

def uniquePaths(m, n):
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[-1]

Same grid-DP shape as Unique Paths, but the recurrence takes the MIN of top/left plus the current cell's own cost.

def minPathSum(grid):
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            elif r == 0:
                grid[r][c] += grid[r][c - 1]
            elif c == 0:
                grid[r][c] += grid[r - 1][c]
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[-1][-1]

Bottom-up DP over amounts 0..target: dp[a] = 1 + min(dp[a - coin]) over all usable coins.

def coinChange(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

A 0/1 knapsack in disguise: can we pick a subset summing to total/2? Iterate targets in REVERSE to avoid reusing an item twice in one pass.

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for n in nums:
        for t in range(target, n - 1, -1):
            dp[t] = dp[t] or dp[t - n]
    return dp[target]

Either the max subarray is normal (plain Kadane), OR it wraps around, which equals total_sum minus the MINIMUM subarray (also via Kadane).

def maxSubarraySumCircular(nums):
    total = cur_max = cur_min = best_max = best_min = nums[0]
    for n in nums[1:]:
        cur_max = max(n, cur_max + n)
        best_max = max(best_max, cur_max)
        cur_min = min(n, cur_min + n)
        best_min = min(best_min, cur_min)
        total += n
    if best_max < 0:
        return best_max
    return max(best_max, total - best_min)

Greedy simplification of the DP: track the farthest reachable index; if the current position ever exceeds it, you're stuck.

def canJump(nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + n)
    return True

Keep a stack of indices with decreasing temperatures. When a warmer day appears, pop and resolve every colder day waiting on the stack.

def dailyTemperatures(temperatures):
    res = [0] * len(temperatures)
    stack = []          # indices, decreasing temps
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

Precompute "next greater" for every value in nums2 using a monotonic stack, then just look values up for nums1.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []
    for n in nums2:
        while stack and stack[-1] < n:
            next_greater[stack.pop()] = n
        stack.append(n)
    return [next_greater.get(n, -1) for n in nums1]

Simulate a circular array by iterating 2n times using modulo indexing, while the monotonic-stack logic stays identical.

def nextGreaterElements(nums):
    n = len(nums)
    res = [-1] * n
    stack = []
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            res[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)
    return res

Maintain an increasing stack of bar indices. When a shorter bar appears, pop taller bars and compute the rectangle each one could form using the stack for the left boundary.

def largestRectangleArea(heights):
    stack = []   # indices, increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best

Alternative to the two-pointer solution: maintain a decreasing stack of walls; when a taller wall appears, pop the trough and compute trapped water bounded by both sides.

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - height[bottom]
            water += width * bounded_height
        stack.append(i)
    return water

Store (price, span) pairs; when a new price is >= the top, absorb its span before pushing — amortized O(1) per call.

class StockSpanner:
    def __init__(self):
        self.stack = []   # (price, span)

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Greedily build the lexicographically smallest subsequence with a monotonic stack, but only pop when enough elements remain to still reach length k.

def mostCompetitive(nums, k):
    stack = []
    n = len(nums)
    for i, x in enumerate(nums):
        while stack and stack[-1] > x and len(stack) - 1 + (n - i) >= k:
            stack.pop()
        if len(stack) < k:
            stack.append(x)
    return stack

Build the result digit by digit with an increasing monotonic stack, popping a larger digit whenever a smaller one arrives and removals remain.

def removeKdigits(num, k):
    stack = []
    for d in num:
        while stack and k > 0 and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    while k > 0:
        stack.pop()
        k -= 1
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Walk the sorted intervals in three phases: add all intervals ending before the new one starts, merge all overlapping ones into it, then append the rest.

def insert(intervals, newInterval):
    res = []
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    res.append(newInterval)
    while i < n:
        res.append(intervals[i]); i += 1
    return res

Sort by END time and greedily keep the interval that finishes earliest — the classic activity-selection greedy proof.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    removed = 0
    prev_end = float('-inf')
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end
        else:
            removed += 1
    return removed

Sort by end coordinate; shoot an arrow at the end of the first balloon, and it bursts every subsequent balloon that starts before that point.

def findMinArrowShots(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows = 1
    end = points[0][1]
    for start, e in points[1:]:
        if start > end:
            arrows += 1
            end = e
    return arrows

Record the LAST index each character appears at. Extend the current partition's boundary to the max last-index of every character seen so far.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    res = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

Think of it as BFS by levels: track the current jump's boundary and the farthest reachable point; increment jumps whenever you exhaust the current level.

def jump(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
    return jumps

If the total gas >= total cost, a solution exists. Reset the candidate start whenever the running tank goes negative — no earlier station could have worked either.

def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

Greedily flip any row not starting with 1 (maximizes the leading bit), then flip any column where 0s outnumber 1s (maximizes that column's contribution).

def matrixScore(grid):
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        if grid[r][0] == 0:
            for c in range(cols):
                grid[r][c] ^= 1
    total = 0
    for c in range(cols):
        ones = sum(grid[r][c] for r in range(rows))
        total += max(ones, rows - ones) * (2 ** (cols - 1 - c))
    return total

Sort tall-first (ties by smaller k-value first), then insert each person at index k — taller people already placed are unaffected by later, shorter insertions.

def reconstructQueue(people):
    people.sort(key=lambda p: (-p[0], p[1]))
    res = []
    for p in people:
        res.insert(p[1], p)
    return res

Two viable expert approaches: a Binary Indexed Tree over rank-compressed values scanned right-to-left, or a modified merge sort that counts cross-inversions during the merge step.

def countSmaller(nums):
    n = len(nums)
    sorted_vals = sorted(set(nums))
    rank = {v: i + 1 for i, v in enumerate(sorted_vals)}
    tree = [0] * (len(sorted_vals) + 1)

    def update(i):
        while i < len(tree):
            tree[i] += 1
            i += i & (-i)

    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    res = [0] * n
    for i in range(n - 1, -1, -1):
        r = rank[nums[i]]
        res[i] = query(r - 1)
        update(r)
    return res

Binary search on the SMALLER array to find a partition point such that every element on the left half is <= every element on the right half across both arrays.

def findMedianSortedArrays(A, B):
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)
    lo, hi = 0, m
    half = (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        A_left = A[i - 1] if i > 0 else float('-inf')
        A_right = A[i] if i < m else float('inf')
        B_left = B[j - 1] if j > 0 else float('-inf')
        B_right = B[j] if j < n else float('inf')
        if A_left <= B_right and B_left <= A_right:
            if (m + n) % 2:
                return max(A_left, B_left)
            return (max(A_left, B_left) + min(A_right, B_right)) / 2
        elif A_left > B_right:
            hi = i - 1
        else:
            lo = i + 1

Union stones that share a row or a column. Every connected component of size c lets you remove c-1 stones (keep exactly one per component).

def removeStones(stones):
    parent = {}
    def find(x):
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
    for r, c in stones:
        union(('r', r), ('c', c))
    roots = {find(('r', r)) for r, c in stones} | {find(('c', c)) for r, c in stones}
    return len(stones) - len(roots)

Sweep through critical x-coordinates using a max-heap of active building heights (lazy deletion); a skyline key point is emitted whenever the max height changes.

import heapq
def getSkyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))
        events.append((r, 0, 0))
    events.sort()
    res = []
    live = [(0, float('inf'))]   # (-height, end)
    for x, neg_h, r in events:
        while live[0][1] <= x:
            heapq.heappop(live)
        if neg_h:
            heapq.heappush(live, (neg_h, r))
        cur_height = -live[0][0]
        if not res or res[-1][1] != cur_height:
            res.append([x, cur_height])
    return res

K-way merge with a min-heap: always advance the pointer of the list holding the current minimum, tracking the running max to compute each candidate range.

import heapq
def smallestRange(nums):
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    cur_max = max(lst[0] for lst in nums)
    best = [float('-inf'), float('inf')]
    while True:
        val, i, j = heapq.heappop(heap)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(nums[i]):
            return best
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))

Augment merge sort: before merging two sorted halves, count cross pairs where left[i] > 2 * right[j] using a two-pointer sweep, since both halves are already sorted.

def reversePairs(nums):
    def sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, cl = sort_count(arr[:mid])
        right, cr = sort_count(arr[mid:])
        count = cl + cr
        j = 0
        for i in range(len(left)):
            while j < len(right) and left[i] > 2 * right[j]:
                j += 1
            count += j
        merged, i, j = [], 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged, count
    return sort_count(nums)[1]

Build prefix sums, then apply the same merge-sort-with-cross-counting trick: count pairs (i, j) where prefix[j] - prefix[i] falls inside [lower, upper] during each merge.

def countRangeSum(nums, lower, upper):
    prefix = [0]
    for n in nums:
        prefix.append(prefix[-1] + n)

    def sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, cl = sort_count(arr[:mid])
        right, cr = sort_count(arr[mid:])
        count = cl + cr
        lo = hi = 0
        for x in left:
            while lo < len(right) and right[lo] - x < lower:
                lo += 1
            while hi < len(right) and right[hi] - x <= upper:
                hi += 1
            count += hi - lo
        merged, i, j = [], 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged, count
    return sort_count(prefix)[1]

3D generalization solved with a min-heap starting from every border cell: always expand from the currently lowest boundary wall, tracking the max wall height seen along each path.

import heapq
def trapRainWater(heightMap):
    rows, cols = len(heightMap), len(heightMap[0])
    visited = [[False] * cols for _ in range(rows)]
    heap = []
    for r in range(rows):
        for c in range(cols):
            if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
                heapq.heappush(heap, (heightMap[r][c], r, c))
                visited[r][c] = True
    water = 0
    while heap:
        h, r, c = heapq.heappop(heap)
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                visited[nr][nc] = True
                water += max(0, h - heightMap[nr][nc])
                heapq.heappush(heap, (max(h, heightMap[nr][nc]), nr, nc))
    return water

Use a difference array to track "currently flipped" state in O(1) per position; greedily flip a window whenever the current effective bit is 0, without ever mutating the future directly.

def minKBitFlips(nums, k):
    n = len(nums)
    diff = [0] * (n + 1)
    flips = cur_flips = 0
    for i in range(n):
        cur_flips += diff[i]
        effective = (nums[i] + cur_flips) % 2
        if effective == 0:
            if i + k > n:
                return -1
            flips += 1
            cur_flips += 1
            diff[i + k] -= 1
    return flips

DP where dp[i] = nums[i] + max(0, best dp value within the last k indices). A monotonic deque maintains that windowed maximum in O(1) amortized per step.

from collections import deque
def constrainedSubsetSum(nums, k):
    dq = deque()   # indices, dp values decreasing
    dp = [0] * len(nums)
    best = float('-inf')
    for i, n in enumerate(nums):
        if dq and dq[0] < i - k:
            dq.popleft()
        dp[i] = n + (dp[dq[0]] if dq and dp[dq[0]] > 0 else 0)
        best = max(best, dp[i])
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return best