Algorithm Code
Time: O(n) build, O(1) query | Space: O(n)
1// Basic Prefix Sum Construction
2function buildPrefixSum(arr) {
3 prefixSum = [0] // Start with 0 for easier calculations
4
5 for (let i = 0; i < arr.length; i++) {
6 prefixSum[i + 1] = prefixSum[i] + arr[i]
7 }
8
9 return prefixSum
10}
11
12// Range Sum Query using Prefix Sum
13function rangeSum(prefixSum, left, right) {
14 // Sum from left to right (inclusive)
15 return prefixSum[right + 1] - prefixSum[left]
16}
17
18// Advanced: 2D Prefix Sum
19function build2DPrefixSum(matrix) {
20 rows = matrix.length
21 cols = matrix[0].length
22 prefix2D = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0))
23
24 for (let i = 1; i <= rows; i++) {
25 for (let j = 1; j <= cols; j++) {
26 prefix2D[i][j] = matrix[i-1][j-1] +
27 prefix2D[i-1][j] +
28 prefix2D[i][j-1] -
29 prefix2D[i-1][j-1]
30 }
31 }
32
33 return prefix2D
34}
35
36// Subarray Sum Equals K
37function subarraySum(nums, k) {
38 count = 0
39 prefixSum = 0
40 sumFreq = {0: 1} // Handle sum = k from beginning
41
42 for (let num of nums) {
43 prefixSum += num
44
45 if (sumFreq[prefixSum - k]) {
46 count += sumFreq[prefixSum - k]
47 }
48
49 sumFreq[prefixSum] = (sumFreq[prefixSum] || 0) + 1
50 }
51
52 return count
53}Algorithm Steps
Step 1 of 12
1
Initialize prefix sum array with 0 at index 0
2
Add arr[0] = 3 to prefix[0] = 0 → 3
3
Add arr[1] = 1 to prefix[1] = 3 → 4
4
Add arr[2] = 4 to prefix[2] = 4 → 8
5
Add arr[3] = 1 to prefix[3] = 8 → 9
6
Add arr[4] = 5 to prefix[4] = 9 → 14
7
Add arr[5] = 9 to prefix[5] = 14 → 23
8
Add arr[6] = 2 to prefix[6] = 23 → 25
9
Range sum [1, 3] = prefix[4] - prefix[1] = 9 - 3 = 6
10
Range sum [0, 2] = prefix[3] - prefix[0] = 8 - 0 = 8
11
Range sum [2, 4] = prefix[5] - prefix[2] = 14 - 4 = 10
12
All possible subarray sums calculated using prefix sum in O(1) time each
Prefix Sum Visualizer
Phase: BUILD | Time Complexity: O(n) build, O(1) query | Space Complexity: O(n)
Original Array:
3
1
4
1
5
9
2
0
1
2
3
4
5
6
Prefix Sum Array:
0
0
Current Element
Current Prefix Sum
Query Range
Query Bounds
Step 0 of 110%
0.25x4x