Prefix Sum

Problem: Given nums (can contain negatives) and k, return how many contiguous subarrays sum to k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2 * 10⁴ · -1000 ≤ nums[i] ≤ 1000 · -10⁷ ≤ k ≤ 10⁷

From brute force to the pattern: Try every start i and every end j and add up the slice: O(n³), or O(n²) if you extend a running sum from each start. The waste is that every slice sum is rebuilt from scratch. With prefix sums a slice sum is one subtraction, and storing the prefixes you've seen in a hash map turns "is there a start that makes this sum k?" into one O(1) lookup, so the whole thing is O(n).

Spot it: "number of subarrays" + "sum equals k" + negatives allowed, so Sliding Window won't work. That points to Prefix Sum + hash map.

Key insight: If running_now − running_earlier = k, then the slice between those two points sums to k. So at every step, count how many earlier prefixes equal running_now − k.

Approach:

1. Seed seen = {0: 1} for the empty prefix.
2. For each number, add it to running.
3. Add seen[running − k] to the count: each one is a start point that makes a k-sum slice ending here.
4. Only then record running in seen.

from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # seen: running total -> how many times we have reached that total so far
        seen = {}
        # The empty prefix (before index 0) has total 0. Recording it lets
        # a slice that starts at index 0 be counted.
        seen[0] = 1
        running = 0   # sum of nums[0..i]
        count = 0     # the answer
        for i in range(len(nums)):
            number = nums[i]
            running = running + number
            # A slice ending at i sums to k exactly when an earlier running
            # total equals running - k. Count all such earlier totals.
            needed = running - k
            if needed in seen:
                count = count + seen[needed]
            # Record AFTER counting, so we never count an empty slice.
            if running not in seen:
                seen[running] = 0
            seen[running] = seen[running] + 1
        return count

What the code is doing, line by line:

1. seen is a dictionary from "running total" to "how many times we reached it". We seed it with seen[0] = 1 for the empty prefix.
2. running is the sum of everything up to the current index; count is the answer.
3. In the loop, we read nums[i] into number and add it to running.
4. needed = running - k: if some earlier running total equals this, the slice after that point up to i sums to k. We add how many times we saw it.
5. Finally we record running in seen (create it with 0 if new, then add 1). This happens after counting, so a slice never pairs with itself.
6. After the loop, count holds the number of slices that sum to k.

Dry run on the example nums = [1, 2, 3], k = 3:

i	number	running	needed	added	count	seen after
0	1	1	-2	0	0	{0: 1, 1: 1}
1	2	3	0	1	1	{0: 1, 1: 1, 3: 1}
2	3	6	3	1	2	{0: 1, 1: 1, 3: 1, 6: 1}

Result: 2. The two slices are [1, 2] (found at i = 1, because total 0 was seen) and [3] (found at i = 2, because total 3 was seen).

Edge cases to test:

• k = 0 with zeros in the array, e.g. [0, 0, 0] → 6 subarrays (forgetting to seed {0: 1} gives the wrong count).
• Negative numbers, e.g. [1, -1, 0], k = 0: a sliding window would fail here, prefix sums don't.
• A single element equal to k, e.g. [3], k = 3 → 1.

Complexity: O(n) time, O(n) space.

Problem: In a binary array, find the length of the longest subarray with an equal number of 0s and 1s.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · nums[i] is either 0 or 1.

From brute force to the pattern: Check every subarray and count its 0s and 1s: O(n²). Mapping 0 → −1 turns "balanced" into "sums to 0", and two equal prefix sums enclose such a subarray. Storing the first index of each prefix sum lets you measure the longest one in a single O(n) pass.

Spot it: "equal number of" → turn each 0 into −1. Now "equal" means "sum is 0". It's a longest question, so store the first index where each running sum appears.

Approach:

1. Map 0 → −1 and 1 → +1, so "equal counts" means "sum 0".
2. Store the first index at which each running sum appears, seeded with {0: -1}.
3. When a running sum repeats, the slice between the two indices sums to 0. Update the best length.

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # first_at: running sum -> the FIRST index where we saw it
        first_at = {}
        # Running sum 0 is "seen" just before index 0 (at index -1).
        first_at[0] = -1
        running = 0   # (number of 1s) - (number of 0s) so far
        best = 0      # longest balanced slice found so far
        for i in range(len(nums)):
            bit = nums[i]
            # Treat 1 as +1 and 0 as -1, so "equal counts" means "sum is 0".
            if bit == 1:
                running = running + 1
            else:
                running = running - 1
            if running in first_at:
                # Same running sum as at index first_at[running]: the slice
                # after that index, up to i, has sum 0, so it is balanced.
                length = i - first_at[running]
                if length > best:
                    best = length
            else:
                # First time we see this sum: remember where. Never overwrite
                # it, because the earliest index gives the longest slice.
                first_at[running] = i
        return best

What the code is doing, line by line:

1. first_at remembers the first index where each running sum appeared. first_at[0] = -1 says sum 0 happened "just before index 0".
2. For each index, a 1 adds 1 to running and a 0 subtracts 1. So running = (ones so far) − (zeros so far).
3. If this running was seen before at index first_at[running], the numbers between that index and i added up to 0: equal 0s and 1s. Its length is i - first_at[running]; keep it if it beats best.
4. If it is new, store i as its first index. We never overwrite, because an earlier start means a longer slice.
5. Return best.

Dry run on the example nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]:

i	bit	running	what happens	best
0	0	-1	new sum, store first_at[-1] = 0	0
1	1	0	seen at index -1, length = 1 - -1 = 2	2
2	1	1	new sum, store first_at[1] = 2	2
3	1	2	new sum, store first_at[2] = 3	2
4	1	3	new sum, store first_at[3] = 4	2
5	1	4	new sum, store first_at[4] = 5	2
6	0	3	seen at index 4, length = 6 - 4 = 2	2
7	0	2	seen at index 3, length = 7 - 3 = 4	4
8	0	1	seen at index 2, length = 8 - 2 = 6	6

Result: 6 (indices 3..8: [1, 1, 1, 0, 0, 0]).

Edge cases to test:

• No balanced subarray, e.g. [0, 0, 0] → 0.
• The whole array is balanced, e.g. [0, 1, 1, 0] → 4 (needs the seed {0: −1}).
• Length 1 → always 0.

Complexity: O(n) time, O(n) space.

Problem: Return the number of non-empty contiguous subarrays of nums whose sum is divisible by k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · 2 ≤ k ≤ 10⁴

From brute force to the pattern: Sum every subarray and test % k: O(n²). A slice is divisible exactly when its two bounding prefix sums leave the same remainder, so you only need a count per remainder (an array of size k). Each prefix adds the count of earlier equal remainders: O(n + k).

Spot it: "divisible by k" means two prefixes with the same remainder mod k enclose a divisible slice. Count prefixes by remainder.

Approach:

1. Keep counts of prefix remainders mod k, with remainder 0 seen once.
2. For each number, update running = (running + x) % k.
3. Every earlier prefix with the same remainder forms a divisible slice, so add its count, then increment it.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # count_mod[r] = how many prefixes so far have remainder r (mod k).
        # [0] * k makes a list of k zeros.
        count_mod = [0] * k
        # The empty prefix has sum 0, so remainder 0 has been seen once.
        count_mod[0] = 1
        running = 0   # running sum, kept as a remainder mod k
        answer = 0
        for i in range(len(nums)):
            number = nums[i]
            # Python's % always gives a result from 0 to k - 1, even for
            # negative numbers, so it is safe to use as a list index.
            running = (running + number) % k
            # Every earlier prefix with the same remainder encloses a slice
            # whose sum is divisible by k.
            answer = answer + count_mod[running]
            # Count this prefix too, for later positions.
            count_mod[running] = count_mod[running] + 1
        return answer

What the code is doing, line by line:

1. count_mod is a list with one counter per remainder 0..k−1. count_mod[0] = 1 counts the empty prefix.
2. running holds the running sum, but we only keep its remainder mod k.
3. For each number, update the remainder. Python's % never returns a negative number, so it is a safe index.
4. Every earlier prefix with the same remainder forms a slice whose sum is divisible by k, so add count_mod[running] to answer.
5. Then add 1 to count_mod[running] so later positions can pair with this prefix.

Dry run on the example nums = [4, 5, 0, -2, -3, 1], k = 5:

i	number	running (remainder)	added (count_mod[running] before)	answer	count_mod after
0	4	4	0	0	[1, 0, 0, 0, 1]
1	5	4	1	1	[1, 0, 0, 0, 2]
2	0	4	2	3	[1, 0, 0, 0, 3]
3	-2	2	0	3	[1, 0, 1, 0, 3]
4	-3	4	3	6	[1, 0, 1, 0, 4]
5	1	0	1	7	[2, 0, 1, 0, 4]

Result: 7. Notice -2: (4 + -2) % 5 is 2 in Python, never negative.

Edge cases to test:

• Negative numbers: Python's % already returns a non-negative remainder (-1 % 5 == 4); in other languages add k.
• Every element divisible by k, e.g. [5, 5], k = 5 → 3.
• k = 1: every subarray counts, n(n + 1) / 2.

Complexity: O(n) time, O(k) space.

Problem: Design NumMatrix(matrix) with sumRegion(row1, col1, row2, col2), which returns the sum of the rectangle with top-left (row1, col1) and bottom-right (row2, col2) (inclusive). There can be up to 10⁴ queries, each must be O(1).

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 200 · -10⁴ ≤ matrix[i][j] ≤ 10⁴ · 0 ≤ row1 ≤ row2 < m · 0 ≤ col1 ≤ col2 < n · At most 10⁴ calls will be made to sumRegion.

From brute force to the pattern: Adding up the rectangle cell by cell costs O(rows · cols) per query, too slow for many queries. A 2-D prefix sum spends O(rows · cols) once and then answers every query with four lookups (inclusion–exclusion).

Spot it: many rectangle-sum queries on a fixed grid. Use a 2-D prefix sum.

Inclusion–exclusion picture: big rectangle − top strip − left strip + the corner you subtracted twice.

Approach:

1. Build P with one extra row and column of zeros.
2. P[r+1][c+1] = cell + top + left − top-left (the overlap was added twice).
3. Query = big − top strip − left strip + corner.

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        rows = len(matrix)
        cols = len(matrix[0])
        # self.table has one extra row and one extra column of zeros.
        # self.table[row + 1][col + 1] = sum of the rectangle (0, 0) .. (row, col).
        self.table = []
        for row in range(rows + 1):
            # [0] * (cols + 1) makes one row of zeros
            self.table.append([0] * (cols + 1))
        for row in range(rows):
            for col in range(cols):
                cell = matrix[row][col]
                above = self.table[row][col + 1]    # rectangle ending one row up
                left = self.table[row + 1][col]     # rectangle ending one column left
                overlap = self.table[row][col]      # inside BOTH above and left
                # above + left counts the overlap twice, so take it away once
                self.table[row + 1][col + 1] = cell + above + left - overlap

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        big = self.table[row2 + 1][col2 + 1]       # (0, 0) .. (row2, col2)
        top_strip = self.table[row1][col2 + 1]     # all rows above row1
        left_strip = self.table[row2 + 1][col1]    # all columns left of col1
        corner = self.table[row1][col1]            # removed twice, add back once
        return big - top_strip - left_strip + corner

What the code is doing, line by line:

1. __init__ builds self.table with one extra row and column of zeros, one row at a time with append.
2. For each cell, it reads the cell value, the rectangle sum just above (above), just to the left (left), and the diagonal one (overlap).
3. above + left counts the overlap area twice, so the new value is cell + above + left - overlap.
4. sumRegion reads four numbers from the table: the big rectangle from (0, 0) to the bottom-right corner, the strip above the query, the strip to its left, and the top-left corner.
5. Big − top strip − left strip removes everything outside, but the corner was removed twice, so it is added back once.

Dry run on the example from LeetCode (the 5 × 5 matrix), query sumRegion(2, 1, 4, 3):

First, the table built by __init__ (row 0 and column 0 are the padding zeros):

table row	col 0	col 1	col 2	col 3	col 4	col 5
0	0	0	0	0	0	0
1	0	3	3	4	8	10
2	0	8	14	18	24	27
3	0	9	17	21	28	36
4	0	13	22	26	34	49
5	0	14	23	30	38	58

Then the query:

step	value
big = table[5][4]	38
top_strip = table[2][4]	24
left_strip = table[5][1]	14
corner = table[2][1]	8
big - top_strip - left_strip + corner	8

Result: 8.

Edge cases to test:

• A single-cell region (row1 == row2, col1 == col2).
• A region touching row 0 or column 0: the padded extra row/column of zeros avoids index −1.
• Negative values in the matrix.

Complexity: build O(R·C), query O(1).

Problem: Return the number of non-empty submatrices of matrix whose elements sum to target.

Solve it on LeetCode ↗

Constraints: 1 ≤ matrix.length ≤ 100 · 1 ≤ matrix[0].length ≤ 100 · -1000 ≤ matrix[i][j] ≤ 1000 · -10^8 ≤ target ≤ 10^8

From brute force to the pattern: Enumerating all submatrices is O(r² · c²) and summing each one adds more. Fixing the pair of rows reduces the problem to 1-D: squash the columns into sums, then count subarrays summing to target in O(c) with a prefix-sum map. Total O(r² · c).

Spot it: a 2-D version of #560. Fix a pair of rows (top, bottom). Squash the columns between them into a 1-D array of column sums, then run the #560 hash-map trick on it.

Approach:

1. Pick a top row and extend the bottom row down one row at a time.
2. Keep col[c] = sum of column c between top and bottom: a 1-D array.
3. Run the #560 prefix + hash map count on col for target.

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        answer = 0
        for top in range(rows):
            # col_sums[col] = sum of column col from row top down to row bottom.
            col_sums = [0] * cols
            for bottom in range(top, rows):
                # Grow the band by one row: add row bottom into the column sums.
                for col in range(cols):
                    col_sums[col] = col_sums[col] + matrix[bottom][col]
                # col_sums is now a 1-D array. Count its slices that sum to
                # target with the problem 560 trick.
                seen = {}
                seen[0] = 1
                running = 0
                for col in range(cols):
                    running = running + col_sums[col]
                    needed = running - target
                    if needed in seen:
                        answer = answer + seen[needed]
                    if running not in seen:
                        seen[running] = 0
                    seen[running] = seen[running] + 1
        return answer

What the code is doing, line by line:

1. The outer loop picks a top row and starts a fresh col_sums list of zeros.
2. The middle loop moves bottom down one row at a time and adds that row into col_sums. Now col_sums[col] is the sum of column col between top and bottom.
3. Any sub-matrix that uses exactly rows top..bottom is a slice of col_sums. So we run the problem 560 code on col_sums with target.
4. That inner part keeps seen and running exactly like 560, adding seen[needed] to answer each time.
5. After every pair of rows has been tried, answer is the total count.

Dry run on the example matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]], target = 0:

top	bottom	col_sums	slices of col_sums with sum 0	answer
0	0	[0, 1, 0]	2	2
0	1	[1, 2, 1]	0	2
0	2	[1, 3, 1]	0	2
1	1	[1, 1, 1]	0	2
1	2	[1, 2, 1]	0	2
2	2	[0, 1, 0]	2	4

Result: 4: the four single-cell zeros in the corners.

Edge cases to test:

• A single cell equal to target.
• target = 0 with zeros and negatives (the {0: 1} seed matters).
• One row or one column: it degenerates to plain LeetCode 560.

Complexity: O(R²·C) time, O(C) space. Make R the smaller dimension.

Problem: Given a fixed array, answer many sumRange(left, right) calls (inclusive) quickly.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁵ ≤ nums[i] ≤ 10⁵ · 0 ≤ left ≤ right < nums.length · At most 10⁴ calls will be made to sumRange.

From brute force to the pattern: Summing nums[left..right] per query is O(n) each, so q queries cost O(n · q). Building the prefix array once in O(n) makes every query O(1).

Spot it: "many queries" on an array that never changes. That's textbook Prefix Sum.

1. In the constructor, build prefix with a leading 0.
2. For each query, return prefix[right+1] − prefix[left].

class NumArray:
    def __init__(self, nums: List[int]):
        # self.prefix[i] = sum of the first i numbers.
        # It starts with 0, which means "the sum of nothing".
        self.prefix = [0]
        running_total = 0
        for i in range(len(nums)):
            running_total = running_total + nums[i]
            # store the running total after element i
            self.prefix.append(running_total)

    def sumRange(self, left: int, right: int) -> int:
        # "right plus one minus left"
        return self.prefix[right + 1] - self.prefix[left]

What the code is doing, line by line:

1. __init__ starts self.prefix as [0] (sum of nothing) and keeps a running_total.
2. For each number, it adds the number to running_total and appends the new total. So self.prefix[i] is the sum of the first i numbers.
3. sumRange returns self.prefix[right + 1] - self.prefix[left]: everything through right, minus everything before left.

Dry run on the example nums = [-2, 0, 3, -5, 2, -1]:

i	nums[i]	running_total	self.prefix after
0	-2	-2	[0, -2]
1	0	-2	[0, -2, -2]
2	3	1	[0, -2, -2, 1]
3	-5	-4	[0, -2, -2, 1, -4]
4	2	-2	[0, -2, -2, 1, -4, -2]
5	-1	-3	[0, -2, -2, 1, -4, -2, -3]

query	computation	result
sumRange(0, 2)	prefix[3] - prefix[0] = 1 - 0	1
sumRange(2, 5)	prefix[6] - prefix[2] = -3 - -2	-1
sumRange(0, 5)	prefix[6] - prefix[0] = -3 - 0	-3

Edge cases to test:

• left == right (a single element).
• The whole array (left = 0, right = n − 1): this is why prefix has n + 1 entries.
• Negative numbers.

Complexity: build O(n), each query O(1), space O(n).

Problem: Return answer[i] = product of every element except nums[i], without using division, in O(n).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 2 ≤ nums.length ≤ 10⁵ · -30 ≤ nums[i] ≤ 30 · The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

From brute force to the pattern: For each i, multiply all other elements: O(n²). Dividing the total product by nums[i] breaks on zeros and is forbidden. Prefix products from the left and suffix products from the right give each answer in O(1), so O(n) overall.

Spot it: "everything except i" = (everything to the left of i) × (everything to the right of i). That's a prefix product times a suffix product.

1. Left pass: answer[i] = product of nums[0..i-1], starting from 1.
2. Right pass: keep a running suffix product and multiply it into answer[i] while walking from the end.
3. No extra arrays needed: the output array holds the prefix products.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        # [1] * size makes a list of size ones (1 is the "empty product")
        answer = [1] * size
        # Pass 1, left to right: answer[i] = product of everything LEFT of i.
        left_product = 1
        for i in range(size):
            answer[i] = left_product
            left_product = left_product * nums[i]
        # Pass 2, right to left: multiply in the product of everything RIGHT of i.
        right_product = 1
        i = size - 1
        while i >= 0:
            answer[i] = answer[i] * right_product
            right_product = right_product * nums[i]
            i = i - 1
        return answer

What the code is doing, line by line:

1. size is how many numbers there are. answer starts as a list of size ones.
2. Pass 1 walks left to right. Before multiplying, it stores left_product (the product of everything left of i) into answer[i], then multiplies nums[i] into left_product.
3. Pass 2 walks right to left with a while loop: i starts at size - 1 (the last index) and goes down by 1 until it passes 0.
4. At each step it multiplies answer[i] by right_product (the product of everything right of i), then multiplies nums[i] into right_product.
5. Now answer[i] = (left product) × (right product) = everything except nums[i], with no division.

Dry run on the example nums = [1, 2, 3, 4]:

pass	i	nums[i]	product after this step	answer
1 (left to right)	0	1	left_product = 1	[1, 1, 1, 1]
1 (left to right)	1	2	left_product = 2	[1, 1, 1, 1]
1 (left to right)	2	3	left_product = 6	[1, 1, 2, 1]
1 (left to right)	3	4	left_product = 24	[1, 1, 2, 6]
2 (right to left)	3	4	right_product = 4	[1, 1, 2, 6]
2 (right to left)	2	3	right_product = 12	[1, 1, 8, 6]
2 (right to left)	1	2	right_product = 24	[1, 12, 8, 6]
2 (right to left)	0	1	right_product = 24	[24, 12, 8, 6]

Result: [24, 12, 8, 6].

Edge cases to test:

• One zero, e.g. [1, 2, 0, 4] → only index 2 is non-zero.
• Two zeros → every answer is 0.
• Negative numbers, e.g. [-1, 1, 0, -3, 3].

Complexity: O(n) time, O(1) extra space (not counting the output).

Problem: Return true if there is a subarray of length ≥ 2 whose sum is a multiple of k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹ · 0 ≤ sum(nums[i]) ≤ 2³¹ - 1 · 1 ≤ k ≤ 2³¹ - 1

From brute force to the pattern: Checking every subarray of length ≥ 2 is O(n²). Equal remainders mod k mean the slice between them is a multiple of k; remembering where each remainder first appeared lets one pass check the length condition in O(1).

Spot it: "multiple of k" = same remainder trick as #974. "Length ≥ 2" means you must store the first index of each remainder and check the distance.

1. Keep first_at = {0: -1}: remainder 0 is seen "before" index 0.
2. Walk with running = (running + x) % k.
3. If this remainder was seen at index j and i − j ≥ 2, return true.
4. Otherwise record the remainder only the first time you see it, to keep the longest distance.

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # first_at: remainder -> earliest index where the running sum had it
        first_at = {}
        first_at[0] = -1   # remainder 0 is "seen" just before index 0
        running = 0
        for i in range(len(nums)):
            number = nums[i]
            running = (running + number) % k
            if running in first_at:
                # Same remainder as at index first_at[running]: the slice after
                # that index, up to i, has a sum that is a multiple of k.
                length = i - first_at[running]
                if length >= 2:
                    return True
            else:
                # Never overwrite: the earliest index gives the longest slice.
                first_at[running] = i
        return False

What the code is doing, line by line:

