Topic 1: Arrays & Hashing

This includes prefix-sum type questions as well

Canonical Questions #

String simulations #

These problems involve doing some operations on strings. The key idea here is that we should be exploiting string-specific APIs that python provides. Other things could be that instead of actually doing the hard operations, it might make sense to do soft simulations of the applications to solve some of these problems.

Problems #

1. Process String with Special Operations I (3612)

   I have an on optimal solution that works well enough for the constraints by actually carrying out the processes. Optimisations would be amortising things (soft deletes, lazy reversal flags) OR some other way to simulate without the memory overheads.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution: def processStr(self, s: str) -> str: """ It's a string state management exercise, might need to find ways to do this efficiently. Okay this works, a better approach is likely to amortise the expensive operations, keep a "is_reversed" flag and then try not to copy over on the reversed operations and just pop and all that when we need, I guess a soft delete would work as well, and we can filter it out at the end when joining the list into a string. """ res = [] for char in s: if char == "#": res += res continue if char == "%": res = res[::-1] continue if char == "*": res = res[:-1] continue res.append(char) return "".join(res)

   Code Snippet 1: Process String with Special Operations I (3612)
   Pattern Extraction

   Core Insight: When operations mutate a collection, consider whether you can defer expensive operations using flags (lazy reversal, soft deletes) rather than executing them immediately.

   Pattern Name: Lazy Simulation / Deferred Operations

   Canonical Section: Arrays & Hashing > String Simulations

   Recognition Signals:

   • A sequence of operations mutates a data structure (append, delete, reverse, duplicate)
   • Some operations are expensive if executed eagerly (\(O(n)\) reversal, \(O(n)\) duplication)
   • Constraints allow naive simulation (small input) OR require amortisation (large input)
   • Operations compose — their cumulative effect can be computed without intermediate materialisation

   Anti-Signals:

   • Operations don’t compose (each depends on the materialised intermediate state) — must simulate eagerly
   • Output requires intermediate states, not just the final result — can’t defer
   • Constraints are small enough that naive simulation is fine — over-engineering wastes time

   Decision Point: If constraints are generous (\(n \leq 10^3\)), simulate directly. If tight (\(n \leq 10^5\)), look for deferred/lazy patterns. The tell is whether operations are associative or composable.

   Pitfalls and Misconceptions

   1. Trap: Implementing reversal by actually reversing the list each time. Why: Each reversal is \(O(n)\); with \(m\) reversal operations this becomes \(O(mn)\), which TLEs on large inputs. Correction: Use a boolean is_reversed flag and adjust append/pop logic based on flag state.

      1. Trap: Forgetting that duplication (#) doubles the size, which can cause memory explosion.

      Why: Repeated doublings produce exponential sizes (\(2^k \cdot n\)); materialising these overflows memory. Correction: For the follow-up (3614), track virtual size rather than materialising the string.

   Problem Mutations

   1. What if the string could be \(10^6\) characters with \(10^6\) operations? (stress-tests: eager simulation) Naive simulation TLEs. Need lazy flags for reversal and soft deletes, only materialising at the end.

      1. What if you needed the character at index \(k\) without materialising the full string? (stress-tests: materialisation assumption)

      This IS Problem 3614. Forward pass for virtual size, reverse pass with inverse operations to find the character at index \(k\). Connects to LC 1545 Find Kth Bit in Nth Binary String.

      1. What if operations included conditional branching (e.g., “if length > K, reverse”)? (stress-tests: composability)

      Lazy flags break because the decision depends on materialised state. Must simulate eagerly or batch process between branch points.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Process String with Special Operations I generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Process String with Special Operations II (3614) Here, we will observe that if we actually carry out the operations, they are too expensive. Therefore, our objective should be to do soft simulations on these operations. This is a reverse simulation that we’d need to do, so we can do a 2 pass approach on this. First one is to find out the final length of the output string, then we will use the inverse of each process and do some logic there.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   class Solution: def processStr(self, s: str, k: int) -> str: """ This is virtual simulation of the string operations, instead of directly simulating it. We won't construct the string and operate on it, we will work backwards, doing the inverse operations. We shall do 2 passes: 1. find the final length, early return if not satisfactory 2. in reverse order of the input, we carry out inverse operations. we can early return when the char count matches k. """ # first pass: final length calculation size = 0 for c in s: if c.islower(): size += 1 elif c == "*" and size > 0: # remover, pops 1 out size -= 1 elif c == "#": # duplicator size *= 2 # early returns if out of bounds index if not (0 <= k < size): return '.' # 2nd pass, inverse simulation: for c in reversed(s): if c.islower(): size -= 1 # found the char: if k == size: return c elif c == "*": # inverse of poping is pushing size += 1 elif c == "#": # inverse of doubling is halving, but need to be careful if we need to rotate k size //= 2 if k >= size: # is in theright half k -= size elif c == "%": # need to flip it: k = size - 1 - k return "."

   Code Snippet 2: Process String with Special Operations II (3614)
   Pattern Extraction

   Core Insight: When you only need a single character from a massive virtual string, don’t build the string — trace backwards through the operations using their inverses to find which original character maps to position \(k\). Pattern Name: Reverse Virtual Simulation / Inverse Operation Tracing Canonical Section: Arrays & Hashing > String Simulations Recognition Signals:

   • Operations produce an exponentially large output (doubling, tripling)
   • Query asks for a specific position in the final output, not the whole output
   • Each operation has a well-defined inverse (halving undoes doubling, un-reversing undoes reversing)
   • Two-pass structure: forward for size, backward for content

   Anti-Signals:

   • Need the entire output string — can’t avoid materialisation
   • Operations don’t have clean inverses (e.g., lossy operations like modular arithmetic)
   • Multiple queries at different positions — might need to build a more complete data structure

   Decision Point: The size explosion (doubling) combined with a point query is the tell. If you see “find character at index \(k\) after \(n\) operations where some operations double/triple,” it’s reverse virtual simulation.

   Pitfalls and Misconceptions

   1. Trap: Trying to build the actual string and index into it. Why: Doubling creates strings of size \(2^k\); even a modest number of doublings overflows memory. Correction: Forward pass computes virtual size only; backward pass traces the index using inverse operations.

      1. Trap: Getting the halving logic wrong when \(k\) falls in the second half of a doubled string.

      Why: After halving, if \(k \geq \text{size}\), the character is in the duplicated copy and needs k - size= to map back to the original half. Correction: After size // 2=, check if k > size: k -= size=. This mirrors the index into the original half.

      1. Trap: Forgetting to handle the reversal inverse correctly.

      Why: Reversing a string of length \(n\) maps index \(k\) to \(n - 1 - k\). Missing this produces wrong characters. Correction: For %, apply k = size - 1 - k in the backward pass.

   Problem Mutations

   1. What if there were \(10^5\) point queries instead of one? (stress-tests: single-query assumption) Each query needs its own backward trace: \(O(n)\) per query, \(O(qn)\) total. For many queries, consider building a segment-tree-like structure over the operations.

      1. What if the operations included insertion at arbitrary positions? (stress-tests: invertibility)

      Insertion doesn’t have a clean positional inverse without tracking insertion points. Would need an augmented data structure like an order-statistic tree.

      1. What if you needed a contiguous substring \([k, k+m)\) instead of a single character? (stress-tests: point query assumption)

      Could trace each position independently (\(O(mn)\)) or batch-trace positions that share operation paths. Connects to range query optimisation patterns.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Process String with Special Operations II generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

3. Sort Vowels in a String (2785)

   This is just a simple string manipulation, we’re just focused on constructing something efficiently. My solution uses a Counter and a generator (iterator) to spit out the next values for vowels, when we come across them. Some useful tips for this would be to directly use sets instead of lists for such direct membership checks with characters.

   1 2 3 4 5 6 7 8 9 10 11 12 13

   class Solution: def sortVowels(self, s: str) -> str: vowels = set("aeiouAEIOU") # set allows for fast membership checks sorted_vowels = sorted([ch for ch in s if ch in vowels]) res = [] idx = 0 for ch in s: if ch in vowels: res.append(sorted_vowels[idx]) idx += 1 else: res.append(ch) return "".join(res)

   Code Snippet 3: Sort Vowels in a String (2785)
   Pattern Extraction

   Core Insight: When you need to reorder only a subset of elements while preserving the rest in place, extract the subset, sort it, and re-insert using an index pointer. Pattern Name: Selective In-Place Reordering Canonical Section: Arrays & Hashing > String Simulations Recognition Signals:

   • Only a subset of elements needs reordering (vowels, digits, specific characters)
   • Non-target elements must stay in their original positions
   • The reordering rule is simple (sorting, reversing, cycling)

   Anti-Signals:

   • All elements need reordering — just sort the whole thing
   • The reordering depends on the positions of non-target elements — subset extraction loses position context
   • Need to reorder in-place with \(O(1)\) space — extraction uses \(O(k)\) space

   Decision Point: “Reorder X while keeping Y fixed” is the phrase that triggers this pattern. If \(X\) is a small, easily identifiable subset, extract-sort-reinsert is the cleanest approach.

   Pitfalls and Misconceptions

   1. Trap: Using a list for vowel membership checks instead of a set.

   Why: in on a list is \(O(k)\); on a set it’s \(O(1)\). With 10 vowels it’s barely noticeable, but it’s a bad habit that scales poorly. Correction: Use vowels = set("aeiouAEIOU") for \(O(1)\) lookups.

   1. Trap: Forgetting that vowels include both uppercase and lowercase variants.

   Why: Missing uppercase vowels means some vowels aren’t extracted, producing incorrect output. Correction: Include all 10 variants: set("aeiouAEIOU").

   Problem Mutations

   1. What if instead of sorting vowels, you needed to reverse them? (stress-tests: sort assumption)

   Same extract-reinsert pattern, just reverse instead of sort. The pattern generalises to any permutation of the extracted subset.

   1. What if you needed to sort consonants instead of vowels? (stress-tests: subset definition)

   Complement the membership check. The algorithm is identical; only the predicate changes.

   1. What if the string were a stream and you needed to output characters one at a time? (stress-tests: offline assumption)

   Can’t pre-extract and sort. Would need an online data structure (e.g., a heap for the vowel buffer). Connects to LC 295 Find Median from Data Stream. (notes)

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Sort Vowels in a String generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Prefix sums / Subarray Sum = K (prefix sum + hashmap) #

• The key idea for such problems is to rely on preprocessed prefix/suffix arrays to help make local decisions better.

  Typically we can expect multiple passes of the input so that we can rely on some preprocessed auxiliary working to help us get to the answer.

  • These problems may also deal with contiguous segments (subarrays) and searching for some condition to be met.
  • The idea here is that we can create prefix sums and that can be our target that we might want to search for, so it’s also like a 2sum searchability problem
  • Also classic use when we care about range sums and the like.

• this type of problem is actually also a DP problem. The main reason why is that the order of filling matters for us (so that we avoid double counting).

Problems #

1. Product of Array Except Self (238)

   This is a classic problem. It’s just a prefix / suffix processing that we need to do. It’s just a 2 pass that we do here. The intuition is that we need to rely on partial running subs from left/right.

   The space optimisation has this odd rule where it doesn’t include the output array, so we can just store the intermediate values within that output array, and reuse it – effectively using no extra space.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) output = [1] * n # handle the prefixes first prefix = 1 for i in range(n): output[i] = prefix prefix *= nums[i] # now handle the suffixes suffix = 1 for i in range(n - 1, -1, -1): output[i] *= suffix suffix *= nums[i] return output

   Code Snippet 4: Product of Array Except Self (238)
   Pattern Extraction

   Core Insight: The product of everything except index \(i\) is the product of everything to its left times the product of everything to its right — two prefix/suffix sweeps avoid division entirely. Pattern Name: Prefix-Suffix Decomposition Canonical Section: Arrays & Hashing > Prefix Sums Recognition Signals:

   • “Compute something for each index that depends on all other elements”
   • Division is explicitly disallowed or problematic (zeros in the array)
   • The operation is associative (product, sum, gcd, xor)
   • Two-pass structure: left-to-right accumulation, right-to-left accumulation

   Anti-Signals:

   • Division is allowed and there are no zeros — just compute total product and divide
   • The operation is not associative (e.g., subtraction) — prefix-suffix doesn’t decompose cleanly
   • Need online/streaming results — can’t do the second pass

   Decision Point: “Product/sum of all except self” without division is the canonical trigger. The moment you see “without using division,” reach for prefix-suffix decomposition. Interviewer Comms: “I’ll do two passes. First left-to-right, accumulating a running prefix product into the output array. Then right-to-left, multiplying each position by the running suffix product. Each position ends up holding left-product times right-product, which is the product of everything except itself. \(O(n)\) time, \(O(1)\) extra space since the output array doesn’t count.”

   Pitfalls and Misconceptions

   1. Trap: Reaching for division (total product / nums[i]). Why: Fails when nums[i] = 0=. Also, the problem explicitly forbids division. Correction: Use the two-pass prefix-suffix approach.
   2. Trap: Using two separate arrays for prefix and suffix products. Why: Works but uses \(O(n)\) extra space. The problem asks for \(O(1)\) extra space (output array excluded). Correction: Store prefix products in the output array during the first pass, then multiply in suffix products during the second pass using a single rolling variable.
   3. Trap: Off-by-one in the prefix/suffix accumulation — including nums[i] in its own product. Why: The prefix at index \(i\) must be the product of \([0, i)\), not \([0, i]\). Including nums[i] double-counts it. Correction: Update the output before updating the running product: output[i] = prefix; prefix * nums[i]=.
   Problem Mutations

   1. What if the array contains zeros? (stress-tests: division shortcut) Prefix-suffix still works perfectly. Division-based approaches fail. This is why the prefix-suffix pattern is strictly more general.
   2. What if you needed sum-except-self instead of product? (stress-tests: operation type) Identical pattern, replace multiplication with addition. Or just compute total sum and subtract: total - nums[i]. The prefix-suffix approach generalises to any associative operation.
   3. What if the array were updated online and you needed to re-query? (stress-tests: static assumption) Prefix-suffix requires \(O(n)\) rebuild per update. For online updates, use a segment tree with range products: \(O(\log n)\) per update and query. Connects to LC 307 Range Sum Query - Mutable.
   4. What if you needed the product of all except a contiguous subarray \([l, r]\)? (stress-tests: single-element exclusion) Prefix-suffix still works: prefix[l] * suffix[r+1]. This is the range-product variant.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Product of Array Except Self generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Trionic Array I (3637)

   This just does a single pass of 3 monotonic regions and ensures other things such as the length of the segments are appropriate. The solution presented below just does a direct sweep for things instead of actually using prefix/suffix sums.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

   class Solution: def isTrionic(self, nums: List[int]) -> bool: """ 3 partitions, they are strictly increasing, strictly decreasing, strictly increasing. consider the boundaries a, +, a, -/0,b, -,b, -, b, +/0, c, +, c boundaries can be 0 or n We also realise that we need to form 3 segments, we aren't looking for turning points necessarily, we are looking for 3 segments. m1 failed: if I just use triples """ n = len(nums) if n < 4: return False # can't form 2 segments with less than 4 elements # 1: find end of strictly increasing segment: p = 0 while p < n - 1 and nums[p] < nums[p + 1]: p += 1 # check if failure: if p == 0: return False # 2: find end of strictly decreasing: q = p while q < n - 1 and nums[q] > nums[q + 1]: q += 1 # for us to end, the final segment must have at least one element and q must have moved from p if q == p or q == n - 1: return False # 3: check final segment is strictly decreasing: i = q while i < n - 1 and nums[i] < nums[i + 1]: i += 1 # i should be n - 1 (reached the end) return i == n - 1

   Code Snippet 5: Trionic Array I (3637)
   Pattern Extraction

   Core Insight: Verify three strictly monotonic segments (inc, dec, inc) via greedy pointer advancement through each phase. Pattern Name: Multi-Phase Monotonicity Verification Canonical Section: Arrays & Hashing > Prefix Sums Recognition Signals:

   • Validate array shape (peak-valley-peak, bitonic, trionic)
   • Segments must be strictly monotonic
   • Linear scan with phase tracking

   Anti-Signals:

   • Need to FIND the best trionic subarray (optimisation) – that’s LC 3640
   • Non-strict monotonicity – need \(\leq\) instead of \(<\)

   Decision Point: Validation = sweep verifying each phase. Optimisation = precompute segment properties and search.

   Pitfalls and Misconceptions

   1. Trap: Using turning-point detection instead of segment-based scanning. Why: Turning points are ambiguous with plateaus. Three while loops advancing while monotonic is clearer. Correction: Sequentially consume each segment with its own loop.

      1. Trap: Forgetting minimum segment lengths.

      Why: Each segment needs at least 2 elements. With \(n < 4\), two proper segments can’t form. Correction: Early return False if \(n < 4\).

   Problem Mutations

   1. What if you needed the longest trionic subarray? (stress-tests: boolean vs optimisation) Precompute increasing-run lengths from left and right. Similar structure but more bookkeeping.

      1. What if the pattern were bitonic (inc then dec only)? (stress-tests: three segments)

      Simpler: one peak, two segments. Scan for the peak, verify monotonicity on each side.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Trionic Array I. Review against personal solving experience.
   

