LeetCode Python/Java/C++/JS  >  Array  >  238. Product of Array Except Self  >  Solved in Ruby, Python, Java, C++, JavaScript, C#, Go  >  GitHub or Repost

    LeetCode link: 238. Product of Array Except Self, difficulty: Medium.

    Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

    The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

    You must write an algorithm that runs in O(n) time and without using the division operation.

    Example 1:

    Input: nums = [1,2,3,4]

    Output: [24,12,8,6]

    Example 2:

    Input: nums = [-1,1,0,-3,3]

    Output: [0,0,9,0,0]

    Constraints:

    • 2 <= nums.length <= 10^5
    • -30 <= nums[i] <= 30
    • The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

    Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

    Hint 1

    Think how you can efficiently utilize prefix and suffix products to calculate the product of all elements except self for each index. Can you pre-compute the prefix and suffix products in linear time to avoid redundant calculations?

    Hint 2

    Can you minimize additional space usage by reusing memory or modifying the input array to store intermediate results?

    Intuition
    PreviousNext

    1. Decompose the Problem: Break down the product except self into left product × right product
    2. Two Passes:
      • First pass: Calculate the left product for each element
      • Second pass: Calculate the right product for each element
    3. Combine Results: Multiply left and right products to get the final result

    Pattern of "Pre-Computation Techniques"

    Pre-Computation Techniques are an optimization method that reduces real-time computational overhead by calculating and storing intermediate or frequently used data in advance. The core idea is "trade space for time."

    Key Application Scenarios

    • Prefix/Suffix computation problems for arrays.
    • High-frequency computation problems: Such as Fibonacci sequences, factorials, prime number tables, etc., which avoid repetitive calculations by pre-generating lookup tables.
    • Dynamic Programming (DP): Pre-computing and storing solutions to sub-problems, e.g., the knapsack problem or shortest path problems.

    Step by Step Solutions

    1. Initialize Arrays:

      • Create a leftProducts array to store the product of all elements to the left of each element
      • Create a rightProducts array to store the product of all elements to the right of each element

    2. Compute Left Products (Left to Right Pass):

      • The left product of the first element is initialized to 1
      • For subsequent elements: leftProducts[i] = nums[i-1] * leftProducts[i-1]

    3. Compute Right Products (Right to Left Pass):

      • The right product of the last element is initialized to 1
      • For previous elements: rightProducts[i] = nums[i+1] * rightProducts[i+1]

    4. Combine Results:

      • For each position, multiply left and right products: answer[i] = leftProducts[i] * rightProducts[i]

    5. Return the Result Array

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(N)

    Solution in languages: Ruby Python Java C++ JavaScript C# Go

    Ruby # 

    # @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
  #           nums: [1,  2, 3, 4]
  #  left_products: [1,  1, 2, 6]
  # right_products: [24,12, 4, 1]
  #         answer: [24,12, 8, 6]
  size = nums.size

  left_products = Array.new(size, 1)
  (1...size).each do |i|
    left_products[i] = nums[i - 1] * left_products[i - 1]
  end

  right_products = Array.new(size, 1)
  (size - 2).downto(0) do |i|
    right_products[i] = nums[i + 1] * right_products[i + 1]
  end

  answer = []
  (0...size).each do |i|
    answer << left_products[i] * right_products[i]
  end

  answer
