Leetcode 238； Product of Array except itself

March 21, 2016

Worked on the algorithm LeetCode 238:

Product of an array
http://juliachencoding.blogspot.ca/2015/07/two-algorithms-questions.html

http://fisherlei.blogspot.ca/2015/10/leetcode-product-of-array-except-self.html

Julia likes to share some tips about writing the code, assuming that you know the optimal solution is using dynamic programming (DP), and extra space is O(N).

For example,

Array: [1, 2, 3 ,4], denoted as arr[].

for each i, i = 0 to 3,
product of i, denoted as P[i],
leftP[i]   = arr[0] *arr[1]*...arr[i-1] = leftP[i-1]*arr[i-1].
rightP[i] = ...
P[i[ = leftP[i] * rightP[i]

write C# code:

1  public static int[] getProduct(int[] arr)   // not A, match description: arr  <- complaint 1, style
2 {
3      if(arr== null || arr.Length ==0) return null;
4
5     int n = arr.Length;
6     int[] res = new int[n];
7
8   int tmp =1;
9    for(int i=0; i< n; i++)
10   {
11       if( i ==0)         // <- complaint 2: 
12            res[0] = 1; // <-  complaint 2: not necessary, remove if clause

}

So, write again starting from line 9. Remember the analysis, only thing you have to do, one multiplication, one extra variable to store previous result - tmp.

Code should match the analysis <-  Julia learned the lesson. 

8    int tmp = 1; 
9    for(int i=0; i< n; i++)
10   {
11       res[i] = tmp;   // it works when i = 0; 
12       tmp *= arr[i];
13   }

    that is the code for leftP[i].

Next practice:
https://www.hackerrank.com/challenges/computing-the-correlation

https://www.hackerrank.com/challenges/unbounded-knapsack