Suffix Product

The suffix product array of a given array is an auxiliary array where each element is the product of all elements to the right of that index.

This allows answering range product queries in O(1) time.

For array a[], suffixProduct[i] = a[i] * a[i+1] * … * a[n-1]

Java example:

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

int[] suffixProduct(int[] arr) {
  int n = arr.length;
  int[] suffixProd = new int[n];  

  suffixProd[n-1] = arr[n-1];
  for (int i = n-2; i >= 0; i--) {
    suffixProd[i] = suffixProd[i+1] * arr[i];
  }

  return suffixProd;
}

// Get product of interval [i, j]
int prod(int i, int j, int[] suffixProd) {
  if (i == 0) return suffixProd[j];
  return suffixProd[j] / suffixProd[i-1];
}

C++ example:

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

vector<int> suffixProduct(vector<int> arr) {
  int n = arr.size();
  vector<int> suffixProd(n);

  suffixProd[n-1] = arr[n-1];
  for (int i = n-2; i >= 0; i--) {
    suffixProd[i] = suffixProd[i+1] * arr[i];
  }

  return suffixProd;
}

// Get product of interval [i, j]
int prod(int i, int j, vector<int>& suffixProd) {
  if (i == 0) return suffixProd[j];
  return suffixProd[j] / suffixProd[i-1];
} 

Python example:

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

def suffix_product(arr):
  
  n = len(arr)
  suffixProd = [0] * n

  suffixProd[n-1] = arr[n-1]
  for i in range(n-2, -1, -1):
    suffixProd[i] = suffixProd[i+1] * arr[i]

  return suffixProd

# Get product of interval [i, j]
def prod(i, j, suffixProd):
  if i == 0: return suffixProd[j]
  return suffixProd[j] / suffixProd[i-1]

Suffix products allow fast range product queries on arrays. Useful for combinatorics problems.

The concept of Suffix Product involves calculating the product of elements in an array from the current index to the last index. This is known as the “suffix” product because it includes the current element and all elements that come after it in the array.

A common application of this concept is when you want to calculate the product of all elements in an array except for the current element at each index. By using the Suffix Product in combination with a Prefix Product, you can achieve this without explicitly using division.

Solution

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int[] suffixProduct(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    result[n - 1] = nums[n - 1];
    
    for(int i = n - 2; i >= 0; i--) {
        result[i] = result[i + 1] * nums[i];
    }

    return result;
}

C++:

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

#include <vector>

std::vector<int> suffixProduct(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n);
    result[n - 1] = nums[n - 1];

    for(int i = n - 2; i >= 0; i--) {
        result[i] = result[i + 1] * nums[i];
    }

    return result;
}

Python:

1
2
3
4
5
6
7
8
9

def suffixProduct(nums):
    n = len(nums)
    result = [0] * n
    result[n - 1] = nums[n - 1]

    for i in range(n - 2, -1, -1):
        result[i] = result[i + 1] * nums[i]

    return result

In each of these examples, we are iterating through the input array from right to left, calculating the Suffix Product as we go. The result is an array containing the Suffix Product for each element, where result[i] is the product of all elements from nums[i] to the end of the array.

Tabular Representation

Here’s an example table that shows the input and what happens in each iteration for each of the elements in the array when calculating the Suffix Product.

Consider an input array: nums = [2, 3, 4, 5]

Here’s the step-by-step breakdown of the table:

1. Iteration 1: The last element is 5. There are no elements to the right, so the suffix product is just the current element itself: 5.
2. Iteration 2: The current element is 4. Multiply it with the next element in the result array (5): 4 * 5 = 20.
3. Iteration 3: The current element is 3. Multiply it with the next element in the result array (20): 3 * 20 = 60.
4. Iteration 4: The current element is 2. Multiply it with the next element in the result array (60): 2 * 60 = 120.

The final result is the Suffix Product Array: [120, 60, 20, 5], which is the product of all elements from the current index to the end of the array for each index.