Prefix and Suffix Arrays

A Prefix Array, also known as a Prefix Sum Array or Cumulative Sum Array, is an Array with the calculation of cumulative sums of elements in a source array. It stores the cumulative sum of elements up to a certain index in the array. This can also be done in-place, so that the target rewrites values of the source.

Prefix and Suffix arrays are useful for range computations. For example, LeetCode 1608. Special Array With X Elements Greater Than or Equal X

Here’s how it works:

Given an array of numbers, the prefix array would be another array where each element prefix[i] stores the sum of elements from index 0 to index i in the array.

For example, given nums = [1, 2, 3, 4, 5], the prefix array would be [1, 3, 6, 10, 15], because:

prefix[0] = 1                      // sum from nums[0] to [0]
prefix[1] = 1 + 2 = 3              // sum from nums[0] to [1]
prefix[2] = 1 + 2 + 3 = 6          // sum from nums[0] to [2]
prefix[3] = 1 + 2 + 3 + 4 = 10     // sum from nums[0] to [3]
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 // sum from nums[0] to [4]
Code language: JavaScript (javascript)

Here is an example of creating a prefix array in-place, in JavaScript:—

const nums = [1, 2, 3, 4, 5];
nums.forEach((num, i) => nums[i] += nums[i-1] ?? 0);
// [1, 3, 6, 10, 15]
Code language: JavaScript (javascript)

Suffix Array:

A suffix array is similar to a prefix array, but it stores cumulative sums in reverse order. Instead of storing the sum of elements up to a certain index from left to right, a suffix array stores the sum of elements from right to left.

Given the array nums = [1, 2, 3, 4, 5], the suffix array would be:—

suffix[4] = 5
suffix[3] = 5 + 4 = 9
suffix[2] = 5 + 4 + 3 = 12
suffix[1] = 5 + 4 + 3 + 2 = 14
suffix[0] = 5 + 4 + 3 + 2 + 1 = 15

//  [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

Suffix Array Code

Creating a suffix array function is a little trickier than writing a prefix array. It can be done with a new array or in-place, replacing values of an existing array. Here are both.

function createSuffixArray(nums) {
    const suffixArray = new Uint32Array(nums);
    for (let i = suffixArray.length - 2; i >= 0; i--) {
        suffixArray[i] += suffixArray[i+1];
    }
    return suffixArray;
}

const nums = [1, 2, 3, 4, 5];
createSuffixArray(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

By pre-allocating a Uint32Array of the appropriate length and iterating over the input array from right to left, I efficiently compute the cumulative sums and store them directly in the suffix array without needing to reverse the array or create intermediate copies. This approach is concise and efficient.

This can also be done in-place.

function createSuffixArrayInPlace(nums) {
    for (let i = nums.length - 2; i >= 0; i--) {
        nums[i] += nums[i+1];
    }
    return nums; // Optional: Return the modified nums array
}

const nums = [1, 2, 3, 4, 5];
const suffixArray = createSuffixArrayInPlace(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)