end

    Python # 

    class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)

        #           nums: [1,  2, 3, 4]
        #  left_products: [1,  1, 2, 6]
        # right_products: [24,12, 4, 1]
        #         answer: [24,12, 8, 6]
        left_products = [1] * size
        for i in range(1, size):
            left_products[i] = nums[i - 1] * left_products[i - 1]

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

        answer = []
        for i in range(size):
            answer.append(left_products[i] * right_products[i])

        return answer

    Java # 

    class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        int[] leftProducts = new int[size];
        leftProducts[0] = 1;
        for (int i = 1; i < size; i++) {
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];
        }

        int[] rightProducts = new int[size];
        rightProducts[size - 1] = 1;
        for (int i = size - 2; i >= 0; i--) {
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];
        }

        int[] answer = new int[size];
        for (int i = 0; i < size; i++) {
            answer[i] = leftProducts[i] * rightProducts[i];
        }

        return answer;
    }
}

    C++ # 

    class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        vector<int> left_products(size, 1);
        for (int i = 1; i < size; i++) {
            left_products[i] = nums[i - 1] * left_products[i - 1];
        }

        vector<int> right_products(size, 1);
        for (int i = size - 2; i >= 0; i--) {
            right_products[i] = nums[i + 1] * right_products[i + 1];
        }

        vector<int> answer(size);
        for (int i = 0; i < size; i++) {
            answer[i] = left_products[i] * right_products[i];
        }

        return answer;
    }
};

    JavaScript # 

    /**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  const size = nums.length

  const leftProducts = new Array(size).fill(1)
  for (let i = 1; i < size; i++) {
    leftProducts[i] = nums[i - 1] * leftProducts[i - 1]
  }

  const rightProducts = new Array(size).fill(1)
  for (let i = size - 2; i >= 0; i--) {
    rightProducts[i] = nums[i + 1] * rightProducts[i + 1]
  }

  const answer = []
  for (let i = 0; i < size; i++) {
    answer.push(leftProducts[i] * rightProducts[i])
  }

  return answer
};

    C# # 

    public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int size = nums.Length;
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        int[] leftProducts = new int[size];
        leftProducts[0] = 1;

        for (int i = 1; i < size; i++)
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];

        int[] rightProducts = new int[size];
        rightProducts[size - 1] = 1;

        for (int i = size - 2; i >= 0; i--)
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];

        int[] answer = new int[size];

        for (int i = 0; i < size; i++)
            answer[i] = leftProducts[i] * rightProducts[i];

        return answer;
    }
}

    Go # 

    func productExceptSelf(nums []int) []int {
    size := len(nums)

    leftProducts := make([]int, size)
    leftProducts[0] = 1
    for i := 1; i < size; i++ {
        leftProducts[i] = nums[i - 1] * leftProducts[i - 1]
    }

    rightProducts := make([]int, size)
    rightProducts[size - 1] = 1
    for i := size - 2; i >= 0; i-- {
        rightProducts[i] = nums[i + 1] * rightProducts[i + 1]
    }

    answer := make([]int, size)
    for i := 0; i < size; i++ {
        answer[i] = leftProducts[i] * rightProducts[i]
    }

    return answer
}
    Solution in languages: Ruby Python Java C++ JavaScript C# Go

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 238. Product of Array Except Self. Thanks!

    Intuition of solution 2: Rolling variable O(1)

    1. Space Optimization: Utilize the output array to store intermediate results, avoiding extra space
    2. Two-Phase Calculation: First compute left products and store in the result, then dynamically compute right products and merge directly
    3. In-Place Operation: Use only a single variable to dynamically maintain the right product

    Step by Step Solutions

    1. Initialize Result Array:

      • Create an answer array of the same size, initialized with all 1s

    2. Compute Left Products (Left → Right Pass):

      • Initialize left_product = 1
      • During traversal: answer[i] = left_product, then left_product *= nums[i]

    3. Compute Right Products and Merge (Right → Left Pass):

      • Initialize right_product = 1
      • During traversal: answer[i] *= right_product, then right_product *= nums[i]

    4. Return Result Array

      • Space Complexity: O(1) (Output array not counted in space complexity)

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Solution in languages: Ruby Python Java C++ JavaScript C# Go

    Ruby # 

    # @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
  size = nums.size
  answer = Array.new(size, 1)

  left_product = 1
  (0...size).each do |i|
    answer[i] = left_product
    left_product *= nums[i]
  end

  #    nums: [1,  2, 3, 4]
  #  answer: [1,  1, 2, 6]  left_product done 
  #  answer: [24,12, 8, 6] right_product done

  right_product = 1
  (size - 1).downto(0) do |i|
    answer[i] *= right_product
    right_product *= nums[i]
  end

  answer
end

    Python # 

    class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        answer = [1] * size

        left_product = 1
        for i in range(size):
            answer[i] = left_product
            left_product *= nums[i]

        #    nums: [1,  2, 3, 4]
        #  answer: [1,  1, 2, 6]  left_product done 
        #  answer: [24,12, 8, 6] right_product done

        right_product = 1
        for i in range(size-1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]

        return answer

    Java # 

    class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] answer = new int[size];
        Arrays.fill(answer, 1);

        int leftProduct = 1;
        for (int i = 0; i < size; i++) {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  leftProduct done 
        //  answer: [24,12, 8, 6] rightProduct done

        int rightProduct = 1;
        for (int i = size - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

    C++ # 

    class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> answer(size, 1);

        int left_product = 1;
        for (int i = 0; i < size; ++i) {
            answer[i] = left_product;
            left_product *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  left_product done 
        //  answer: [24,12, 8, 6] right_product done

        int right_product = 1;
        for (int i = size - 1; i >= 0; --i) {
            answer[i] *= right_product;
            right_product *= nums[i];
        }

        return answer;
    }
};

    JavaScript # 

    /**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  const answer = [];
  let left_product = 1;

  for (let i = 0; i < nums.length; i++) {
    answer[i] = left_product;
    left_product *= nums[i];
  }

  //  nums: [1,  2, 3, 4]
  //  answer: [1,  1, 2, 6]  left_product done 
  //  answer: [24,12, 8, 6] right_product done

  right_product = 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    answer[i] *= right_product;
    right_product *= nums[i];
  }

  return answer;
};

    C# # 

    public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int size = nums.Length;
        int[] answer = new int[size];
        Array.Fill(answer, 1);

        int leftProduct = 1;
        for (int i = 0; i < size; i++)
        {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  leftProduct done 
        //  answer: [24,12, 8, 6] rightProduct done

        int rightProduct = 1;
        for (int i = size - 1; i >= 0; i--)
        {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

    Go # 

    func productExceptSelf(nums []int) []int {
    n := len(nums)
    answer := make([]int, n)

    answer[0] = 1
    for i := 1; i < n; i++ {
        answer[i] = answer[i-1] * nums[i-1]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        answer[i] *= right
        right *= nums[i]
    }

    return answer
}
    Solution in languages: Ruby Python Java C++ JavaScript C# Go

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 238. Product of Array Except Self. Thanks!
    PreviousNext