Pattern 1: Prefix Sum

• YouTube source.
• Colab notebook.
• Basic problem: find sum of elements in a sub-array.
  • Say you need to find sum of a[i] to a[j]. Then only need to loop through and add up. Hence only O(n).
• But if you have m queries (i.e. need to perform m different sums). Then if we simply repeat the above, we need O(mn). How to do it more efficiently?
• Example of single query:

  # single query
  def find_subarray_sum(array, i, j):
    subarray_sum = 0
    for k in range(i, j+1):
        subarray_sum += array[k]
    return subarray_sum
  

• Idea: create a prefix summary, where value at index i is the sum of all elements from start up to index i.
  • p[i] = a[0] + a[1] + … + a[i]
  • Now, you can do one query in just O(1):
  • sum[i,j] = p[j] - p[i-1]
  • If there is also a space constraint (you are not allow to create a new array to store p, then you can modify the input array itself), e.g:

    def create_prefix_sum(array):
    for i in range(1, len(array)):
        array[i] = array[i-1] + array[i]
    return array
    

• Related Leetcode problems:
  • 1. Range Sum Query - Immutable.
  • 1. Contiguous array
  • 1. Subarray sum equals K.

303. Range Sum Query - Immutable.

• Given an integer array nums, and multiple queries, each query is a pair of indices [i,j], return corresponding sums of these queries. Each sum is the sum of elements between the indices i, and j, inclusively

  '''
  ["NumArray", "sumRange", "sumRange", "sumRange"]
  [[-2, 0, 3, -5, 2, -1], [0, 2], [2, 5], [0, 5]]
  Output
  [null, 1, -1, -3]
  '''
  

• 525. Contiguous array.
  • Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1 ~~~python ‘’’ Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Input: nums = [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. ‘’’

* **560. Subarray sum equals K.**.
  * Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
  * A subarray is a contiguous non-empty sequence of elements within an array.
 
~~~python
# Input: nums = [1,1,1], k = 2
# Output: 2
# Input: nums = [1,2,3], k = 3
# Output: 2