1. first_at maps a remainder to the earliest index where the running sum had it. first_at[0] = -1 covers slices that start at index 0.
2. Each step adds the number and keeps only the remainder mod k.
3. If that remainder was seen before, the slice between has a sum that is a multiple of k. Its length is i - first_at[running]; if that is at least 2, return True.
4. If the remainder is new, store the index. Never overwrite, so we always measure from the earliest index.
5. If the loop ends with no success, return False.

Dry run on the example nums = [23, 2, 4, 6, 7], k = 6:

i	number	running (remainder)	what happens	result
0	23	5	new remainder, store first_at[5] = 0	keep going
1	2	1	new remainder, store first_at[1] = 1	keep going
2	4	5	seen at index 0, length 2 >= 2	return True

Result: True: the slice [2, 4] (indices 1..2) sums to 6.

Edge cases to test:

• [0, 0] with any k → True (0 is a multiple of every k).
• A single element that is a multiple of k, e.g. [6], k = 6 → False (length 1).
• Seeding {0: −1} so a valid prefix starting at index 0 is found.

Complexity: O(n) time, O(min(n, k)) space.

Problem: Count downward paths in a binary tree (from any node to any descendant) whose values sum to targetSum.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 1000]. · -10⁹ ≤ Node.val ≤ 10⁹ · -1000 ≤ targetSum ≤ 1000

From brute force to the pattern: Starting a DFS from every node and following every downward path is O(n²) on a skewed tree. Treating each root-to-node path like an array, the prefix-sum hash map counts matching paths ending at each node in O(1), so O(n) total.

Spot it: a root-to-node path is just an array. Count "subarrays with sum = target" along it, which is #560, done during a DFS.

1. DFS from the root, carrying the running sum from the root to the current node.
2. At each node, add seen[running − target] to the answer.
3. Add running to seen, recurse into both children, then remove it on the way back (backtrack). This keeps only the current path's prefixes in the map.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # self.seen: running sum from the root -> how many nodes on the
        # CURRENT path (root down to here) have that running sum.
        self.seen = {}
        self.seen[0] = 1          # the empty path above the root
        self.target = targetSum
        return self.count_paths(root, 0)

    # Helper method (a separate method instead of a nested function).
    # Returns how many good paths end somewhere in the subtree of node.
    def count_paths(self, node, running):
        if node is None:
            return 0
        running = running + node.val
        # Paths that END at this node: earlier prefixes equal to running - target.
        needed = running - self.target
        count = 0
        if needed in self.seen:
            count = self.seen[needed]
        # Make this prefix visible to the nodes below.
        if running not in self.seen:
            self.seen[running] = 0
        self.seen[running] = self.seen[running] + 1
        count = count + self.count_paths(node.left, running)
        count = count + self.count_paths(node.right, running)
        # Backtrack: we are leaving this node, so remove its prefix again.
        self.seen[running] = self.seen[running] - 1
        return count

What the code is doing, line by line:

1. pathSum sets up shared state on self: the seen dictionary (seeded with {0: 1}) and the target. Then it calls the helper on the root with running sum 0.
2. count_paths returns 0 for a missing child (node is None).
3. Otherwise it adds node.val to running, the sum from the root down to this node.
4. Paths that end here and sum to the target start right after an ancestor whose running sum was running - target. self.seen[needed] says how many such ancestors there are.
5. It records running in self.seen so the children can use it, then adds the counts from the left and right subtrees.
6. Before returning, it subtracts 1 from self.seen[running] (backtracking), so sibling branches do not see this node's total.

Dry run on the example root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8. Rows are in DFS visit order (node, then its left subtree, then its right subtree):

visit node	current path	running	needed = running - 8	paths ending here	seen on the path (after adding)
10	10	10	2	0	{0: 1, 10: 1}
5	10 → 5	15	7	0	{0: 1, 10: 1, 15: 1}
3	10 → 5 → 3	18	10	1	{0: 1, 10: 1, 15: 1, 18: 1}
3	10 → 5 → 3 → 3	21	13	0	{0: 1, 10: 1, 15: 1, 18: 1, 21: 1}
-2	10 → 5 → 3 → -2	16	8	0	{0: 1, 10: 1, 15: 1, 18: 1, 16: 1}
2	10 → 5 → 2	17	9	0	{0: 1, 10: 1, 15: 1, 17: 1}
1	10 → 5 → 2 → 1	18	10	1	{0: 1, 10: 1, 15: 1, 18: 1, 17: 1}
-3	10 → -3	7	-1	0	{0: 1, 10: 1, 7: 1}
11	10 → -3 → 11	18	10	1	{0: 1, 10: 1, 18: 1, 7: 1}

Result: 3: the paths 5 → 3, 5 → 2 → 1 and -3 → 11. Notice how seen only ever holds the totals of the current path, thanks to the backtracking step.

Edge cases to test:

• Negative values, so a path can still match after the sum overshoots.
• targetSum = 0 with zero-valued nodes.
• An empty tree → 0.

Complexity: O(n) time, O(h) space (h = tree height).