3. Trionic Array II (3640)

   This is a nifty use of prefix sums. I think this is one of the rare instances where most of the work is to determine what to precompute.

   We should think of it as a search for ALL the trionic subarrays, which we shall use precomputed prefix sums for. The rough idea is to look for 3 segments (formed by 2 turning points, one peak, one trough). We shall move a pointer representing the middle peak idx, then once we find it, we shall attempt to expand rightward to find the trough then we shall use the precomputed suffix array to get the best right hand side value.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

   class Solution: def maxSumTrionic(self, nums: List[int]) -> int: """ Scan for 3 segments: A: strictly increasing prefix, B: strictly decreasing middle, C: strictly increasing suffix. Precompute for every index: ​ - inc_sum_left: max sum of a strictly increasing subarray ending at each position (from the left) ​ - inc_sum_right: max sum of a strictly increasing subarray starting at each position (from the right) The main pass looks for peaks, then greedily extends the decreasing segment as much as possible. Then checks that after the decreasing segment, another increase exists -- if so, computes the sum by joining the 3 regions. """ n = len(nums) inc_sum_left = [0] * n # max sum of strictly increasing subarray ending at each i (left-to-right) inc_sum_right = [0] * n # max sum of strictly increasing subarray starting at each i (right-to-left) inc_sum_left[0] = nums[0] inc_sum_right[-1] = nums[-1] # Precompute left-to-right strictly increasing sums (for segment A) for i in range(1, n): if nums[i] > nums[i-1]: inc_sum_left[i] = max(inc_sum_left[i-1] + nums[i], nums[i]) else: inc_sum_left[i] = nums[i] # Precompute right-to-left strictly increasing sums (for segment C) for i in range(n-2, -1, -1): if nums[i] < nums[i+1]: inc_sum_right[i] = max(inc_sum_right[i+1] + nums[i], nums[i]) else: inc_sum_right[i] = nums[i] i = 0 ans = float("-inf") while i < n: # Looking for a peak: left increasing, peak, then decreasing middle if i+2 < n and nums[i] < nums[i+1] and nums[i+1] > nums[i+2]: curr_sum = 0 # curr_sum shall hold the sum of the decreasing segment. j = i+1 # Expand the strictly decreasing region (middle segment B) while j+1 < n and nums[j] > nums[j+1]: curr_sum += nums[j] j += 1 # If another increasing segment exists after the trough if j+1 < n and nums[j] < nums[j+1]: curr_sum += nums[j] trionic_subarray_sum = inc_sum_left[i] + curr_sum + inc_sum_right[j+1] ans = max(ans, trionic_subarray_sum) i += 1 return ans

   Code Snippet 6: Trionic Array II (3640)
   Pattern Extraction

   Core Insight: Precompute max increasing-subarray sums from left and right. Scan for peaks, greedily extend the decreasing middle, combine left + middle + right. Pattern Name: Prefix-Suffix Precomputation with Interior Scan Canonical Section: Arrays & Hashing > Prefix Sums Recognition Signals:

   • “Max sum subarray with a specific shape” (three-segment constraint)
   • The shape has two outer segments and one interior
   • Precomputed partial answers for outer segments

   Anti-Signals:

   • Simple max subarray (no shape constraint) – Kadane
   • Bitonic (two segments) – simpler two-sided precomputation

   Decision Point: Three-segment structure = precompute both left and right partial answers, interior scan to connect them.

   Pitfalls and Misconceptions

   1. Trap: Not resetting the increasing-sum accumulator when the property breaks. Why: inc_sum_left[i] should be the max sum ending at \(i\), not total. When sequence stops increasing, restart from nums[i]. Correction: if nums[i] > nums[i-1]: inc_sum_left[i] = inc_sum_left[i-1] + nums[i] else: inc_sum_left[i] = nums[i].
   2. Trap: Missing the check that a valid right-increasing segment exists after the trough. Why: Without verifying nums[j] < nums[j+1] after the decreasing segment, you combine with a non-existent right segment. Correction: After the decreasing extension, check adjacency before using inc_sum_right[j+1].
   Problem Mutations

   1. What if values could be negative? (stress-tests: positive assumption) Algorithm works unchanged. Negative values reduce sums but max comparison handles this.
   2. What if the pattern had four segments? (stress-tests: three segments) More precomputation arrays and a more complex interior scan. Generalises but combinatorially harder.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Trionic Array II. Review against personal solving experience.
   

