/*You have an array of integers, and for each index you want to find the product of every integer except the integer at that index. Write a function get_products_of_all_ints_except_at_index() that takes an array of integers and returns an array of the products.*/ Greedy/DP approach

productExceptIndexDP.java

/*You have an array of integers, and for each index you want to find the product
of every integer except the integer at that index.
Write a function get_products_of_all_ints_except_at_index() that takes an array 
of integers and returns an array of the products.*/

public static int[] get_products_of_all_ints_except_at_index_dp(int[] arr){
    //build front
    int[] front = new int[arr.length];
    front[0] = 1;
    for(int i = 1; i < arr.length; i++){
        front[i] = front[i-1] * arr[i-1];
    }

    //build back
    int temp = 1;
    for(int i = arr.length-1; i >= 0; i--){
        front[i] = front[i]*temp;
        temp = temp*arr[i];
    }

    return front;
}

productExceptIndexDP3N.java

public static int[] get_products_of_all_ints_except_at_index_dp(int[] arr){
    //build front
    int[] front = new int[arr.length];
    front[0] = 1;
    for(int i = 1; i < arr.length; i++){
        front[i] = front[i-1] * arr[i-1];
    }

    //build back
    int[] back = new int[arr.length];
    back[arr.length-1] = 1;
    for(int i = arr.length-2; i >= 0; i--){
        back[i] = back[i+1] * arr[i+1];
    }
    
    for(int i = 0; i < arr.length; i++){
      arr[i] = front[i]*back[i];
    }

    return arr;
}