Problem: Remove the shortest subarray (it may be empty, but you can't remove the whole array) so the sum of what remains is divisible by p. Return its length, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ p ≤ 10⁹

From brute force to the pattern: Trying every subarray to remove and re-checking the rest is O(n²) or worse. In remainder terms, you need the shortest slice with sum ≡ need (mod p): a prefix-remainder map storing the latest index finds the shortest one ending at each j in O(1).

Spot it: the removed slice must have sum % p == total % p. That's a remainder lookup, and because it asks for the shortest, store the latest index of each remainder.

1. need = total % p. If it's 0, return 0.
2. Walk with running % p. A slice (j, i] works when (running_i − running_j) % p == need, i.e. running_j ≡ running_i − need.
3. Look that up in last_at and keep the minimum length. Always overwrite last_at[running] with the newest index.
4. If the best length is the whole array, return −1.

class Solution:
    def minSubarray(self, nums: List[int], divisor: int) -> int:
        # (LeetCode calls the divisor p.)
        # Add up all the numbers with a plain loop.
        total = 0
        for i in range(len(nums)):
            total = total + nums[i]
        # The removed slice must have this same remainder.
        need = total % divisor
        if need == 0:
            return 0       # already divisible: remove nothing
        # last_at: remainder -> LATEST index where a prefix had that remainder
        last_at = {}
        last_at[0] = -1    # the empty prefix
        running = 0
        best = len(nums)   # means "not found yet" (removing everything is not allowed)
        for i in range(len(nums)):
            running = (running + nums[i]) % divisor
            # An earlier prefix with remainder want encloses a slice whose
            # remainder is need.
            want = (running - need) % divisor
            if want in last_at:
                length = i - last_at[want]
                if length < best:
                    best = length
            # Always overwrite: the most recent index gives the shortest slice.
            last_at[running] = i
        if best < len(nums):
            return best
        else:
            return -1

What the code is doing, line by line:

1. A plain loop adds up total. need = total % divisor is the remainder the removed slice must have. If it is 0, nothing needs removing.
2. last_at maps a remainder to the latest index with that prefix remainder, seeded with {0: -1}.
3. best starts at len(nums), which means "nothing valid found" because removing the whole array is not allowed.
4. Each step updates running (a remainder) and computes want = (running - need) % divisor: the remainder an earlier prefix must have so that the slice in between has remainder need.
5. If want is in last_at, the slice length is i - last_at[want]; keep it if shorter.
6. Always overwrite last_at[running] = i: a more recent start gives a shorter slice.
7. At the end, return best if it was improved, otherwise −1.

Dry run on the example nums = [3, 1, 4, 2], p = 6:

Total is 10, so need = 10 % 6 = 4.

i	nums[i]	running	want	want in last_at?	best	last_at after
0	3	3	5	no	4	{0: -1, 3: 0}
1	1	4	0	yes, at index -1, length 2	2	{0: -1, 3: 0, 4: 1}
2	4	2	4	yes, at index 1, length 1	1	{0: -1, 3: 0, 4: 1, 2: 2}
3	2	4	0	yes, at index -1, length 4	1	{0: -1, 3: 0, 4: 3, 2: 2}

Result: 1: remove [4], leaving 3 + 1 + 2 = 6.

Edge cases to test:

• Already divisible (need = 0) → 0.
• Only removing the whole array would work → −1 (the whole array may not be removed).
• Large numbers, so work with remainders throughout.

Complexity: O(n) time, O(min(n, p)) space.

Problem: The array can contain negatives. Return the length of the shortest subarray with sum ≥ k, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁵ ≤ nums[i] ≤ 10⁵ · 1 ≤ k ≤ 10⁹

From brute force to the pattern: Checking all (i, j) pairs of prefix sums is O(n²). A monotonic deque keeps only start candidates that could still give a shorter answer: an older start with a larger prefix is never better, so it gets dropped. Each index enters and leaves once: O(n).

Spot it: because of negatives, Sliding Window fails. With prefix sums the question becomes: for each j, find the latest i < j with P[j] − P[i] ≥ k. A monotonic deque of increasing prefix values answers that in amortized O(1).

1. Build P with a leading 0.
2. Keep a deque of indices whose P values are strictly increasing.
3. For each j: while P[j] − P[dq[0]] ≥ k, record j − dq[0] and pop from the front. That start can never give a shorter answer later.
4. While P[j] ≤ P[dq[-1]], pop from the back. A later, smaller prefix is always a better start.
5. Push j.

from collections import deque


class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        # prefix[i] = sum of the first i numbers (prefix[0] = 0)
        prefix = [0]
        running = 0
        for i in range(len(nums)):
            running = running + nums[i]
            prefix.append(running)
        best = len(nums) + 1    # bigger than any real answer = "not found yet"
        # candidates holds start indices whose prefix values strictly increase.
        # deque: append(x) adds x at the back, popleft() removes and returns
        # the front item, pop() removes the back item.
        candidates = deque()
        for j in range(len(prefix)):
            # Front check: while the oldest start makes a slice with sum >= k,
            # record its length and drop it (any later j would only be longer).
            while len(candidates) > 0 and prefix[j] - prefix[candidates[0]] >= k:
                start = candidates.popleft()
                length = j - start
                if length < best:
                    best = length
            # Back check: a start whose prefix is >= prefix[j] is never better
            # than j (j is later AND has a smaller prefix), so remove it.
            last = len(candidates) - 1
            while len(candidates) > 0 and prefix[j] <= prefix[candidates[last]]:
                candidates.pop()
                last = len(candidates) - 1
            candidates.append(j)
        if best <= len(nums):
            return best
        else:
            return -1

What the code is doing, line by line:

1. First build prefix with a leading 0 using a running total and append.
2. best starts one larger than any real answer. candidates is a deque of start indices whose prefix values go strictly up from front to back.
3. For each end index j, the front loop checks the oldest start: if prefix[j] - prefix[front] >= k, that slice works. Record its length and popleft() it, since a later j could only make it longer.
4. The back loop removes starts whose prefix is >= prefix[j]: j is a later start with a smaller (or equal) prefix, so it is always at least as good. last is the index of the back item and is recomputed after each pop().
5. Then j joins the back of the deque as a future start.
6. Return best if it was improved, otherwise −1.

Dry run on the example nums = [2, -1, 2], k = 3:

prefix = [0, 2, 1, 3].

j	prefix[j]	popped from front (recorded)	popped from back	candidates after	best
0	0	-	-	[0]	4
1	2	-	-	[0, 1]	4
2	1	-	[1]	[0, 2]	4
3	3	[0]	-	[2, 3]	3

Result: 3 (the whole array, 2 - 1 + 2 = 3).

Edge cases to test:

• No valid subarray → −1.
• A single element ≥ k → 1.
• Negatives between positives, e.g. [2, -1, 2], k = 3 → 3.

Complexity: O(n) time (each index enters and leaves the deque once), O(n) space.

Problem: Given positive weights w, implement pickIndex() that returns index i with probability w[i] / sum(w).

Solve it on LeetCode ↗

Constraints: 1 ≤ w.length ≤ 10⁴ · 1 ≤ w[i] ≤ 10⁵ · pickIndex will be called at most 10⁴ times.

From brute force to the pattern: Repeating each index w[i] times in a list makes picking O(1) but needs memory proportional to the total weight. Prefix sums compress that list into n boundaries, and binary search finds the boundary in O(log n).

Spot it: Stack the weights end to end on a number line: index i owns the stretch [prefix[i], prefix[i + 1]). A random point on the line lands in index i's stretch with exactly the right probability, and finding the stretch is a binary search over prefix sums.

Why not another pattern? Building a list with each index repeated w[i] times is simple but needs sum(w) memory (up to 10⁹). A linear scan over the prefix sums is O(n) per pick; binary search makes it O(log n).

Approach:

1. Constructor: build running totals prefix where prefix[i] = w[0] + … + w[i].
2. pickIndex: draw a random integer target in 1..total.
3. Binary-search the first index with prefix[i] ≥ target; that's the answer.

import random

class Solution:
    def __init__(self, w: List[int]):
        self.prefix = []
        running = 0
        for weight in w:
            running = running + weight
            self.prefix.append(running)  # index i owns the numbers (prefix[i-1], prefix[i]]
        self.total = running

    def pickIndex(self) -> int:
        target = random.randint(1, self.total)  # a random point on the number line
        lo = 0
        hi = len(self.prefix) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.prefix[mid] < target:
                lo = mid + 1  # target lies to the right of mid's range
            else:
                hi = mid  # mid's range might contain target
        return lo

What the code is doing, line by line:

1. self.prefix: running totals; with w = [1, 3] they are [1, 4], so index 0 owns {1} and index 1 owns {2, 3, 4}.
2. random.randint(1, self.total): every integer in 1..total is equally likely, so index i is hit with probability w[i] / total.
3. The binary search finds the first prefix total that is at least target: the owner of that number.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single weight → always 0.
• One huge weight among tiny ones.
• Equal weights → uniform picks.

Complexity: Constructor O(n); each pickIndex O(log n) time; O(n) space.

Problem: Count the non-empty subarrays of the binary array nums whose sum equals goal.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · nums[i] is either 0 or 1. · 0 ≤ goal ≤ nums.length

From brute force to the pattern: Summing every subarray is O(n²). With prefix sums, each subarray ending at j corresponds to one earlier prefix, and a count map looks those up in O(1): O(n).

Spot it: "Count subarrays with sum exactly goal" is the prefix-sum + hash-map counting pattern: a subarray ending at j works for every earlier prefix equal to running − goal.

Why not another pattern? A sliding window works for "at most" counts with non-negative numbers (exactly(g) = atMost(g) − atMost(g − 1)) and is also O(n). The prefix-count map handles goal = 0 directly without that trick.

Approach:

1. seen = {0: 1} counts prefix sums seen so far (the empty prefix included).
2. For each number, update running, add seen[running − goal] to the answer, then record running.

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        seen = {0: 1}  # prefix sum -> how many times it has appeared
        running = 0
        count = 0
        for x in nums:
            running = running + x
            count = count + seen.get(running - goal, 0)  # earlier prefixes that start a valid subarray
            seen[running] = seen.get(running, 0) + 1
        return count

What the code is doing, line by line:

1. seen = {0: 1}: lets a subarray that starts at index 0 be counted.
2. seen.get(running - goal, 0): each earlier prefix equal to running − goal marks the start of a subarray ending here with sum goal.
3. Record running only after counting, so a subarray is never empty.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• goal = 0: count the runs of zeros, e.g. [0, 0, 0, 0, 0] → 15.
• goal larger than the number of 1s → 0.
• All ones.

Complexity: O(n) time, O(n) space.

Problem: Each booking [first, last, seats] reserves seats on every flight from first to last (1-indexed). Return the total seats reserved on each of the n flights.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 2 * 10⁴ · 1 ≤ bookings.length ≤ 2 * 10⁴ · bookings[i].length == 3 · 1 ≤ firsti ≤ lasti ≤ n · 1 ≤ seatsi ≤ 10⁴

From brute force to the pattern: Looping over every flight in every booking is O(n · b), up to 4·10¹⁰ operations. The difference array records each booking in O(1) and one prefix sum reconstructs all totals: O(n + b).

Spot it: Many "add x to a whole range" updates followed by one read of every position: the difference array trick, which is a prefix sum in reverse.

Why not another pattern? Adding seats flight by flight for each booking is O(n · bookings). A segment tree supports range updates too, but is unnecessary when all queries come after all updates.

Approach:

1. diff = [0] * (n + 1).
2. For each booking: diff[first − 1] += seats and diff[last] −= seats (where the range ends).
3. A running sum over diff gives the total for each flight.

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * (n + 1)
        for first, last, seats in bookings:
            diff[first - 1] = diff[first - 1] + seats  # the range starts here
            diff[last] = diff[last] - seats  # and stops after flight `last`
        answer = []
        running = 0
        for i in range(n):
            running = running + diff[i]  # prefix sum of the differences
            answer.append(running)
        return answer

What the code is doing, line by line:

1. diff[first - 1] += seats: from flight first (0-indexed first − 1) onward, add seats.
2. diff[last] -= seats: cancel it after flight last. The extra slot n absorbs ranges that end at the last flight.
3. The running total over diff rebuilds the actual count for every flight in one pass.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A booking covering all flights.
• Single-flight bookings (first == last).
• Overlapping bookings add up.

Complexity: O(n + b) time for b bookings, O(n) space.

Problem: A day is tiring if hours[i] > 8. A well-performing interval has strictly more tiring days than non-tiring days. Return the length of the longest such interval.

Solve it on LeetCode ↗

Constraints: 1 ≤ hours.length ≤ 10⁴ · 0 ≤ hours[i] ≤ 16

From brute force to the pattern: Checking all intervals is O(n²). The ±1 transformation makes it a prefix-sum question, and because the sum moves by 1 each step, one lookup of s − 1 finds the best start: O(n).

Spot it: Map tiring days to +1 and others to −1: you want the longest subarray with positive sum. Positive sums of subarrays are differences of prefix sums, and remembering where each prefix value first appeared finds the longest one.

Why not another pattern? A sliding window fails because the sum isn't monotonic when the window grows (values can be −1). Checking every subarray is O(n²).

Key insight: If the running sum s is positive, the whole prefix works. Otherwise the best start is right after the first time the prefix sum was s − 1 (sums change by 1 at a time, so s − 1 is reached before any smaller value).

Approach:

1. Scan with s = running sum of +1/−1.
2. If s > 0, the prefix 0..i is valid: answer i + 1.
3. Else if s − 1 has appeared, the interval after its first appearance is valid: length i − first[s − 1].
4. Record the first index of each prefix sum value.

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        first = {}  # prefix sum -> first index where it appeared
        s = 0
        best = 0
        for i in range(len(hours)):
            s = s + (1 if hours[i] > 8 else -1)  # tiring day +1, normal day -1
            if s > 0:
                best = i + 1  # the whole prefix has more tiring days
            elif s - 1 in first:
                best = max(best, i - first[s - 1])  # start right after sum s-1 first appeared
            if s not in first:
                first[s] = i  # keep only the earliest index (longest intervals)
        return best

What the code is doing, line by line:

1. s is the prefix sum of the ±1 values.
2. s > 0: the interval from day 0 to day i already has more tiring days.
3. Otherwise the sum of (j, i] is s − prefix(j); it's positive when prefix(j) ≤ s − 1, and the earliest such j is where s − 1 first appeared.
4. first[s] = i only on the first occurrence, so intervals stay as long as possible.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No tiring days → 0.
• All tiring days → n.
• The best interval is in the middle.

Complexity: O(n) time, O(n) space.

Problem: A subarray is nice if it contains exactly k odd numbers. Count the nice subarrays.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 50000 · 1 ≤ nums[i] ≤ 10^5 · 1 ≤ k ≤ nums.length

From brute force to the pattern: Counting odds in every subarray is O(n²). Prefix counts of odd numbers make every subarray's count a subtraction, and a count map finds matching starts in O(1).

Spot it: Replace each number by 1 if odd and 0 if even: you're counting subarrays with sum exactly k, the prefix-count map pattern.

Why not another pattern? A sliding window with exactly(k) = atMost(k) − atMost(k − 1) also works in O(n). Checking all subarrays is O(n²).

Approach:

1. seen = {0: 1}; odds = number of odd values so far.
2. At each position add seen[odds − k], then record odds.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        seen = {0: 1}  # how many prefixes had this many odd numbers
        odds = 0
        count = 0
        for x in nums:
            odds = odds + (x % 2)  # 1 for odd, 0 for even
            count = count + seen.get(odds - k, 0)  # starts that leave exactly k odds
            seen[odds] = seen.get(odds, 0) + 1
        return count

What the code is doing, line by line:

1. x % 2 is 1 for odd numbers, so odds is a prefix count.
2. A subarray ending here has exactly k odds when it starts after a prefix with odds − k odds.
3. Recording after counting keeps subarrays non-empty.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Not enough odd numbers → 0.
• All odd numbers.
• Even numbers between odd ones multiply the possibilities.

Complexity: O(n) time, O(n) space (an array of size n + 1 works too).

Problem: For each cell (i, j), return the sum of all mat[r][c] with |r − i| ≤ k and |c − j| ≤ k (clipped to the grid).

Solve it on LeetCode ↗

Constraints: m == mat.length · n == mat[i].length · 1 ≤ m, n, k ≤ 100 · 1 ≤ mat[i][j] ≤ 100

From brute force to the pattern: Summing a (2k + 1)² block for every cell is O(m · n · k²). One 2-D prefix sum makes every block four lookups: O(m · n) total.

Spot it: Many rectangle sums over one fixed grid: a 2-D prefix sum makes each rectangle O(1).

Why not another pattern? Summing each block directly is O(m · n · k²). A sliding window per row and column also works but is harder to get right.

Approach:

1. Build P[r + 1][c + 1] = sum of mat[0..r][0..c].
2. For each cell, clamp the block to r1 = max(0, i − k), r2 = min(m − 1, i + k) (same for columns).
3. Rectangle sum = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]  # P[r][c] = sum of mat[0..r-1][0..c-1]
        for r in range(m):
            for c in range(n):
                P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
        answer = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1 = max(0, i - k)  # clamp the block to the grid
                r2 = min(m - 1, i + k)
                c1 = max(0, j - k)
                c2 = min(n - 1, j + k)
                answer[i][j] = P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
        return answer

What the code is doing, line by line:

1. P has an extra row and column of zeros so rectangles touching the edge need no special case.
2. Building P: the cell plus the prefix above plus the prefix to the left, minus the overlap counted twice.
3. The block is clamped so it never leaves the grid.
4. Inclusion–exclusion: big rectangle − strip above − strip to the left + the corner removed twice.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than the grid → every cell gets the total sum.
• A single row or column.
• Corner cells (the block is clipped on two sides).

Complexity: O(m · n) time and space.

Problem: Change elements (to values in 1..limit) so that every mirrored pair nums[i] + nums[n − 1 − i] has the same sum. Return the minimum number of changes.

Solve it on LeetCode ↗

Constraints: n == nums.length · 2 ≤ n ≤ 10⁵ · 1 ≤ nums[i] ≤ limit ≤ 10⁵ · n is even.

From brute force to the pattern: For every candidate sum T (up to 2·limit), computing every pair's cost is O(n · limit), too slow at 10⁵ × 10⁵. Each pair's cost changes only at 4 breakpoints, so a difference array plus a prefix sum gives the totals for all T in O(n + limit).

Spot it: Try every possible target sum T in 2..2·limit. For one pair (a, b), the cost is 0 if T = a + b, 1 if T is in [min(a,b) + 1, max(a,b) + limit], else 2. Each pair adds a piecewise-constant cost over T: a difference array plus a prefix sum totals it for all T.

Why not another pattern? Trying every target and recomputing every pair's cost is O(n · limit). The difference array is O(n + limit).

Approach:

1. diff over sums 0..2·limit + 1. For each pair (a, b) with lo = min, hi = max:
2. Every target costs 2 at first: diff[2] += 2.
3. Targets in [lo + 1, hi + limit] cost one less: diff[lo + 1] −= 1, diff[hi + limit + 1] += 1.
4. The target a + b costs one less again: diff[a + b] −= 1, diff[a + b + 1] += 1.
5. Prefix-sum diff over 2..2·limit and take the minimum.

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        diff = [0] * (2 * limit + 2)
        for i in range(n // 2):
            a = nums[i]
            b = nums[n - 1 - i]
            lo = min(a, b)
            hi = max(a, b)
            diff[2] = diff[2] + 2  # by default this pair needs 2 changes
            diff[lo + 1] = diff[lo + 1] - 1  # from lo+1 one change is enough ...
            diff[hi + limit + 1] = diff[hi + limit + 1] + 1  # ... up to hi+limit
            diff[a + b] = diff[a + b] - 1  # exactly a+b needs no change
            diff[a + b + 1] = diff[a + b + 1] + 1
        best = n
        moves = 0
        for target in range(2, 2 * limit + 1):
            moves = moves + diff[target]  # prefix sum = total moves for this target sum
            best = min(best, moves)
        return best

What the code is doing, line by line:

1. Each mirrored pair contributes a cost that depends only on the chosen target sum.
2. Changing one element of the pair can reach any sum from lo + 1 (shrink the bigger to 1) to hi + limit (grow the smaller to limit).
3. The difference array records each pair's three cost levels with five O(1) updates.
4. The prefix sum at target is the total number of changes for that target; the minimum over all targets is the answer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already complementary → 0.
• limit small, so some sums are unreachable with one change.
• Two elements only.

Complexity: O(n + limit) time and space.

Problem: For each index i, return the sum of |i − j| over all other indices j with nums[j] == nums[i].

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: For each index, scanning all equal indices is O(k²) per group, O(n²) when one value dominates. Running prefix sums of positions compute every answer in O(1).

Spot it: Within one group of equal values (positions sorted), the distance from position p to all positions on its left is p × count_left − sum_left, and to the right sum_right − p × count_right. Running prefix sums of positions give both.

Why not another pattern? Comparing all pairs inside each group is O(n²) when one value repeats a lot.

Approach:

1. Group the indices by value (they come out sorted).
2. For each group, compute the total of its positions.
3. Walk the group keeping left_sum and left_count; for position p: right side = total − left_sum − p, right_count = size − left_count − 1.
4. answer[p] = p·left_count − left_sum + right_sum − p·right_count.

from collections import defaultdict

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        groups = defaultdict(list)  # value -> its indices in increasing order
        for i, x in enumerate(nums):
            groups[x].append(i)
        answer = [0] * len(nums)
        for positions in groups.values():
            total = sum(positions)
            size = len(positions)
            left_sum = 0  # sum of positions to the left of p
            for left_count, p in enumerate(positions):
                right_sum = total - left_sum - p
                right_count = size - left_count - 1
                answer[p] = (p * left_count - left_sum) + (right_sum - p * right_count)
                left_sum = left_sum + p  # p joins the left side
        return answer

What the code is doing, line by line:

1. groups[x] lists the indices holding value x, already sorted because we scan left to right.
2. enumerate(positions) gives left_count (how many equal values are to the left) together with the position p.
3. Left distances: each of the left_count positions is p − q, which sums to p·left_count − left_sum. Right distances are the mirror image.
4. left_sum += p after using it, so p counts as "left" for the next position.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A value appearing once → 0.
• All values equal.
• Large indices (answers exceed 32 bits; Python is fine).

Complexity: O(n) time and space.

Problem: A subarray nums[i..j] is good if |nums[i] − nums[j]| == k. Return the maximum sum of a good subarray, or 0 if none exists.

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹ · 1 ≤ k ≤ 10⁹

From brute force to the pattern: Trying every start for every end is O(n²). With prefix sums, the best start for an end only depends on the minimum prefix before each value, which a hash map keeps in O(1) per step.

Spot it: Subarray sum = prefix[j + 1] − prefix[i]. For a fixed end j, the start must hold value nums[j] ± k, and to maximise the sum you want the smallest prefix[i] among such starts: a hash map from value to the minimum prefix sum before it.

Why not another pattern? Checking every pair (i, j) is O(n²). A sliding window doesn't apply: the condition is about the two endpoint values, not the window's contents.

Approach:

1. Keep prefix (sum of nums[0..j−1]) and best_start[v] = smallest prefix sum seen just before an index holding v.
2. At index j: first record best_start[nums[j]] = min(..., prefix) (a subarray may start here).
3. Add nums[j] to prefix; for v in {nums[j] − k, nums[j] + k}, if v is in the map, candidate = prefix − best_start[v].
4. Return the best candidate, or 0.

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        best_start = {}  # value -> smallest prefix sum right before an index with that value
        prefix = 0  # sum of nums[0..j-1]
        best = None
        for x in nums:
            if x not in best_start or prefix < best_start[x]:
                best_start[x] = prefix  # a good subarray could start here
            prefix = prefix + x  # now prefix = sum of nums[0..j]
            for v in (x - k, x + k):
                if v in best_start:
                    candidate = prefix - best_start[v]  # sum of nums[i..j] for the best start i
                    if best is None or candidate > best:
                        best = candidate
        return best if best is not None else 0

What the code is doing, line by line:

1. best_start[x] = prefix before adding x: the subarray starting at this index has sum prefix_after − prefix_before.
2. Keeping the minimum prefix per value maximises prefix − best_start[v].
3. (x - k, x + k): the start value must differ from the end value by exactly k, in either direction.
4. best is None: sums can be negative, so 0 is only returned when no good subarray exists.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No good subarray → 0.
• All negative numbers (the best sum is negative, e.g. -6).
• The same value repeated (keep the smaller prefix).

Complexity: O(n) time, O(n) space.

Problem: Count submatrices that contain the top-left cell of grid and have sum ≤ k.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ n, m ≤ 1000 · 0 ≤ grid[i][j] ≤ 1000 · 1 ≤ k ≤ 10⁹

From brute force to the pattern: Summing every rectangle anchored at (0, 0) from scratch is O((m · n)²). The 2-D prefix sum gives each one in O(1).

Spot it: A submatrix containing the top-left cell is exactly the rectangle (0, 0)..(r, c), whose sum is the 2-D prefix sum P[r][c]. So build the 2-D prefix sums and count the ones ≤ k.

Why not another pattern? Summing each candidate rectangle separately is O((m · n)²). No search is needed at all: there's one candidate per cell.

Approach:

1. Build prefix sums in place: P[r][c] = grid[r][c] + P[r−1][c] + P[r][c−1] − P[r−1][c−1].
2. Count the cells whose prefix sum is ≤ k.

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m = len(grid)
        n = len(grid[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]  # P[r+1][c+1] = sum of grid[0..r][0..c]
        count = 0
        for r in range(m):
            for c in range(n):
                P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
                if P[r + 1][c + 1] <= k:
                    count = count + 1  # the rectangle from (0,0) to (r,c) qualifies
        return count

What the code is doing, line by line:

1. Each cell (r, c) defines exactly one submatrix that contains the top-left cell: (0, 0) to (r, c).
2. P[r + 1][c + 1] is that rectangle's sum, built from the neighbours with inclusion–exclusion.
3. Count it if it's at most k. (Values are non-negative, so you could even stop a row early.)

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k smaller than grid[0][0] → 0.
• A single cell.
• Every rectangle qualifies → m · n.

Complexity: O(m · n) time and space.

Problem: Count binary arrays with exactly zero zeros and one ones in which no run of equal bits is longer than limit, modulo 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 1 ≤ zero, one, limit ≤ 200

From brute force to the pattern: Listing all arrangements is exponential. A DP that tries every possible length for the last run is O(z · o · limit), about 8·10⁶ steps here. The subtraction (a sliding-window sum over the DP) drops it to O(z · o).

Spot it: Counting arrangements built left to right with a constraint on run length is DP. The "no run longer than limit" rule is handled like a sliding-window sum: add all ways to append this bit, then subtract the ways that end in a run that just exceeded limit.

Why not another pattern? Enumerating arrays is C(zero + one, zero), astronomically many. A DP that also loops over run lengths is O(z · o · limit); the subtraction trick removes that factor.

Key insight: dp0[i][j] = arrays with i zeros, j ones, ending in 0. Appending a 0 to any array with i − 1 zeros gives dp0[i−1][j] + dp1[i−1][j], but that over-counts arrays whose last limit + 1 bits are all 0. Those are exactly the arrays that ended in 1 before that run started: dp1[i − limit − 1][j]. Symmetrically for dp1.

Approach:

1. Base cases: dp0[i][0] = 1 for 1 ≤ i ≤ limit (only zeros), dp1[0][j] = 1 for 1 ≤ j ≤ limit.
2. dp0[i][j] = dp0[i−1][j] + dp1[i−1][j] − dp1[i−limit−1][j] (when i > limit).
3. dp1[i][j] = dp0[i][j−1] + dp1[i][j−1] − dp0[i][j−limit−1] (when j > limit).
4. Answer: dp0[zero][one] + dp1[zero][one], all modulo 10⁹ + 7.

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10 ** 9 + 7
        # dp0[i][j] / dp1[i][j]: arrays with i zeros and j ones ending in 0 / 1
        dp0 = [[0] * (one + 1) for _ in range(zero + 1)]
        dp1 = [[0] * (one + 1) for _ in range(zero + 1)]
        for i in range(1, min(zero, limit) + 1):
            dp0[i][0] = 1  # only zeros, a run of length i <= limit
        for j in range(1, min(one, limit) + 1):
            dp1[0][j] = 1  # only ones
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                ways0 = dp0[i - 1][j] + dp1[i - 1][j]  # append a 0 to anything
                if i > limit:
                    ways0 = ways0 - dp1[i - limit - 1][j]  # remove arrays now ending in limit+1 zeros
                dp0[i][j] = ways0 % MOD
                ways1 = dp0[i][j - 1] + dp1[i][j - 1]  # append a 1 to anything
                if j > limit:
                    ways1 = ways1 - dp0[i][j - limit - 1]  # remove arrays now ending in limit+1 ones
                dp1[i][j] = ways1 % MOD
        return (dp0[zero][one] + dp1[zero][one]) % MOD

What the code is doing, line by line:

1. Two tables split arrays by their last bit, which is what the run-length rule depends on.
2. Base cases: an array of only zeros is stable only if its single run is at most limit long.
3. ways0 appends a 0 to every array with one fewer zero; the subtraction removes exactly those that now end in a run of limit + 1 zeros (they came from arrays ending in 1 with limit + 1 fewer zeros).
4. % MOD after each step keeps numbers small; Python's % also fixes any negative intermediate value.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• limit ≥ both counts → every arrangement: C(zero + one, zero).
• limit = 1 → the bits must alternate.
• One count much larger than the other (may give 0).

Complexity: O(zero · one) time and space.

Problem: Can one horizontal or one vertical cut split grid into two non-empty parts with equal sums?

Solve it on LeetCode ↗

Constraints: 1 ≤ m == grid.length ≤ 10⁵ · 1 ≤ n == grid[i].length ≤ 10⁵ · 2 ≤ m * n ≤ 10⁵ · 1 ≤ grid[i][j] ≤ 10⁵

From brute force to the pattern: Summing both sides for each of the m − 1 + n − 1 cuts is O((m + n) · m · n). Row and column totals with running prefixes check every cut in O(1).

Spot it: A horizontal cut after row r splits the total into (sum of rows 0..r) and the rest: a running prefix sum over rows (and over columns for vertical cuts).

Why not another pattern? Recomputing each side's sum for every cut is O(m · n) per cut. Prefix sums over row totals and column totals make each cut O(1).

Approach:

1. Compute each row's sum and each column's sum, and the total.
2. If the total is odd, return False.
3. Running prefix over row sums: if it ever equals total / 2 before the last row, return True. Same for columns.

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        row_sums = [sum(row) for row in grid]
        col_sums = [sum(col) for col in zip(*grid)]  # zip(*grid) walks the columns
        total = sum(row_sums)
        if total % 2 == 1:
            return False  # two equal integer halves are impossible
        half = total // 2
        for sums in (row_sums, col_sums):
            prefix = 0
            for i in range(len(sums) - 1):  # a cut must leave both parts non-empty
                prefix = prefix + sums[i]
                if prefix == half:
                    return True
        return False

What the code is doing, line by line:

1. zip(*grid) transposes the grid, so col_sums has one total per column.
2. An odd total can't be split into two equal integers.
3. range(len(sums) - 1): cutting after the last row/column would leave an empty part.
4. A prefix equal to half the total means the rest is the other half.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Odd total → False.
• A single row (only vertical cuts possible).
• The equal split exists only vertically.

Complexity: O(m · n) time, O(m + n) space.

Problem: Count the subarrays in which target appears strictly more than half of the time.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 1000 · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ target ≤ 10⁹

From brute force to the pattern: Counting target in every subarray is O(n²). The ±1 transformation makes it "count pairs of prefixes with prefix[i] < prefix[j]", and because prefixes move by one step at a time, a running counter answers it in O(n).

Spot it: Map target to +1 and everything else to −1. target is the majority exactly when the subarray's sum is positive, i.e. prefix[j] > prefix[i]. So for each prefix, count the earlier prefixes that are smaller.

Why not another pattern? Checking all O(n²) subarrays with running counts also passes for n ≤ 1000. A Fenwick tree over prefix values gives O(n log n). Because prefix sums move by exactly ±1, a single running counter gives O(n).

Key insight: Keep less = number of earlier prefixes smaller than the current prefix. Moving up by 1 adds the prefixes equal to the old value; moving down by 1 removes the prefixes equal to the new value. A count map of prefix values makes both O(1).

Approach:

1. count = {0: 1} (the empty prefix), prefix = 0, less = 0.
2. On target: less += count[prefix], then prefix += 1.
3. Otherwise: prefix −= 1, then less −= count[prefix].
4. Add less to the answer, then record prefix in count.

from collections import defaultdict

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        count = defaultdict(int)  # prefix value -> how many earlier prefixes had it
        count[0] = 1  # the empty prefix
        prefix = 0
        less = 0  # earlier prefixes strictly smaller than the current prefix
        answer = 0
        for x in nums:
            if x == target:
                less = less + count[prefix]  # prefixes equal to the old value are now smaller
                prefix = prefix + 1
            else:
                prefix = prefix - 1
                less = less - count[prefix]  # prefixes equal to the new value are no longer smaller
            answer = answer + less  # each smaller earlier prefix starts a majority subarray
            count[prefix] = count[prefix] + 1
        return answer

What the code is doing, line by line:

1. With ±1 values, a subarray's sum is prefix[j] − prefix[i]; positive means target is the strict majority.
2. less counts earlier prefixes below the current one, which is exactly the number of valid subarrays ending here.
3. Going up by one: every earlier prefix that equalled the old value is now strictly smaller, so add their count.
4. Going down by one: earlier prefixes equal to the new value stop being smaller, so subtract their count.
5. Record the current prefix only after counting, so subarrays are non-empty.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• target not present → 0.
• All elements equal target → n(n + 1)/2.
• Exactly half is not enough ("strictly more than half").

Complexity: O(n) time, O(n) space.

Problem: Return the largest sum of any rectangle in matrix that is no larger than k (one is guaranteed to exist).

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 100 · -100 ≤ matrix[i][j] ≤ 100 · -10⁵ ≤ k ≤ 10⁵

From brute force to the pattern: Every rectangle with a 2-D prefix sum costs O(r² · c²). Fixing the rows reduces it to 1-D, and the sorted prefix list answers "best earlier start" with a binary search instead of a scan.

Spot it: Rectangle sums → fix a top and bottom row, add up each column between them, and the problem becomes 1-D: the best subarray sum ≤ k. A subarray sum is prefix[j] − prefix[i], so for each prefix[j] you want the smallest earlier prefix ≥ prefix[j] − k: a binary search in a sorted list of prefix sums.

Why not another pattern? Kadane's algorithm finds the maximum subarray sum but can't respect the "≤ k" cap. Enumerating every rectangle with a 2-D prefix sum is O(r² · c²).

Approach:

1. For each pair of rows top ≤ bottom, maintain col_sums[c] = sum of column c between them.
2. Scan col_sums with a running prefix sum; keep earlier prefixes in a sorted list (starting with 0).
3. For each prefix p, binary-search the smallest earlier prefix q ≥ p − k; p − q is a candidate ≤ k.
4. Insert p into the sorted list and continue; keep the best candidate.

from bisect import bisect_left, insort

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        best = float("-inf")
        for top in range(rows):
            col_sums = [0] * cols  # column sums between top and bottom
            for bottom in range(top, rows):
                for c in range(cols):
                    col_sums[c] = col_sums[c] + matrix[bottom][c]
                seen = [0]  # sorted prefix sums seen so far (0 = empty prefix)
                prefix = 0
                for value in col_sums:
                    prefix = prefix + value
                    # the smallest earlier prefix q with prefix - q <= k
                    pos = bisect_left(seen, prefix - k)
                    if pos < len(seen):
                        best = max(best, prefix - seen[pos])
                    insort(seen, prefix)  # keep the list sorted
        return best

What the code is doing, line by line:

1. top and bottom fix the rows; col_sums accumulates as bottom moves down, so it never has to be rebuilt from scratch.
2. Inside, it's the 1-D problem on col_sums: a subarray (i, j] has sum prefix − q where q is an earlier prefix.
3. bisect_left(seen, prefix - k) finds the smallest q ≥ prefix − k, which gives the largest sum that is still ≤ k.
4. insort(seen, prefix) inserts while keeping the list sorted (a balanced tree would make this O(log c)).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All negative values.
• k smaller than every positive sum (the answer may be negative).
• A single row or column.

Complexity: O(r² · c log c) with a balanced tree (insort on a list is O(c) per insert, fine for these limits).

Problem: Rotate nums by k; each element v that ends up at an index ≥ v scores a point. Return the smallest k with the highest score.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] < nums.length

From brute force to the pattern: Scoring each of the n rotations from scratch is O(n²). Each element only changes the score at a couple of rotations, so a difference array accumulates all of them in O(n).

Spot it: Trying every rotation and rescoring is O(n²). For one element, the rotations where it scores form a contiguous circular range, so each element contributes "+1 on a range": a difference array over k, then a prefix sum.

Why not another pattern? Simulating every rotation is quadratic; a segment tree would also work but is overkill for range +1 updates read once at the end.

Key insight: Element i with value v moves to index (i − k) mod n. It stops scoring exactly at rotation k = (i − v + 1) mod n and starts scoring again one step after it reaches index n − 1. So record −1 at (i − v + 1) mod n on top of a baseline of +1 per rotation step; the running total is the score change.

Approach:

1. change[k] starts at 1 for every k (each rotation moves one element from index 0 to the back, where it always scores).
2. For each element: change[(i − nums[i] + 1) % n] −= 1 (the rotation where it drops below its value).
3. Prefix-sum change; the index of the maximum is the answer (the first one on ties).

class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        change = [1] * n  # each step, the element moved to the back gains a point
        for i in range(n):
            change[(i - nums[i] + 1) % n] = change[(i - nums[i] + 1) % n] - 1  # rotation where it starts losing its point
        for k in range(1, n):
            change[k] = change[k] + change[k - 1]  # prefix sum: relative score of rotation k
        best_k = 0
        for k in range(n):
            if change[k] > change[best_k]:
                best_k = k  # strictly better keeps the smallest k on ties
        return best_k

What the code is doing, line by line:

1. change holds how the score changes from rotation k − 1 to k; the baseline 1 is the element wrapping to the end.
2. (i - nums[i] + 1) % n: at this rotation, element i sits one index too low to score, so the score drops by one.
3. The prefix sum turns changes into relative scores (all shifted by the same constant, which doesn't affect the argmax).
4. Strict > keeps the smallest k among equal scores.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single element → 0.
• Several rotations tie for the best score: return the smallest.
• All zeros: every rotation scores n.

Complexity: O(n) time and space.

Problem: Make one horizontal or vertical cut. The two parts must have equal sums, or become equal after discounting one cell from one part, provided that part stays connected without it. Is it possible?

Solve it on LeetCode ↗

Constraints: 1 ≤ m == grid.length ≤ 10⁵ · 1 ≤ n == grid[i].length ≤ 10⁵ · 2 ≤ m * n ≤ 10⁵ · 1 ≤ grid[i][j] ≤ 10⁵

From brute force to the pattern: For every cut, trying every cell and running a connectivity check is O((m · n)²) or worse. Sums come from prefix sums, value lookups from counters, and connectivity from the rectangle's shape, so each cut is O(n) and the whole check is linear.

Spot it: For each cut, prefix sums give both part sums in O(1). The difference d must be 0, or equal to the value of a removable cell in the heavier part. Value counts per part (a hash map updated as the cut moves) answer "is there a cell worth d?" in O(1).

Why not another pattern? Trying every cut and every cell is O((m · n)²). A full connectivity check per removal is unnecessary: the shape of a rectangle tells you which cells are safe.

Key insight: A rectangular part with at least 2 rows and 2 columns stays connected after removing any single cell. A part that is a single row or a single column only stays connected if you remove one of its two end cells. So: count values in each part; for thin parts, check just the two ends.

Approach:

1. Handle horizontal cuts on grid and on its transpose (vertical cuts become horizontal).
2. Move the cut down one row at a time, keeping the top sum and value counts for top and bottom.
3. Let d = top − bottom. d == 0 → True. If d > 0, look for a removable cell worth d in the top part; if d < 0, one worth −d in the bottom part.
4. Removable: any cell if the part has ≥ 2 rows and ≥ 2 columns; otherwise only the two end cells of that line.

from collections import Counter

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def check(g):
            m = len(g)
            n = len(g[0])
            total = sum(map(sum, g))
            top_count = Counter()
            bottom_count = Counter(v for row in g for v in row)
            top = 0
            for i in range(m - 1):  # cut after row i
                for v in g[i]:
                    top_count[v] = top_count[v] + 1  # row i moves from bottom to top
                    bottom_count[v] = bottom_count[v] - 1
                top = top + sum(g[i])
                bottom = total - top
                d = top - bottom
                if d == 0:
                    return True
                if d > 0:  # discount a cell worth d from the top part (rows 0..i)
                    if n == 1:
                        ends = {g[0][0], g[i][0]}  # a single column: only its ends
                    elif i == 0:
                        ends = {g[0][0], g[0][n - 1]}  # a single row: only its ends
                    else:
                        ends = None  # a thick rectangle: any cell can go
                    if (ends is not None and d in ends) or (ends is None and top_count[d] > 0):
                        return True
                else:  # discount a cell worth -d from the bottom part (rows i+1..m-1)
                    need = -d
                    if n == 1:
                        ends = {g[i + 1][0], g[m - 1][0]}
                    elif i + 1 == m - 1:
                        ends = {g[m - 1][0], g[m - 1][n - 1]}
                    else:
                        ends = None
                    if (ends is not None and need in ends) or (ends is None and bottom_count[need] > 0):
                        return True
            return False

        transposed = [list(col) for col in zip(*grid)]  # vertical cuts = horizontal cuts of the transpose
        return check(grid) or check(transposed)

What the code is doing, line by line:

1. check(g) tries every horizontal cut; calling it on the transpose covers vertical cuts.
2. As the cut moves down, row i moves from the bottom counter to the top counter, and top grows by that row's sum.
3. d == 0: equal without discounting anything.
4. A part with one column or one row is a line; removing a middle cell would split it, so only its two ends may be discounted.
5. Otherwise the part is at least 2 × 2 and any cell can be discounted; the counter says whether a cell with the needed value exists.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal sums without discounting.
• A single-column grid (only end cells can be discounted).
• The needed value exists but only in the middle of a thin part → not allowed.

Complexity: O(m · n) time and space (each row moves between the counters once, for each of the two orientations).

Problem: Count arrays of length n with values in [l, r] where adjacent values differ and no three consecutive values are strictly increasing or strictly decreasing (so the direction must alternate), modulo 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 3 ≤ n ≤ 2000 · 1 ≤ l < r ≤ 2000

From brute force to the pattern: Enumerating arrays is exponential, and a DP that loops over every previous value is O(n · m²). Prefix sums of each DP row turn every transition into O(1).

Spot it: A sequence built step by step, where the next value depends on the last value and the last direction: DP. Each transition sums over all smaller (or larger) previous values, which is a prefix sum over the DP row.

Why not another pattern? Summing over all previous values directly is O(n · m²) (8·10⁹ for m = 2000). Prefix sums of the previous row make it O(n · m).

Key insight: Let up[v] = arrays ending at v whose last step went up, and down[v] = last step went down. Directions alternate, so new_up[v] = Σ down[u] for u < v and new_down[v] = Σ up[u] for u > v. Both are prefix/suffix sums of the previous row.

Approach:

1. Work with offsets 0..m−1 where m = r − l + 1.
2. Length 2: up[v] = v (any smaller first value), down[v] = m − 1 − v.
3. For each further length, build prefix sums of down and suffix sums of up to compute the next row.
4. Answer: sum(up) + sum(down) after reaching length n.

from itertools import accumulate

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10 ** 9 + 7
        m = r - l + 1  # number of possible values
        up = [v for v in range(m)]  # length 2 arrays ending at v after a step up
        down = [m - 1 - v for v in range(m)]  # ... after a step down
        for _ in range(n - 2):
            below = [0] + list(accumulate(down))  # below[v] = sum of down[0..v-1]
            above = list(accumulate(reversed(up)))[::-1] + [0]  # above[v] = sum of up[v..m-1]
            new_up = [below[v] % MOD for v in range(m)]  # previous step went down, now go up to v
            new_down = [above[v + 1] % MOD for v in range(m)]  # previous step went up, now go down to v
            up = new_up
            down = new_down
        return (sum(up) + sum(down)) % MOD

What the code is doing, line by line:

1. Values only matter relative to each other, so work with 0..m−1.
2. Length 2: to arrive at v by going up, the first value is any of the v smaller ones.
3. below[v] = total of down over values smaller than v (a prefix sum), so new_up[v] = arrays that just went down and now go up to v.
4. above[v + 1] = total of up over values larger than v (a suffix sum), giving new_down[v].
5. After n − 2 extensions the arrays have length n; add both directions.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 3 and only two values, e.g. l = 4, r = 5 → 2.
• Large n and m (keep everything modulo 10⁹ + 7).
• Adjacent equal values are never allowed.

Complexity: O(n · m) time, O(m) space.

Problem: Person x requests y unless y ≤ 0.5·x + 7, y > x, or (y > 100 and x < 100). Count all requests.

Solve it on LeetCode ↗

Constraints: n == ages.length · 1 ≤ n ≤ 2 * 10⁴ · 1 ≤ ages[i] ≤ 120

From brute force to the pattern: All pairs: O(n²). Age counting with prefix sums: O(n).

Spot it: Only ages matter and there are just 120 of them. Count people per age; with prefix sums, the number of valid targets for age x is the count in (0.5x + 7, x], minus one for the person themself.

Why not another pattern? Checking all pairs of up to 2·10⁴ people is 4·10⁸ comparisons.

Approach:

1. count[a] per age; prefix[a] = people aged ≤ a.
2. For each age x with people: if x ≤ 14 nobody qualifies (the range is empty).
3. Targets = prefix[x] − prefix[x // 2 + 7] − 1; add count[x] · targets.

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for a in ages:
            count[a] += 1
        prefix = [0] * 121  # prefix[a]: people aged <= a
        for a in range(1, 121):
            prefix[a] = prefix[a - 1] + count[a]
        requests = 0
        for x in range(15, 121):  # for x <= 14, nobody satisfies 0.5x + 7 < y <= x
            if count[x]:
                targets = prefix[x] - prefix[x // 2 + 7] - 1  # ages in (x/2 + 7, x], minus themself
                requests += count[x] * targets
        return requests

What the code is doing, line by line:

1. y > 0.5x + 7 for integers means y ≥ x // 2 + 8, so subtracting prefix[x // 2 + 7] removes everyone too young.
2. The third rule is implied by y ≤ x, so it never matters.
3. Each person of age x sends to every valid target except themself.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Everyone younger than 15 → 0.
• Many people of the same age.
• Ages above 100.

Complexity: O(n + 120) time, O(120) space.

Problem: For each query [l, r], count the plates * lying between two candles | inside s[l..r].

Solve it on LeetCode ↗

Constraints: 3 ≤ s.length ≤ 10⁵ · s consists of '*' and '|' characters. · 1 ≤ queries.length ≤ 10⁵ · queries[i].length == 2 · 0 ≤ lefti ≤ righti < s.length

From brute force to the pattern: Scanning each query is O(nq); nearest-candle arrays plus prefix sums make it O(n + q).

Spot it: Only plates between the first candle at or after l and the last candle at or before r count. Precompute those nearest candles and a prefix count of plates, then each query is O(1).

Why not another pattern? Scanning each query's substring is O(n · q).

Approach:

1. plates[i] = plates in s[:i].
2. next_candle[i] (scan from the right) and prev_candle[i] (from the left).
3. Query: a = next_candle[l], b = prev_candle[r]; if a < b: plates[b] − plates[a], else 0.

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        plates = [0] * (n + 1)  # plates[i]: '*' in s[:i]
        for i, ch in enumerate(s):
            plates[i + 1] = plates[i] + (ch == "*")
        prev_candle = [-1] * n  # nearest '|' at or before i
        last = -1
        for i, ch in enumerate(s):
            if ch == "|":
                last = i
            prev_candle[i] = last
        next_candle = [n] * n  # nearest '|' at or after i
        nxt = n
        for i in range(n - 1, -1, -1):
            if s[i] == "|":
                nxt = i
            next_candle[i] = nxt
        answer = []
        for l, r in queries:
            a, b = next_candle[l], prev_candle[r]  # the candles that enclose plates in [l, r]
            answer.append(plates[b] - plates[a] if a < b else 0)
        return answer

What the code is doing, line by line:

1. Plates outside the outermost candles of the query can't be between two candles.
2. plates[b] − plates[a] counts plates strictly between positions a and b (both candles).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No candles in the range → 0.
• Only one candle → 0.
• Queries covering the whole string.

Complexity: O(n + q) time, O(n) space.

Problem: Count submatrices that contain grid[0][0], have equally many X and Y, and at least one X.

Solve it on LeetCode ↗

Constraints: 1 ≤ grid.length, grid[i].length ≤ 1000 · grid[i][j] is either 'X', 'Y', or '.'.

From brute force to the pattern: Recounting each of the mn prefix rectangles is O((mn)²); prefix sums make it O(mn).

Spot it: Containing the top-left cell means each submatrix is grid[0..i][0..j], i.e. a 2D prefix. Keep prefix sums of X − Y and of X.

Why not another pattern? Counting each prefix submatrix from scratch is O((mn)²).

Approach:

1. Running column sums per row: diff[j] (X − Y) and xs[j] (X count) for rows 0..i.
2. Sweep j left to right accumulating them into the prefix of row i.
3. Count (i, j) with prefix diff 0 and prefix X > 0.

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        cols = len(grid[0])
        col_diff = [0] * cols  # X - Y in column j over rows 0..i
        col_x = [0] * cols  # number of X in column j over rows 0..i
        count = 0
        for row in grid:
            diff = xs = 0  # totals of the prefix grid[0..i][0..j]
            for j, ch in enumerate(row):
                col_diff[j] += (ch == "X") - (ch == "Y")
                col_x[j] += ch == "X"
                diff += col_diff[j]
                xs += col_x[j]
                if diff == 0 and xs > 0:
                    count += 1  # balanced and contains an X
        return count

What the code is doing, line by line:

1. Column totals grow row by row; summing them left to right gives each prefix rectangle.
2. Booleans add as 0/1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No X anywhere → 0.
• One row.
• Balanced but without X (all dots) doesn't count.

Complexity: O(m · n) time, O(n) space.

Problem: Each query multiplies nums[l], nums[l + k], … (up to r) by v mod 10⁹ + 7. Return the XOR of the final array.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10³ · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ q == queries.length ≤ 10³ · queries[i] = [li, ri, ki, vi] · 0 ≤ li ≤ ri < n · 1 ≤ ki ≤ n · 1 ≤ vi ≤ 10⁵

From brute force to the pattern: This is the direct simulation, fast enough here.

Spot it: With n, q ≤ 1000, a direct simulation costs at most 10⁶ updates. (Version II, with 10⁵, needs a stepped multiplicative difference array — see the next problem.)

Why not another pattern? Anything fancier is unnecessary at this size.

Approach:

1. For each query, loop i in range(l, r + 1, k) and multiply.
2. XOR all values.

from functools import reduce
from operator import xor

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        for l, r, k, v in queries:
            for i in range(l, r + 1, k):  # every k-th index in [l, r]
                nums[i] = nums[i] * v % MOD
        return reduce(xor, nums)

What the code is doing, line by line:

1. range(l, r + 1, k) visits exactly the indices the query touches.
2. XOR isn't compatible with the multiplications, so it's computed once at the end.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 (every index).
• k > r − l (one index).
• Large products (mod).

Complexity: O(q · n) time in the worst case (k = 1), O(1) extra space.

Problem: For each query, concatenate the non-zero digits of s[l..r] into x and return x · (sum of its digits) mod 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 1 ≤ m == s.length ≤ 10⁵ · s consists of digits only. · 1 ≤ queries.length ≤ 10⁵ · queries[i] = [li, ri] · 0 ≤ li ≤ ri < m

From brute force to the pattern: Concatenating per query is O(n) each; prefix values answer each in O(1).

Spot it: Like a rolling hash: P[i] is the number formed by the non-zero digits of s[:i] (mod p). The digits of a range are P[r + 1] with the prefix P[l] shifted out: subtract P[l] · 10^c where c is how many non-zero digits lie in the range. Prefix sums give c and the digit sum.

Why not another pattern? Building the number per query is O(n) each.

Approach:

1. Prefix arrays: P (number mod p), cnt (non-zero digits), dsum (digit sum), and powers of 10.
2. Query: c = cnt[r+1] − cnt[l], x = (P[r+1] − P[l] · 10^c) mod p, sum = dsum[r+1] − dsum[l].
3. Answer x · sum mod p.

class Solution:
    def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        n = len(s)
        P = [0] * (n + 1)  # non-zero digits of s[:i] read as a number, mod MOD
        cnt = [0] * (n + 1)  # how many non-zero digits in s[:i]
        dsum = [0] * (n + 1)  # their digit sum
        for i, ch in enumerate(s):
            d = int(ch)
            if d:
                P[i + 1] = (P[i] * 10 + d) % MOD
                cnt[i + 1] = cnt[i] + 1
            else:
                P[i + 1] = P[i]
                cnt[i + 1] = cnt[i]
            dsum[i + 1] = dsum[i] + d
        pow10 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow10[i] = pow10[i - 1] * 10 % MOD
        answer = []
        for l, r in queries:
            c = cnt[r + 1] - cnt[l]
            x = (P[r + 1] - P[l] * pow10[c]) % MOD  # drop the digits before l
            answer.append(x * (dsum[r + 1] - dsum[l]) % MOD)
        return answer

What the code is doing, line by line:

1. Appending a digit multiplies the number by 10 and adds it, exactly like a polynomial hash.
2. The prefix P[l] has been shifted left by c digits by position r + 1, so it's removed with P[l] · 10^c.
3. Zeros are skipped in P but don't affect the digit sum anyway.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only zeros in the range → 0.
• Single digit.
• Long ranges (mod arithmetic).

Complexity: O(n + q) time, O(n) space.

Problem: nums is a permutation of 1..n. Count subarrays whose median (lower middle for even length) equals k.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 10⁵ · 1 ≤ nums[i], k ≤ n · The integers in nums are distinct.

From brute force to the pattern: Checking every subarray's median is O(n³ log n) (or O(n²) with care); balance counting is O(n).

Spot it: Only whether each value is above or below k matters. With +1 for bigger and −1 for smaller, a subarray containing k has median k exactly when its balance is 0 (odd length) or 1 (even length). Count matching prefix balances on each side of k with a hash map.

Why not another pattern? Sorting every subarray to find its median is O(n³ log n).

Approach:

1. Find p, the index of k.
2. Walk left from p: record how many left extensions give each balance (left[bal], including the empty one with 0).
3. Walk right from p: for each right balance r, add left[−r] + left[1 − r].

from collections import Counter

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        p = nums.index(k)
        left = Counter({0: 1})  # balance of nums[i..p-1] for every start i <= p
        bal = 0
        for i in range(p - 1, -1, -1):
            bal += 1 if nums[i] > k else -1
            left[bal] += 1
        count = 0
        bal = 0
        for j in range(p, len(nums)):  # end of the subarray
            if j > p:
                bal += 1 if nums[j] > k else -1
            count += left[-bal] + left[1 - bal]  # total balance 0 (odd length) or 1 (even length)
        return count

What the code is doing, line by line:

1. Median k with odd length means as many values above as below k: balance 0.
2. With even length the lower middle is k, so there is one more value above: balance 1.
3. Left and right parts combine by adding balances, so each right balance needs a matching left one.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k at either end.
• Even-length subarrays (balance 1).
• n = 1.

Complexity: O(n) time and space.

Problem: Same as version I but n, q ≤ 10⁵: apply all stepped range multiplications, then XOR the array.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ q == queries.length ≤ 10⁵ · queries[i] = [li, ri, ki, vi] · 0 ≤ li ≤ ri < n · 1 ≤ ki ≤ n · 1 ≤ vi ≤ 10⁵

From brute force to the pattern: Direct simulation is O(nq); splitting by √n bounds every part by O((n + q)√n).

Spot it: A query with step k ≥ √n touches at most √n indices: apply it directly. For a small k, use a difference array along the progression: multiply diff[l] by v and the first index past the range by v⁻¹, then a prefix product with stride k spreads it.

Why not another pattern? Direct simulation is O(n · q) = 10¹⁰ when k = 1.

Approach:

1. B = ⌈√n⌉. Large k: loop the indices.
2. Small k: diff[k][l] *= v; stop = l + ((r − l) // k + 1) · k; if stop < n, diff[k][stop] *= v⁻¹ (Fermat inverse).
3. For each used k: diff[i] *= diff[i − k] left to right, then nums[i] *= diff[i].
4. XOR everything.

from collections import defaultdict
from functools import reduce
from operator import xor

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        B = int(n ** 0.5) + 1
        diff = defaultdict(lambda: [1] * n)  # one stepped difference array per small k
        for l, r, k, v in queries:
            if k >= B:
                for i in range(l, r + 1, k):  # at most sqrt(n) indices
                    nums[i] = nums[i] * v % MOD
            else:
                d = diff[k]
                d[l] = d[l] * v % MOD  # start multiplying at l
                stop = l + ((r - l) // k + 1) * k  # first index of the progression past r
                if stop < n:
                    d[stop] = d[stop] * pow(v, MOD - 2, MOD) % MOD  # cancel it from there on
        for k, d in diff.items():
            for i in range(n):
                if i >= k:
                    d[i] = d[i] * d[i - k] % MOD  # prefix product along step k
                nums[i] = nums[i] * d[i] % MOD
        return reduce(xor, nums)

What the code is doing, line by line:

1. A difference array turns "multiply a range" into two point updates; the prefix product (with the same step) rebuilds the multiplier at every index.
2. Indices of one progression share i mod k, so stepping by k keeps different progressions separate.
3. v⁻¹ = v^(p − 2) mod p because p is prime, and v < p so the inverse exists.
4. Large steps are cheap to do directly, so the work is O(q √n + n √n).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All queries with k = 1.
• A range ending exactly at the last index.
• Repeated k values.

Complexity: O((n + q) √n + q log p) time, O(n √n) space in the worst case.

Problem: Apply range shifts (forward or backward, wrapping a–z) to s. Return the final string.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length, shifts.length ≤ 5 * 10⁴ · shifts[i].length == 3 · 0 ≤ starti ≤ endi < s.length · 0 ≤ directioni ≤ 1 · s consists of lowercase English letters.

From brute force to the pattern: Per-shift loops are O(nq); the difference array is O(n + q).

Spot it: Many range updates followed by one read → a difference array: mark each range's start and end, then a prefix sum gives every position's total.

Why not another pattern? Applying each shift to every letter in its range is O(n · q).

Approach:

1. diff[l] += d, diff[r + 1] −= d (d = ±1).
2. Running sum gives the shift of each letter; apply it mod 26.

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        diff = [0] * (len(s) + 1)
        for start, end, direction in shifts:
            d = 1 if direction else -1
            diff[start] += d  # the shift begins here
            diff[end + 1] -= d  # and stops after end
        out = []
        total = 0
        for i, ch in enumerate(s):
            total += diff[i]  # net shift for position i
            out.append(chr((ord(ch) - 97 + total) % 26 + 97))
        return "".join(out)

What the code is doing, line by line:

1. The prefix sum of the difference array is the total shift at each index.
2. Python's % wraps negative shifts correctly.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Wrap-around (z → a).
• Net zero shifts.
• Single letter.

Complexity: O(n + q) time, O(n) space.

Problem: Build a matrix where each cell is the product of all other cells, modulo 12345.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == grid.length ≤ 10⁵ · 1 ≤ m == grid[i].length ≤ 10⁵ · 2 ≤ n * m ≤ 10⁵ · 1 ≤ grid[i][j] ≤ 10⁹

From brute force to the pattern: Multiplying all other cells per cell is O((nm)²); prefix/suffix products are O(nm).

Spot it: Product of everything except self, like Product of Array Except Self: prefix and suffix products over the flattened matrix. Division isn't possible modulo 12345 (not prime), so prefix/suffix it is.

Why not another pattern? Dividing the total by each cell fails: 12345 isn't prime, and cells can be multiples of its factors.

Approach:

1. Flatten in row-major order.
2. Forward pass: ans[i] = prefix; prefix *= a[i].
3. Backward pass: ans[i] *= suffix; suffix *= a[i].

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        n, m = len(grid), len(grid[0])
        flat = [x % MOD for row in grid for x in row]
        ans = [1] * len(flat)
        prefix = 1
        for i, x in enumerate(flat):
            ans[i] = prefix  # product of everything before i
            prefix = prefix * x % MOD
        suffix = 1
        for i in range(len(flat) - 1, -1, -1):
            ans[i] = ans[i] * suffix % MOD  # times everything after i
            suffix = suffix * flat[i] % MOD
        return [ans[r * m:(r + 1) * m] for r in range(n)]

What the code is doing, line by line:

1. The order of the cells doesn't matter for a product, so the matrix is treated as one array.
2. Reducing mod 12345 at every step keeps numbers small.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Cells that are multiples of 12345 (zero products).
• One row.
• 1 × 2 matrix.

Complexity: O(n · m) time and space.