4. Maximum Number of Subsequences After One Inserting (3628)

   We are asked for max number of subsequences wherein the elements don’t have to be contiguous but need to preserve relative rank order. This is what asks us to try doing a prefix / suffix counting approach.

   We keep prefix and suffix partial subsequences COUNTS for every index and then think how to use the insertion. For the insertion, we can insert L, C or T. For L and T there’s a single best case (add to leftmost and rightmost respectively) for C, there’s a need to comb through.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

   class Solution: def numOfSubsequences(self, s: str) -> int: """ For this, the first thought that comes to mind is to consider prefix counts of partial subsequences. So for each i, we should try count all ​ - # of "L"s until that point ​ - # of "LC"s until that point ​ - # of "LCT"s until that point These partial counts will be useful for us to get the final values without insertion. Now we consider the insertion. The question is probably, which partial sum is the highest jump so that we can add it there? Not too sure how to factor in the "at most one insertion" part. For the insertions, what we insert matters for the cases: 1. L: should only be inserted at the start since it's the first (for max benefit) 2. C: should be inserted at any points midway to do the L_T properly 3. T: should only be inserted at the end (mirrors argument for case 1) We take the max gain from these 3 choices """ n = len(s) # precompute prefix counts for L and LC subsequences preL = [0] * (n + 1) preLC = [0] * (n + 1) for i in range(n): preL[i + 1] = preL[i] + (1 if s[i] == 'L' else 0) preLC[i + 1] = preLC[i] + (preL[i] if s[i] == 'C' else 0) # precompute suffix counts for C, CT pairs, and T (the C and T help us form intermediates to get CT) sufC = [0] * (n + 1) sufCT = [0] * (n + 1) sufT = [0] * (n + 1) for i in reversed(range(n)): sufC[i] = sufC[i + 1] sufCT[i] = sufCT[i + 1] sufT[i] = sufT[i + 1] if s[i] == 'T': sufT[i] += 1 elif s[i] == 'C': sufC[i] += 1 sufCT[i] += sufT[i] # count initial number of "LCT" subsequences countL = countLC = countLCT = 0 for c in s: match c: case 'L': countL += 1 case 'C': countLC += countL case 'T': countLCT += countLC res = countLCT # insert L at start: adds all "CT" pairs res = max(res, countLCT + sufCT[0]) # insert T at end: adds all "LC" pairs res = max(res, countLCT + preLC[n]) # insert C at every position: max over L before * T after for i in range(n + 1): res = max(res, countLCT + preL[i] * sufT[i]) return res

   Code Snippet 7: Maximum Number of Subsequences After One Inserting (3628)
   Pattern Extraction

   Core Insight: Precompute prefix counts of partial subsequences (L, LC, LCT). Insertion of L is best at start, T at end, C sweeps all positions. Take max gain. Pattern Name: Prefix Partial-Subsequence Counting with Optimal Insertion Canonical Section: Arrays & Hashing > Prefix Sums Recognition Signals:

   • “Maximise subsequence count by inserting one element”
   • Partial subsequences tracked via prefix/suffix counting
   • Insertion at different positions has different impacts

   Anti-Signals:

   • No insertion allowed – just count directly
   • Multiple insertions – DP over insertion set

   Decision Point: Single insertion optimisation = precompute counting layer, then evaluate each insertion position. Only C needs a sweep; L and T have single optimal positions.

   Pitfalls and Misconceptions

   1. Trap: Trying all \(O(n)\) positions for L and T insertions. Why: L is always best at start (maximises CT pairs to its right), T always best at end (maximises LC pairs to its left). Only C needs a sweep. Correction: Insert L at start, T at end. Only sweep C positions.
   2. Trap: Forgetting to count the base subsequences before computing gains. Why: Answer = base count + best gain, not just the gain. Correction: Compute countLCT first, then add max gain.
   Problem Mutations

   1. What if you could insert up to \(k\) characters? (stress-tests: single insertion) Each additional character has diminishing returns. Need to evaluate marginal gain per insertion.
   2. What if the pattern were longer (e.g., “LMCT”)? (stress-tests: pattern length) More prefix arrays for each partial subsequence. Insertion evaluation grows in complexity.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Maximum Number of Subsequences After One Inserting. Review against personal solving experience.
   

