Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/7f09cd29e7a75763a18f7f4a9512742f to your computer and use it in GitHub Desktop.
Save jianminchen/7f09cd29e7a75763a18f7f4a9512742f to your computer and use it in GitHub Desktop.
Array of array products - dynamic programming
using System;
class Solution
{
public static int[] ArrayOfArrayProducts(int[] arr)
{
if(arr == null || arr.Length <= 1)
{
return new int[0];
}
var length = arr.Length;
var product = new int[length];
// left to right iteration
var prefixProduct = 1;
for(int index = 0; index < length; index++)
{
product[index] = prefixProduct;
prefixProduct *= arr[index];
}
var suffixProduct = 1;
for(int index = length - 1; index >= 0; index--)
{
product[index] = product[index] * suffixProduct;
suffixProduct *= arr[index];
}
return product;
}
static void Main(string[] args)
{
var product = ArrayOfArrayProducts(new int[]{8, 10, 2});
foreach(var item in product)
{
Console.WriteLine(item);
}
}
}
/*
keywords:
integer array,
define a product except itself for each index i - for example:
[8, 10, 2]
defined product: [10 * 2, 8 * 2, 8 * 10]
ask: return array of products
Constraints: without using division
analysis:
two portion of product, prefixProduct, suffixProduct
dynamic programming
two iterations:
first one is from left to right
each iteration one multiplication
second iteration from right to left
Time complexity: O(n)
space complexity: O(n)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment