Common Array Patterns & Problem Types

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

// Naive range sum: O(n) per query
function rangeSum(arr: number[], left: number, right: number): number {
    let sum = 0;
    for (let i = left; i <= right; i++) {
        sum += arr[i];
    }
    return sum;
}
 
// Example usage
const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
 
// Query: Sum from index 2 to 7 (inclusive)
const result = rangeSum(data, 2, 7);
console.log(result); // 4 + 1 + 5 + 9 + 2 + 6 = 27

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

/**
 * Build a prefix sum array from the original array.
 * 
 * Time Complexity: O(n) — single pass through the array
 * Space Complexity: O(n) — new array of size n+1
 * 
 * @param arr The original array of numbers
 * @returns Prefix sum array where prefix[i] = sum of arr[0..i-1]
 */
function buildPrefixSum(arr: number[]): number[] {
    const n = arr.length;
    const prefix = new Array(n + 1).fill(0);
    
    // prefix[0] = 0 (sentinel for empty range)
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    return prefix;
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefixSums = buildPrefixSum(data);
 
console.log("Original:", data);
// [3, 1, 4, 1, 5, 9, 2, 6]
 
console.log("Prefix Sums:", prefixSums);
// [0, 3, 4, 8, 9, 14, 23, 25, 31]

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

/**
 * In-place prefix sum transformation.
 * Modifies the array to contain cumulative sums.
 * 
 * After transformation: arr[i] = sum of original arr[0..i]
 * 
 * Time: O(n), Space: O(1) auxiliary
 */
function prefixSumInPlace(arr: number[]): void {
    for (let i = 1; i < arr.length; i++) {
        arr[i] += arr[i - 1];
    }
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
prefixSumInPlace(data);
console.log(data);
// [3, 4, 8, 9, 14, 23, 25, 31]
 
// Note: Range query adjustment needed since no sentinel at index 0
// Sum(i to j) = arr[j] - arr[i-1] (handle i=0 specially)

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

/**
 * Answer a range sum query in O(1) time using prefix sums.
 * 
 * @param prefix The precomputed prefix sum array (size n+1)
 * @param left Starting index of the range (inclusive)
 * @param right Ending index of the range (inclusive)
 * @returns Sum of elements from index left to right
 */
function rangeSum(prefix: number[], left: number, right: number): number {
    return prefix[right + 1] - prefix[left];
}
 
// Complete example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = buildPrefixSum(data);
 
// Various range queries — all O(1)
console.log(rangeSum(prefix, 0, 7));  // Entire array: 31
console.log(rangeSum(prefix, 2, 5));  // Indices 2-5: 19
console.log(rangeSum(prefix, 0, 0));  // Single element: 3
console.log(rangeSum(prefix, 4, 7));  // Indices 4-7: 22
console.log(rangeSum(prefix, 3, 3));  // Single element: 1

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

/**
 * 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];
    }
}

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

/**
 * 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]

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

/**
 * 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 = 18

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

/**
 * Count subarrays with sum equal to k.
 * Uses prefix sums + hash map for O(n) solution.
 */
function subarraySum(nums: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    prefixCount.set(0, 1); // Empty prefix has sum 0
    
    let count = 0;
    let currentSum = 0;
    
    for (const num of nums) {
        currentSum += num;
        
        // How many previous prefix sums equal (currentSum - k)?
        const target = currentSum - k;
        if (prefixCount.has(target)) {
            count += prefixCount.get(target)!;
        }
        
        // Record this prefix sum
        prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
    }
    
    return count;
}
 
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2