Difference Array for Range Updates (analogous to prefix sums) #

When you need to apply MANY range operations [start, end] efficiently, we need to consider some lazy approaches so that we defer the computation to as late as possible.

So it’s when we need to do range updates but without iterating on each and every one of them individually then we can use a difference array and gather the cumulative effect as we go along.

• SLOW: \(O(m·n)\) — apply each operation immediately or even if we flatten multiple updates

    for each shift [start, end, direction]:
        for each position i in [start, end]:
            modify(i)  # ← This is expensive with many shifts

  Code Snippet 8: Difference Array for Range Updates (analogous to prefix sums)

• FAST: \(O(m + n)\) — record boundaries, compute cumulative effect once

  Boilerplate for the prefix sum approach would look something like this:

    for each shift [start, end, direction]:
        diff[start] += change
        diff[end + 1] -= change
  
    cumulative = 0
    for each position i:
        cumulative += diff[i]
        final_value[i] = initial_value[i] + cumulative

  Code Snippet 9: Difference Array for Range Updates (analogous to prefix sums)

• Key insight: do an “events based” thinking, try to make it such that instead of marking all the changes, you mark ranges of changes – then apply cumulatively

  • The cumulative sum of the difference array tells you the total effect of ALL operations affecting each position.
  • Instead of modifying elements immediately:
    1. Record where each shift starts and stops (\(O(1)\) per shift)
    2. Compute cumulative effect at each position (\(O(n)\) once)
    3. Apply the cumulative effect to each character (\(O(n)\))

