Basic Prefix Sum pattern for coding interview preparation

Basic Prefix Sum pattern is the simplest form of the Prefix Sum pattern. It is primarily used when we need to calculate the sum of elements within a range [left, right] multiple times.

The main idea is to preprocess the original array and store cumulative sums in a separate prefix array. After this preprocessing, the sum of any range can be calculated in O(1) time instead of iterating through the range every time.

The pattern can be reduced to two formulas:

Build:
prefix[i + 1] = prefix[i] + nums[i]
Query:
sum(left, right) = prefix[right + 1] - prefix[left]

For example, we have an array int nums = [2, 4, 1, 3, 5]. For a range [1, 3]:

prefix[4] = 2 + 4 + 1 + 3
prefix[1] = 2

prefix[4] - prefix[1] = (2 + 4 + 1 + 3) - 2 = 4 + 1 + 3 = 8

The key idea is:

A range sum is the difference between two cumulative sums.

Let’s see how it works in practice:

303. Range Sum Query - Immutable via Prefix Sum.

Build prefix[], then answer each range query using the difference between two prefix sums.

class NumArray {
private:
    vector<int> prefix;

public:
    NumArray(vector<int>& nums)
    {
        prefix.resize(nums.size() + 1);

        // Preprocessing — for loop creates prefix sum array
        for(int i = 0; i < nums.size(); i++)
        {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right)
    {
        // Query — calculate range sum - getting sum of [left, right]
        return prefix[right + 1] - prefix[left];
    }
};

2559. Count Vowel Strings in Ranges

Instead of the sum of numbers, we build a prefix sum of the number of words that start and end with a vowel.

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
      int n = words.size();

      vector<int> prefix(n + 1);

      auto isVowel = [](char c)
      {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
      };

      for(int i = 0; i < n; i++)
      {
        bool valid = isVowel(words[i].front()) && isVowel(words[i].back());

        // Preprocessing
        prefix[i + 1] = prefix[i] + valid;
      }

      vector<int> result;

      for(const auto& query : queries)
      {
        int left = query[0];
        int right = query[1];

        //Query
        result.push_back(prefix[right + 1] - prefix[left]);
      }

      return result;
    }
};