69:T54f,/** * A complete, production-ready prefix sum implementation * with proper validation and error handling. */ class PrefixSumArray { private prefix: number[]; private n: number; constructor(arr: number[]) { this.n = arr.length; this.prefix = new Array(this.n + 1).fill(0); for (let i = 0; i < this.n; i++) { this.prefix[i + 1] = this.prefix[i] + arr[i]; } } /** * Query the sum of elements in range [left, right] inclusive. * @throws Error if indices are out of bounds or invalid */ rangeSum(left: number, right: number): number { // Validate indices if (left < 0 || right >= this.n) { throw new Error(`Index out of bounds: [0, ${this.n - 1}]`); } if (left > right) { throw new Error(`Invalid range: left (${left}) > right (${right})`); } return this.prefix[right + 1] - this.prefix[left]; } /** * Get the total sum of all elements. */ totalSum(): number { return this.prefix[this.n]; } /** * Get the sum of the first k elements. */ sumFirst(k: number): number { if (k < 0 || k > this.n) { throw new Error(`k must be in range [0, ${this.n}]`); } return this.prefix[k]; } }6a:T68e,/** * Difference Array for efficient range updates. * * The difference array D encodes the "jumps" between consecutive elements. * A range update becomes two point operations. * The final array is recovered by computing prefix sums of D. */ class DifferenceArray { private diff: number[]; private n: number; constructor(arr: number[]) { this.n = arr.length; this.diff = new Array(this.n + 1).fill(0); // Build difference array this.diff[0] = arr[0]; for (let i = 1; i < this.n; i++) { this.diff[i] = arr[i] - arr[i - 1]; } } /** * Add value to all elements in range [left, right] inclusive. * Time: O(1) */ rangeUpdate(left: number, right: number, value: number): void { this.diff[left] += value; if (right + 1 < this.n) { this.diff[right + 1] -= value; } } /** * Reconstruct the final array after all updates. * Time: O(n) — essentially computing prefix sums */ getResult(): number[] { const result = new Array(this.n); result[0] = this.diff[0]; for (let i = 1; i < this.n; i++) { result[i] = result[i - 1] + this.diff[i]; } return result; } } // Example: Apply multiple range updates const initial = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; const da = new DifferenceArray(initial); da.rangeUpdate(2, 5, 10); // Add 10 to indices 2-5 da.rangeUpdate(3, 8, 5); // Add 5 to indices 3-8 da.rangeUpdate(0, 4, -3); // Subtract 3 from indices 0-4 console.log(da.getResult()); // [-3, -3, 7, 12, 12, 15, 5, 5, 5, 0]6b:T741,/** * 2D Prefix Sum (Summed Area Table) for O(1) rectangular region sum queries. */ class PrefixSum2D { private prefix: number[][]; private rows: number; private cols: number; constructor(matrix: number[][]) { if (matrix.length === 0 || matrix[0].length === 0) { this.rows = 0; this.cols = 0; this.prefix = []; return; } this.rows = matrix.length; this.cols = matrix[0].length; // Create prefix sum matrix with sentinel row and column this.prefix = Array.from( { length: this.rows + 1 }, () => new Array(this.cols + 1).fill(0) ); // Build using inclusion-exclusion for (let i = 1; i <= this.rows; i++) { for (let j = 1; j <= this.cols; j++) { this.prefix[i][j] = matrix[i - 1][j - 1] + this.prefix[i - 1][j] + this.prefix[i][j - 1] - this.prefix[i - 1][j - 1]; } } } /** * Query sum of rectangular region from (r1,c1) to (r2,c2) inclusive. * Uses inclusion-exclusion to compute in O(1). */ regionSum(r1: number, c1: number, r2: number, c2: number): number { // Convert to 1-indexed prefix array coordinates r1++; c1++; r2++; c2++; return this.prefix[r2][c2] - this.prefix[r1 - 1][c2] - this.prefix[r2][c1 - 1] + this.prefix[r1 - 1][c1 - 1]; } } // Example const matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ]; const ps2d = new PrefixSum2D(matrix); // Sum of entire matrix console.log(ps2d.regionSum(0, 0, 2, 3)); // 78 // Sum of middle 2x2 region (rows 0-1, cols 1-2) console.log(ps2d.regionSum(0, 1, 1, 2)); // 2+3+6+7 = 1862:{"json":{"id":"seed_1cbc962406e975012429d2fd3be0f5ef","slug":"common-array-patterns","category":"Data Structures & Algorithms","topic":"Common Array Patterns & Problem Types","title":"Common Array Patterns & Problem Types","description":"Master the essential array patterns that form the backbone of algorithmic problem-solving. From prefix sums to in-place transformations, build a mental library of reusable techniques that apply across countless problems.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_315a026aee1495c0e6892a778e561ff8","title":"Prefix Sums and Cumulative Arrays","order":0,"content":[{"id":"prefix-sums-opening","title":"The Power of Precomputation","content":[{"data":{"content":"Imagine you're building a financial dashboard that must answer thousands of queries per second: *\"What was the total revenue between March 15th and June 22nd?\"* or *\"How much did we spend in Q3?\"* Each query asks for the sum of values within a range of your data.\n\nThe naive approach—iterating through the range and adding up values for each query—works fine for occasional questions. But at scale, with millions of data points and thousands of concurrent queries, this approach becomes a performance bottleneck that can bring your system to its knees.\n\nEnter **prefix sums**, one of the most elegant and universally applicable array patterns in computer science. This technique transforms O(n) range sum queries into O(1) operations through the strategic investment of upfront computation. It's a masterclass in the fundamental algorithmic principle of **trading preprocessing time for query efficiency**."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will deeply understand prefix sums: their mathematical foundation, construction algorithms, constant-time range queries, space-time tradeoffs, variations (difference arrays, 2D prefix sums), and practical applications from competitive programming to production systems.","variant":"info"},"type":"callout"}]},{"id":"range-query-problem","title":"The Problem: Repeated Range Queries","content":[{"data":{"content":"Let's formalize the problem that prefix sums solve. Given an array of n elements, we want to efficiently answer multiple queries of the form:\n\n**Range Sum Query:** *\"What is the sum of elements from index i to index j (inclusive)?\"*\n\nThis seemingly simple question appears constantly in real-world applications:"},"type":"text"},{"data":{"items":["**Financial analytics** — Total sales between two dates, cumulative P&L, running balances","**Time-series databases** — Aggregate sensor readings over intervals","**Image processing** — Summed area tables for fast region-based calculations","**Game development** — Damage calculations, score accumulation, area-of-effect computations","**Network analysis** — Bandwidth usage over time windows, packet counts","**Competitive programming** — Countless problems reduce to range sum queries"],"title":{"icon":"Database","text":"Range Query Applications","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**The Naive Approach and Its Limitations**\n\nThe straightforward solution iterates through the specified range and accumulates the sum:"},"type":"text"},{"data":{"code":"// Naive range sum: O(n) per query\nfunction rangeSum(arr: number[], left: number, right: number): number {\n let sum = 0;\n for (let i = left; i <= right; i++) {\n sum += arr[i];\n }\n return sum;\n}\n\n// Example usage\nconst data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];\n\n// Query: Sum from index 2 to 7 (inclusive)\nconst result = rangeSum(data, 2, 7);\nconsole.log(result); // 4 + 1 + 5 + 9 + 2 + 6 = 27","fileName":"naiveRangeSum.ts","language":"typescript"},"type":"code"},{"data":{"content":"**Complexity Analysis of the Naive Approach:**\n\n- **Time per query:** O(k), where k = right - left + 1\n- **Worst case:** O(n) when querying the entire array\n- **For Q queries:** O(Q × n) total time\n\nThis might seem acceptable, but consider the scale implications:"},"type":"text"},{"data":{"rows":[["1,000","1,000","1 million","1 millisecond"],["100,000","10,000","1 billion","1 second"],["1,000,000","100,000","100 billion","100 seconds"],["10,000,000","1,000,000","10 trillion","~3 hours"]],"caption":"Naive Range Sum Query Performance at Scale","headers":["Array Size (n)","Queries (Q)","Operations","At 1B ops/sec"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"The Scale Cliff","content":"What works in development fails in production. A million queries against a million-element array takes over an hour with the naive approach. Interactive systems become unresponsive. Batch jobs miss their windows. This is precisely where prefix sums shine.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"cumulative-sum-insight","title":"The Insight: Cumulative Sums and Telescoping","content":[{"data":{"content":"The breakthrough behind prefix sums comes from a simple mathematical observation. Consider what happens when we compute cumulative sums from the beginning of an array:\n\nFor an array **A = [a₀, a₁, a₂, a₃, ..., aₙ₋₁]**, we define the **prefix sum array** **P** where:\n\n- P[0] = 0 (empty sum, a sentinel value)\n- P[1] = a₀\n- P[2] = a₀ + a₁\n- P[3] = a₀ + a₁ + a₂\n- ...\n- P[k] = a₀ + a₁ + ... + aₖ₋₁ (sum of first k elements)\n\nThe key insight is this: **any contiguous range sum can be expressed as the difference of two prefix sums.**"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Telescoping Principle","content":"Sum(i to j) = P[j+1] - P[i]\n\nThis works because P[j+1] contains the sum from index 0 to j, and P[i] contains the sum from index 0 to i-1. Subtracting cancels all elements before index i, leaving exactly the sum from i to j.","variant":"tip"},"type":"callout"},{"data":{"content":"**Visual Proof:**\n\nLet's trace through this with a concrete example:\n\n```\nOriginal array A: [3, 1, 4, 1, 5, 9, 2, 6]\nIndices: 0 1 2 3 4 5 6 7\n\nPrefix sum array P: [0, 3, 4, 8, 9, 14, 23, 25, 31]\nIndices: 0 1 2 3 4 5 6 7 8\n```\n\n**Query: Sum from index 2 to 5 (inclusive)**\n\n- Direct calculation: A[2] + A[3] + A[4] + A[5] = 4 + 1 + 5 + 9 = 19\n- Using prefix sums: P[6] - P[2] = 23 - 4 = 19 ✓\n\n**Why does this work?**\n\n```\nP[6] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 3 + 1 + 4 + 1 + 5 + 9 = 23\nP[2] = A[0] + A[1] = 3 + 1 = 4\n\nP[6] - P[2] = (A[0] + A[1] + A[2] + A[3] + A[4] + A[5]) - (A[0] + A[1])\n = A[2] + A[3] + A[4] + A[5]\n = 19\n```\n\nThe subtraction **telescopes**, canceling all terms before our desired range. This is the elegant heart of the prefix sum technique."},"type":"text"},{"data":{"icon":"Info","title":"Zero-Indexed Prefix Array Convention","content":"We use P of size n+1 with P[0] = 0 as a sentinel. This handles edge cases elegantly: querying from index 0 just becomes P[right+1] - P[0] = P[right+1] - 0 = P[right+1]. No special-case logic needed.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"building-prefix-sums","title":"Building the Prefix Sum Array","content":[{"data":{"content":"Constructing the prefix sum array is a single O(n) pass. Each element is simply the sum of the previous prefix sum and the current original element. This recurrence relation makes the algorithm both simple and efficient:"},"type":"text"},{"data":{"code":"/**\n * Build a prefix sum array from the original array.\n * \n * Time Complexity: O(n) — single pass through the array\n * Space Complexity: O(n) — new array of size n+1\n * \n * @param arr The original array of numbers\n * @returns Prefix sum array where prefix[i] = sum of arr[0..i-1]\n */\nfunction buildPrefixSum(arr: number[]): number[] {\n const n = arr.length;\n const prefix = new Array(n + 1).fill(0);\n \n // prefix[0] = 0 (sentinel for empty range)\n for (let i = 0; i < n; i++) {\n prefix[i + 1] = prefix[i] + arr[i];\n }\n \n return prefix;\n}\n\n// Example\nconst data = [3, 1, 4, 1, 5, 9, 2, 6];\nconst prefixSums = buildPrefixSum(data);\n\nconsole.log(\"Original:\", data);\n// [3, 1, 4, 1, 5, 9, 2, 6]\n\nconsole.log(\"Prefix Sums:\", prefixSums);\n// [0, 3, 4, 8, 9, 14, 23, 25, 31]","fileName":"prefixSumConstruction.ts","language":"typescript"},"type":"code"},{"data":{"content":"**Understanding the Recurrence:**\n\nThe construction follows a simple recurrence relation:\n\n```\nP[0] = 0\nP[i] = P[i-1] + A[i-1] for i = 1, 2, ..., n\n```\n\nThis is equivalent to:\n\n```\nP[i] = Σ(k=0 to i-1) A[k]\n```\n\nEach prefix sum builds upon the previous one, adding exactly one new element. This incremental construction is key to the O(n) time complexity."},"type":"text"},{"data":{"icon":"Zap","title":"Memory Optimization: In-Place Prefix Sums","content":"If you don't need the original array afterward, you can compute prefix sums in-place, using no extra space. Simply overwrite each element with its running sum. However, this destroys the original data, so use this optimization only when appropriate.","variant":"tip"},"type":"callout"},{"data":{"code":"/**\n * In-place prefix sum transformation.\n * Modifies the array to contain cumulative sums.\n * \n * After transformation: arr[i] = sum of original arr[0..i]\n * \n * Time: O(n), Space: O(1) auxiliary\n */\nfunction prefixSumInPlace(arr: number[]): void {\n for (let i = 1; i < arr.length; i++) {\n arr[i] += arr[i - 1];\n }\n}\n\n// Example\nconst data = [3, 1, 4, 1, 5, 9, 2, 6];\nprefixSumInPlace(data);\nconsole.log(data);\n// [3, 4, 8, 9, 14, 23, 25, 31]\n\n// Note: Range query adjustment needed since no sentinel at index 0\n// Sum(i to j) = arr[j] - arr[i-1] (handle i=0 specially)","fileName":"inPlacePrefixSum.ts","language":"typescript"},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"range-queries-constant-time","title":"Answering Range Queries in O(1)","content":[{"data":{"content":"With the prefix sum array constructed, any range sum query becomes a simple subtraction—two array accesses and one arithmetic operation:"},"type":"text"},{"data":{"code":"/**\n * Answer a range sum query in O(1) time using prefix sums.\n * \n * @param prefix The precomputed prefix sum array (size n+1)\n * @param left Starting index of the range (inclusive)\n * @param right Ending index of the range (inclusive)\n * @returns Sum of elements from index left to right\n */\nfunction rangeSum(prefix: number[], left: number, right: number): number {\n return prefix[right + 1] - prefix[left];\n}\n\n// Complete example\nconst data = [3, 1, 4, 1, 5, 9, 2, 6];\nconst prefix = buildPrefixSum(data);\n\n// Various range queries — all O(1)\nconsole.log(rangeSum(prefix, 0, 7)); // Entire array: 31\nconsole.log(rangeSum(prefix, 2, 5)); // Indices 2-5: 19\nconsole.log(rangeSum(prefix, 0, 0)); // Single element: 3\nconsole.log(rangeSum(prefix, 4, 7)); // Indices 4-7: 22\nconsole.log(rangeSum(prefix, 3, 3)); // Single element: 1","fileName":"rangeSumQuery.ts","language":"typescript"},"type":"code"},{"data":{"content":"**Complexity Comparison:**"},"type":"text"},{"data":{"rows":[["Preprocessing Time","O(1) (none)","O(n)"],["Preprocessing Space","O(1)","O(n)"],["Query Time","O(n) worst case","O(1)"],["Total for Q Queries","O(Q × n)","O(n + Q)"],["Update Original Array","O(1)","O(n) to rebuild"]],"caption":"Naive vs Prefix Sum: Complexity Analysis","headers":["Metric","Naive Approach","Prefix Sum Approach"]},"type":"table"},{"data":{"icon":"TrendingUp","title":"The Crossover Point","content":"Prefix sums become advantageous when Q > 1 (more than one query). The break-even point is: O(n + Q) < O(Q × n), which simplifies to Q > n/(n-1) ≈ 1 for large n. In practice, even 2-3 queries justify the preprocessing for large arrays.","variant":"success"},"type":"callout"},{"data":{"content":"**Handling Edge Cases:**\n\nRobust prefix sum implementations must handle several edge cases:\n\n1. **Empty array:** Return empty prefix array or handle as error\n2. **Single element:** Works naturally (P = [0, a₀])\n3. **Full array query:** P[n] - P[0] = P[n]\n4. **Single element query (i=j):** P[i+1] - P[i] = A[i] ✓\n5. **Invalid indices:** Validate left ≤ right and bounds before querying"},"type":"text"},{"data":{"code":"$69","fileName":"robustPrefixSum.ts","language":"typescript"},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"space-time-tradeoff","title":"The Space-Time Tradeoff","content":[{"data":{"content":"Prefix sums exemplify a fundamental principle in algorithm design: **trading space for time** (or equivalently, trading preprocessing for query efficiency).\n\nThis tradeoff appears throughout computer science:\n\n- **Caching:** Store computed results to avoid recomputation\n- **Indexing:** Build lookup structures to accelerate searches\n- **Memoization:** Remember subproblem solutions in dynamic programming\n- **Precomputation tables:** Store factorials, powers, combinatorics\n\nPrefix sums represent perhaps the simplest and cleanest example of this tradeoff in action."},"type":"text"},{"data":{"left":[{"data":{"items":["**O(n) extra space** for the prefix array","**O(n) preprocessing time** upfront","**O(n) update cost** if source data changes","**Memory bandwidth** for cache misses on large arrays"],"title":{"icon":"DollarSign","text":"What We Pay (Costs)","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**O(1) query time** regardless of range size","**O(n + Q) total** for Q queries vs O(nQ)","**Simple implementation** with low constant factors","**Predictable performance** — no worst-case spikes"],"title":{"icon":"Zap","text":"What We Gain (Benefits)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**When Prefix Sums Excel:**\n\n1. **Query-heavy workloads:** Many queries on static or slowly-changing data\n2. **Interactive applications:** Real-time analytics, dashboards, games\n3. **Batch processing:** Answering thousands of range queries in one pass\n4. **Competitive programming:** Almost always beneficial when range sums appear\n\n**When to Reconsider:**\n\n1. **Frequent updates:** If the source array changes often, rebuilding the prefix array becomes expensive. Consider *segment trees* or *Fenwick trees* for O(log n) updates.\n2. **Single query:** For literally one query, preprocessing isn't worth it.\n3. **Memory-constrained environments:** When O(n) extra space is prohibitive.\n4. **Streaming data:** When you can't store the full array anyway."},"type":"text"},{"data":{"icon":"Info","title":"Dynamic Range Sum Structures","content":"When you need both efficient queries AND efficient updates, prefix sums alone aren't enough. Fenwick Trees (Binary Indexed Trees) offer O(log n) for both operations. Segment Trees offer the same complexity with more flexibility for non-associative operations. These are covered in later modules.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"difference-arrays","title":"Variation: Difference Arrays for Range Updates","content":[{"data":{"content":"Prefix sums have a powerful dual: the **difference array**. While prefix sums accelerate range *queries*, difference arrays accelerate range *updates*.\n\n**The Problem:**\n\nGiven an array, perform multiple operations of the form:\n- *\"Add value v to all elements from index i to j\"*\n\nThen, reconstruct the final array.\n\nWith the naive approach, each range update takes O(k) time where k is the range size. For Q updates: O(Q × n) total.\n\n**The Difference Array Solution:**\n\nFor array A, define difference array D where:\n- D[0] = A[0]\n- D[i] = A[i] - A[i-1] for i > 0\n\nThe key insight: **A range update [i, j] by value v becomes just two point updates in D:**\n- D[i] += v (starting the increment)\n- D[j+1] -= v (ending the increment)"},"type":"text"},{"data":{"code":"$6a","fileName":"differenceArray.ts","language":"typescript"},"type":"code"},{"data":{"icon":"Sparkles","title":"The Beautiful Duality","content":"Prefix sums and difference arrays are mathematical inverses. Computing prefix sums from a difference array recovers the original array. Computing differences from a prefix sum array recovers the original array. This duality is fundamental to understanding both techniques.","variant":"tip"},"type":"callout"},{"data":{"rows":[["Prefix Sum","Range Query O(1)","Point Update O(n)","Many queries, few updates"],["Difference Array","Range Update O(1)","Point Query O(n)","Many updates, few queries"]],"caption":"Prefix Sum vs Difference Array","headers":["Technique","Fast Operation","Slow Operation","Primary Use"]},"type":"table"}],"titleType":"number","titleNumber":6},{"id":"2d-prefix-sums","title":"Extension: 2D Prefix Sums (Summed Area Tables)","content":[{"data":{"content":"The prefix sum concept extends naturally to two dimensions, creating what are known as **2D prefix sums** or **summed area tables** (a term from image processing).\n\n**The Problem:**\n\nGiven a 2D matrix of values, answer queries of the form:\n- *\"What is the sum of all elements in the rectangular region from (r1, c1) to (r2, c2)?\"*\n\n**The 2D Prefix Sum Construction:**\n\nFor matrix M, build prefix sum matrix P where P[i][j] = sum of all elements in the rectangle from (0,0) to (i-1, j-1).\n\nThe construction uses the **inclusion-exclusion principle**:\n\n```\nP[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]\n```\n\n- Add the cell above\n- Add the cell to the left \n- Subtract the diagonal (counted twice)\n- Add the current matrix element"},"type":"text"},{"data":{"code":"$6b","fileName":"twoDPrefixSum.ts","language":"typescript"},"type":"code"},{"data":{"icon":"Image","title":"Image Processing Origins","content":"Summed area tables were introduced in computer graphics for fast texture mapping. They're used extensively in image processing for features like box blur, where you need to average pixels in a rectangular region. The Viola-Jones face detection algorithm famously uses integral images (another name for 2D prefix sums) to compute Haar-like features in constant time.","variant":"note"},"type":"callout"},{"data":{"content":"**Complexity Analysis:**\n\n- **Preprocessing:** O(m × n) time and space for an m × n matrix\n- **Query:** O(1) per rectangular region query\n- **Extension:** The technique generalizes to N dimensions with O(2^N) terms in the inclusion-exclusion formula, though practical use beyond 3D is rare."},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"classic-problems","title":"Classic Problems Using Prefix Sums","content":[{"data":{"content":"Prefix sums unlock efficient solutions to a wide variety of problems. Here are several classics that every serious programmer should know:"},"type":"text"},{"data":{"items":["**Problem:** Count how many contiguous subarrays have sum equal to k.","**Insight:** If prefixSum[j] - prefixSum[i] = k, then subarray [i, j-1] has sum k.","**Solution:** Use a hash map to count prefix sum occurrences. For each new prefix sum, check how many previous prefix sums equal (current - k).","**Complexity:** O(n) time, O(n) space."],"title":{"icon":"Code","text":"Problem 1: Count Subarrays with Given Sum","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"code":"/**\n * Count subarrays with sum equal to k.\n * Uses prefix sums + hash map for O(n) solution.\n */\nfunction subarraySum(nums: number[], k: number): number {\n const prefixCount = new Map();\n prefixCount.set(0, 1); // Empty prefix has sum 0\n \n let count = 0;\n let currentSum = 0;\n \n for (const num of nums) {\n currentSum += num;\n \n // How many previous prefix sums equal (currentSum - k)?\n const target = currentSum - k;\n if (prefixCount.has(target)) {\n count += prefixCount.get(target)!;\n }\n \n // Record this prefix sum\n prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);\n }\n \n return count;\n}\n\nconsole.log(subarraySum([1, 1, 1], 2)); // 2\nconsole.log(subarraySum([1, 2, 3], 3)); // 2","fileName":"subarraySum.ts","language":"typescript"},"type":"code"},{"data":{"items":["**Problem:** Count subarrays whose sum is divisible by k.","**Insight:** If prefixSum[j] ≡ prefixSum[i] (mod k), then subarray [i, j-1] has sum divisible by k.","**Solution:** Track counts of prefix sums modulo k. Same remainders indicate divisible subarrays.","**Complexity:** O(n) time, O(k) space."],"title":{"icon":"Code","text":"Problem 2: Subarray Divisibility","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Problem:** For each index i, compute the product of all elements except nums[i], without division.","**Insight:** Use prefix products (left to right) and suffix products (right to left).","**Solution:** result[i] = prefixProduct[i-1] × suffixProduct[i+1]. Two passes, O(1) extra space possible.","**Complexity:** O(n) time, O(1) auxiliary space (using output array for intermediate storage)."],"title":{"icon":"Code","text":"Problem 3: Product of Array Except Self","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Lightbulb","title":"Pattern Recognition","content":"When you see 'sum of contiguous elements' or 'range query' in a problem, prefix sums should immediately come to mind. The technique is so fundamental that recognizing its applicability becomes second nature with practice.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"prefix-sums-summary","title":"Summary: Prefix Sums as a Foundation","content":[{"data":{"content":"Prefix sums represent one of the most important array patterns in computer science—simple to implement, mathematically elegant, and universally applicable. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Prefix sums enable O(1) range sum queries** after O(n) preprocessing—a fundamental space-time tradeoff.","**The telescoping property** allows any range sum to be expressed as the difference of two prefix sums: Sum(i,j) = P[j+1] - P[i].","**Difference arrays are the dual:** They enable O(1) range updates where prefix sums enable O(1) range queries.","**The technique extends to 2D** (and beyond) using inclusion-exclusion, enabling constant-time rectangular region queries.","**Many problems reduce to prefix sums:** Subarray sums, divisibility, counting, and more—with clever use of hash maps for additional power.","**Know when prefix sums aren't enough:** For dynamic updates, Fenwick trees and segment trees offer logarithmic complexity for both queries and updates."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nWith prefix sums mastered, you have a powerful tool for aggregate computations. In the next page, we explore **Kadane's Algorithm**—an elegant technique for finding the maximum sum subarray that builds on the intuition developed here but takes a fundamentally different approach through dynamic programming."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Pattern Acquired","content":"Prefix sums are now part of your algorithmic toolkit. You'll find them appearing again and again—in competitive programming, system design, and production code. The technique is deceptively simple but remarkably powerful. Master it, and you'll solve entire categories of problems with ease.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_bf19d8342c0b6cad76cafe726518d556","title":"Kadane's Algorithm Intuition — Maximum Subarray","order":1,"content":null,"isLocked":true},{"id":"seed_48bbc1e153640e8466c5a625fc750e93","title":"Rotating and Reversing Arrays","order":2,"content":null,"isLocked":true},{"id":"seed_c761b6df6280b46483ccda4bcfc85336","title":"Merging Sorted Arrays","order":3,"content":null,"isLocked":true},{"id":"seed_d7d53ce8888bdd581301da7db29cb44c","title":"In-Place Transformations","order":4,"content":null,"isLocked":true}]}}