• Pattern recognition

  • Use a difference array when:

    1. You have range updates (modify all elements in [start, end])
    2. You have many shifts/updates relative to array size
    3. You only need the final state, not intermediate states
    4. You can afford to compute the cumulative effect at the end

  • Typically seen in:

    1. Range increment operations
    2. Scheduling/time-based problems
    3. Difference calculation problems
    4. Lazy propagation problems

Problems #

1. 2381. Shifting Letters II

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: """ ​ - shifting is an operation to be applied to a subarray. ​ - it's likely a good idea to flatten all the changes so that we know the lexical edit diffs to make per element ​ - inputs suggest that it's linear time, we can't do m * n ​ - the key idea is to not apply changes to individual elements, but to keep a difference array """ base = ord('a') ords = [ord(c) - base for c in s] # 1: mark the range-changes -- the shift boundaries (O(m)) diffs = [0] * (len(s) + 1) # 1 more so that we can mark the end of the segment as n + 1 th for start, end, direction in shifts: change = 1 if direction == 1 else -1 diffs[start] += change # shift starts here diffs[end + 1] -= change # shift ends here # 2: use cumulative changes to get the actual diffs cumulative = 0 for idx in range(len(s)): cumulative += diffs[idx] # changes on cumulative final_ord = base + ((ords[idx] + cumulative) % 26) ords[idx] = final_ord return "".join(chr(o) for o in ords)

   Code Snippet 10: 2381. Shifting Letters II

   • The prefix sum insight here is counterintuitive because:

     Your natural instinct is to “apply changes immediately” But for range operations, it’s faster to “record events” and “calculate cumulative effect” This requires thinking about the problem differently:

     Not: “How do I modify each element?” But: “Where do effects start and stop?”

   Pattern Extraction

   Core Insight: When you have many range updates to apply, mark where each effect starts and stops (boundary events), then sweep once to compute the cumulative effect at each position. Pattern Name: Difference Array for Range Updates Canonical Section: Arrays & Hashing > Difference Array Recognition Signals:

   • Multiple range updates [start, end, delta] applied to an array
   • Only the final state matters, not intermediate states
   • Updates are additive (increments/decrements that compose linearly)
   • Constraint: \(m\) updates on an array of size \(n\) where \(O(mn)\) is too slow

   Anti-Signals:

   • Need intermediate states after each update — must apply updates eagerly or use a persistent structure
   • Updates are multiplicative or non-linear — difference array only works for additive effects
   • Updates are point updates (single index) — no need for the range trick, just update directly
   • Need to query arbitrary ranges after updates — use a segment tree or BIT instead

   Decision Point: “Many range updates, query the final state” is the canonical trigger. If you see \(m\) range modifications and need the final array, difference array is \(O(m + n)\) vs \(O(mn)\) naive.

   Pitfalls and Misconceptions

   1. Trap: Applying each range update by iterating through the range.

   Why: \(O(mn)\) where \(m\) is number of updates and \(n\) is array length. TLEs on large inputs. Correction: Use difference array: diff[start] + delta=, diff[end+1] - delta=, then prefix sum.

   1. Trap: Marking diff[end] instead of diff[end + 1].

   Why: The decrement must go one past the end of the range. Marking diff[end] excludes the last element from the update. Correction: Always use diff[end + 1] - delta=. Allocate diff with size \(n + 1\) to avoid bounds checking.

   1. Trap: Forgetting the modular arithmetic for circular character shifts.

   Why: Cumulative shifts can be negative or exceed 26. Without % 26, character computation produces wrong results. Correction: Apply ((ord(c) - ord('a') + cumulative) % 26) with Python’s modulo handling negatives correctly.

   Problem Mutations

   1. What if updates were multiplicative instead of additive? (stress-tests: linearity assumption)

   Difference array doesn’t work for multiplication. Would need a segment tree with lazy propagation. Connects to LC 715 Range Module.

   1. What if you needed the state after each update, not just the final state? (stress-tests: batch-only assumption)

   Must apply updates online. A BIT (Fenwick tree) supports \(O(\log n)\) range updates and point queries. Connects to the Fenwick tree family.

   1. What if the array were 2D and updates were rectangular regions? (stress-tests: dimensionality)

   Use a 2D difference array: mark four corners of each rectangle. \(O(1)\) per update, \(O(mn)\) final sweep. Connects to LC 2132 Stamping the Grid.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Shifting Letters II generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Sequences #

Problems #

1. Longest Consecutive Sequence (128): it’s more about the elements forming an consecutive sequence

   this is more about finding out whether we have a “noop ladder” like in ROP hacking. Solution: create a set of nums (\(O(n)\)), then for each num, check if it’s the starting num (( n - 1 ) not in num_set) then just keep climbing up that ladder until no more, keep track of max length. Remember, only try to build sequences from the start of a sequence.

   This is such a simple way of looking at the problem, our first reach should NOT be some kind of interval merging or something. The input variables already hint that it’s a linear sweep of some sort.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) longest = 0 for n in num_set: # if this n is the start of the "noop ladder": if n - 1 not in num_set: length = 1 # build sequences from a new start: while n + length in num_set: length += 1 longest = max(longest, length) return longest

   Code Snippet 11: Longest Consecutive Sequence (128)
   Pattern Extraction

   Core Insight: Build a set for \(O(1)\) lookups, then only start counting from sequence heads (elements where n-1 is NOT in the set) — this ensures each element is visited at most twice across all sequences. Pattern Name: Sequence Head Detection with Hash Set Canonical Section: Arrays & Hashing > Sequences Recognition Signals:

   • “Longest consecutive sequence” in unsorted data
   • \(O(n)\) time required (rules out sorting)
   • Elements are integers (consecutive = differ by 1)
   • No need to preserve original order

   Anti-Signals:

   • Array is already sorted — just scan linearly with a counter, no hash set needed
   • Need the actual sequence elements, not just length — hash set approach still works but needs backtracking
   • “Longest increasing subsequence” (NOT consecutive) — completely different problem (LIS, patience sort)

   Decision Point: “Consecutive” means values differ by exactly 1. “Increasing” means relative order matters. Consecutive + unsorted = hash set; increasing = DP/patience sort. This is the most common conflation.

   Pitfalls and Misconceptions

   1. Trap: Sorting the array first and scanning linearly. Why: Sorting is \(O(n \log n)\), which violates the \(O(n)\) requirement. The solution works but doesn’t meet the constraint. Correction: Use a hash set for \(O(1)\) lookups and only start from sequence heads.
   2. Trap: Starting a sequence count from every element, not just sequence heads. Why: Without the n-1 not in set guard, you re-traverse overlapping sequences, producing \(O(n^2)\) worst case. Correction: Only start counting when n - 1 is not in the set — this element is a sequence head.
   3. Trap: Reaching for union-find or interval merging. Why: Both work but are over-engineered for this problem. Union-find adds \(O(\alpha(n))\) overhead and more code; interval merging requires sorting. Correction: The hash set approach is simpler, faster, and directly exploits the “consecutive” property.
   Problem Mutations

   1. What if elements could be floating point? (stress-tests: integer assumption) “Consecutive” is undefined for floats. The problem fundamentally requires discrete values.
   2. What if elements arrived in a stream and you needed the current longest consecutive at any point? (stress-tests: offline assumption) Hash set approach is already online for insertions, but finding the longest after each insertion requires augmenting the set with interval tracking. Connects to interval union data structures.
   3. What if you needed all maximal consecutive sequences, not just the longest? (stress-tests: single-answer assumption) Same algorithm; collect all sequences starting from heads instead of tracking only the max length.
   4. What if the array could have duplicates? (stress-tests: uniqueness) Converting to a set handles duplicates implicitly. No code change needed.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Longest Consecutive Sequence generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

NO Dynamic Range Querying using Fenwick Trees (Binary Index Trees) #

• CLOSING NOTE [2025-12-29 Mon 11:10]
  I stopped prepping for it, I’ll just skip this task until I need to come back to interview prep again
• this kind of problems deal with needing to do prefix sums and also updating them efficiently. They are also extremely niche and a bunch of hard questions in the more recent leetcode questions only accept such solutions. Typically, we can still achieve partial solutions using DP approaches, but will likely timeout unless fenwick trees are used.

Problems #

1. Number of Integers with Popcount-Depth Equal to K II (3624)

   The key idea here is that we need to accumulate interval counts of the popcount depths for depths in range [0, 5], so we have 6 different fenwick trees to track this. Querying comes in 2 forms: range queries and update queries and both can be handled in \(O(log n)\) time thanks to the use of fenwick trees.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

   from typing import List from functools import cache class FenwickTree: def __init__(self, n): self.n = n self.fw = [0]*(n+1) def update(self, i, delta): i += 1 while i <= self.n: self.fw[i] += delta i += i & (-i) def query(self, i): i += 1 s = 0 while i > 0: s += self.fw[i] i -= i & (-i) return s def range_query(self, l, r): return self.query(r) - (self.query(l-1) if l > 0 else 0) class Solution: def popcountDepth(self, nums: List[int], queries: List[List[int]]) -> List[int]: @cache def get_depth(x): depth = 0 while x != 1: x = x.bit_count() depth += 1 return depth n = len(nums) max_depth = 5 depths = [get_depth(x) for x in nums] # stores the current depths of each num, idxed by the nums idx # we build a fenwick tree, each tree will contain the prefix sum for the number of nums with depth = k (fixed) within fenwicks = [FenwickTree(n) for _ in range(max_depth+1)] # Initialize Fenwicks for i, d in enumerate(depths): fenwicks[d].update(i, 1) ans = [] for query in queries: match query: case 1, l, r, k: num_indices = fenwicks[k].range_query(l, r) ans.append(num_indices) case 2, idx, val: old_depth, new_depth = depths[idx], get_depth(val) if old_depth == new_depth: continue fenwicks[old_depth].update(idx, -1) fenwicks[new_depth].update(idx, 1) depths[idx] = new_depth return ans

   Code Snippet 12: Number of Integers with Popcount-Depth Equal to K II (3624)
   Pattern Extraction

   Core Insight: Use Fenwick trees (one per depth level 0-5) for range querying and point updating of popcount-depth counts. Pattern Name: Multiple Fenwick Trees for Dynamic Range Queries Canonical Section: Arrays & Hashing > Fenwick Trees / Dynamic Range Querying Recognition Signals:

   • Range queries AND point updates on the same array
   • Multiple independent “dimensions” to track (depth levels)
   • \(O(\log n)\) per query/update required

   Anti-Signals:

   • Static array, no updates – prefix sums suffice
   • Only point queries, no range queries – simple array

   Decision Point: Updates + range queries = Fenwick tree. Static + range queries = prefix sums. The update requirement is what forces the Fenwick structure.

   Pitfalls and Misconceptions

   1. Trap: Using prefix sums and rebuilding them on each update (\(O(n)\) per update). Why: With \(q\) queries, this is \(O(qn)\). Fenwick tree gives \(O(q \log n)\). Correction: Use Fenwick trees for \(O(\log n)\) update and query.
   2. Trap: Off-by-one in Fenwick tree indexing (0-based vs 1-based). Why: Fenwick trees are 1-indexed. Using 0-based indices breaks the bit manipulation. Correction: Always add 1 to convert: i + 1= before tree operations.
   Problem Mutations

   1. What if the depth function changed (not popcount depth)? (stress-tests: specific function) Same Fenwick structure, different depth computation. The data structure is independent of the function.
   2. What if updates could change values AND insert/delete elements? (stress-tests: fixed array size) Fenwick trees don’t support insertion/deletion. Need a balanced BST or order-statistic tree.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Number of Integers with Popcount-Depth Equal to K II. Review against personal solving experience.
   

2. Sum of Beautiful Subsequences (3671)

   To be honest, I don’t understand this. The DP version will pass 80% of the test cases, I most likely will end up resorting to that. The fenwick tree solutions, I don’t even have an intuition for it.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

   # M1: Fenwick Tree solution (correct, passes all) class Fenwick: def __init__(self, n): self.arr = [0] * (n + 1) def sum(self, i): s = 0 while i > 0: s += self.arr[i] i -= i & (-i) return s def add(self, i, x): while i < len(self.arr): self.arr[i] += x i += i & (-i) class Solution: def totalBeauty(self, nums: List[int]) -> int: MOD = 10**9 + 7 max_val = max(nums) + 1 locs = defaultdict(list) for idx, val in enumerate(nums): locs[val].append(idx) F = [0] * max_val for d in range(1, max_val): # indices of all numbers divisible by d indices = sorted(pos for val in range(d, max_val, d) for pos in locs[val]) if len(indices) <= 1: F[d] = len(indices) continue rank = {pos: r for r, pos in enumerate(indices, 1)} # rank compress fenw = Fenwick(len(indices)) for val in range(d, max_val, d): for pos in reversed(locs[val]): r = rank[pos] new_subseq_count = 1 + fenw.sum(r - 1) F[d] += new_subseq_count fenw.add(r, new_subseq_count) for d in range(max_val - 1, 0, -1): for multiple in range(d * 2, max_val, d): F[d] -= F[multiple] F[d] %= MOD return sum((d * F[d]) % MOD for d in range(1, max_val)) % MOD # M2::PARTIAL: dp solution: from math import gcd from collections import defaultdict class Solution: def totalBeauty(self, nums: List[int]) -> int: """ I think this is a multi step question as well First we just find all the subsequences (and the GCDs within them) Then we combine via the GCD values and get the beauty scores == steps {problem decomposition} ==> naive 1. enum strictly increasing subsequences in the array 2. for each subsequence, find its gcd 3. for each GCD, g, count subsequences with gcd = g 4. calculate == key intuition for optimisation: 1. directly enumerating is costly 2^n, so we have to build up the results. 2. so we use dp 2D where dp[i][g] is the number of strictly increasing subsequences ending at idx i with gcd g """ MOD = (10 ** 9) + 7 n = len(nums) total_beauty = 0 dp = [defaultdict(int) for _ in range(n)] # so dp[i][g] gives number of strictly increasing subsequences ending at index i with gcd g. for i in range(n): dp[i][nums[i]] = 1 # init value, it's gcd 1 for itself for j in range(i): # left pointer if nums[j] < nums[i]: # then can accumulate more GCDs for g, count in dp[j].items(): new_g = gcd(g, nums[i]) new_count = dp[i][new_g] + count dp[i][new_g] = new_count % MOD # now we calculate beauty values: for g, count in dp[i].items(): total_beauty = (total_beauty + (g * count)) % MOD return total_beauty

   Code Snippet 13: Sum of Beautiful Subsequences (3671)
   Pattern Extraction

   Core Insight: Use Fenwick trees with Mobius-function-style inclusion-exclusion on GCD values to count strictly increasing subsequences with exact GCD beauty values. Pattern Name: Fenwick Tree + Mobius Inversion for Subsequence Counting Canonical Section: Arrays & Hashing > Fenwick Trees Recognition Signals:

   • Count subsequences with a divisibility constraint on GCD
   • Need to separate “GCD exactly \(d\)” from “GCD divisible by \(d\)” using inclusion-exclusion
   • Fenwick tree for order-based counting

   Anti-Signals:

   • Simple subsequence counting without GCD constraint – standard DP
   • Small input – brute force DP is acceptable (the \(O(n^2)\) DP passes 80%)

   Decision Point: The Fenwick tree approach is needed for full AC. The DP approach (\(O(n^2)\) with GCD tracking) passes partially. Recognise that this is a number-theory problem disguised as a subsequence problem.

   Pitfalls and Misconceptions

   1. Trap: Trying to solve purely with DP (no Fenwick tree). Why: The DP approach is \(O(n^2)\) with large constant factors from GCD tracking. TLEs on the hardest test cases. Correction: Fenwick tree with rank compression for the full solution.
   2. Trap: Not applying Mobius inversion to separate “GCD exactly \(d\)” from “GCD divisible by \(d\)”. Why: Counting subsequences where all elements are divisible by \(d\) overcounts: some have GCD \(2d\), \(3d\), etc. Correction: Compute F[d] (divisible by \(d\)) for all \(d\), then subtract multiples: F[d] - F[2d] + F[3d] + …=.
   Problem Mutations

   1. What if the subsequence didn’t need to be strictly increasing? (stress-tests: ordering constraint) Different counting approach. The Fenwick tree order-based counting doesn’t apply. Use standard DP.
   2. What if you only needed the count modulo \(10^9 + 7\) without the beauty weighting? (stress-tests: weighted sum) Simpler: just count subsequences per GCD. Drop the \(d \cdot F[d]\) multiplication.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Sum of Beautiful Subsequences. Review against personal solving experience.
   

N-Sum Family #

Problems #

• N-Sum Family
  • 2-sum is about complement finding, pairwise just keep a seen index and use that when searching for complements further down

TODO Sudoku Family #

• Sudoku Family
  • n-dimensional array access is the main learning point here. When we access blocks, then for each cell, we can get which block they’re from using block_idx = row_idx // 3, col_idx // 3.

TODO Stock Family #

SOE #

General #

• Forgetting negatives / zeros in prefix sums \(\implies\) this affects the order of filling / presences of duplicate prefix sums in my list of prefix sums

Jumping the Gun to stdlib thoughts #

• Off-by-one in subarray loops
• Jumping straight to “pythonic” stdlib uses is NOT good. Just think about the minimal implementation then on the second look at it, think of stdlib uses. Need to avoid cases where we interpret the question wrongly. E.g. for “Top K Frequent Elements (347)”, there should be no reason to use a heapq, we can just directly sort based on counted values.

Disambiguating Sliding window vs prefix/suffix accumulation #

• Sliding window vs prefix/suffix accumulation is a common pitfall
  • If the problem wants you to process variable subarrays, or is about max-min over all partitions (not just windows that move by 1), sliding window is probably not a fit.

Prefix Sum Specific #

• Confusing prefix sum index semantics: prefix[i] represents sum of elements nums[0..i-1] (exclusive end), not nums[0..i]. Off-by-one when converting between prefix index and array index.
• Forgetting that prefix sum of an empty prefix is 0, which must be initialised (e.g., prefix[0] = 0 or seeding a hashmap with {0: -1} or {0: 1}).
• For “subarray sum equals K” pattern: forgetting to seed the hashmap with the empty-prefix sum before starting the loop.

Difference Array Specific #

• Marking diff[end] instead of diff[end + 1]: the decrement goes one past the end of the range.
• Forgetting the cumulative sweep after marking boundaries – the difference array is useless without the final prefix-sum pass.

Decision Flow #

• Is it lookup/search? → HashMap

• Is it range sum? → Prefix sums

• Do we care about some properties of subsequences (where the contiguity not important BUT the relative order matters) -> consider using prefix/suffix counting, which may be a state-tracking kind of counting as well.

• Is the problem about a ‘window’ (i.e. strict subarray of size K / variable) or is it accumulating something from start / end

  • if window: most likely Sliding window
  • if accumulation / arbitrary splits then it’s most likely: Prefix/Suffix tracking

• Char counting / Freq counting \(\rightarrow\) use fixed array counter if is fixed space else use collections.Counter

Styles, Tricks and Boilerplate #

1. Better to early return instead of more code-golf like solutions
2. love the use of defaultdict, careful on the choice of keys (must be hashable)
3. use genexps for intermediate lists where possible

Boilerplate #

Prefix Sum Array Construction #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def build_prefix_sum(nums):
    """prefix[i] = sum of nums[0..i-1]; prefix[0] = 0 (empty prefix)"""
    prefix = [0] * (len(nums) + 1)
    for i, num in enumerate(nums):
        prefix[i + 1] = prefix[i] + num
    return prefix

def range_sum(prefix, left, right):
    """Sum of nums[left..right] inclusive"""
    return prefix[right + 1] - prefix[left]

Difference Array for Range Updates #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def apply_range_updates(n, updates):
    """
    updates: list of (start, end, delta)
    Returns final array after all range updates applied.
    """
    diff = [0] * (n + 1)
    for start, end, delta in updates:
        diff[start] += delta
        diff[end + 1] -= delta

    # cumulative sweep
    result = [0] * n
    cumulative = 0
    for i in range(n):
        cumulative += diff[i]
        result[i] = cumulative
    return result

Subarray Sum Equals K (Prefix Sum + Hashmap) #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import defaultdict

def subarray_sum_count(nums, k):
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1  # empty prefix

    for num in nums:
        prefix += num
        count += seen[prefix - k]
        seen[prefix] += 1

    return count

TODO KIV #