Product Of Array Except Self Problem


Description

LeetCode Problem 238.

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 inO(n)time and without using the division operation.

Example 1:

1
2
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

1
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 product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return nums;
        
        vector<int> left(n), right(n);
        left[0] = nums[0], right[n-1] = nums[n-1];
        for (int i = 1; i < n; i ++) {
            left[i] = left[i-1] * nums[i];
            right[n-i-1] = right[n-i] * nums[n-i-1];
        }
        
        vector<int> ans(n, 1);
        for (int i = 0; i < n; i ++) {
            if (i > 0) {
                ans[i] = ans[i] * left[i-1];
            }
            if (i < n-1) {
                ans[i] = ans[i] * right[i+1];
            }
        }
        
        return ans;
    }
};




Related Posts

1-Bit And 2-Bit Characters Problem

LeetCode 717. We have two special characters, the first character...

Teemo Attacking Problem

LeetCode 495. Our hero Teemo is attacking an enemy Ashe...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Max Consecutive Ones Problem

LeetCode 485. Given a binary array nums, return the maximum...

132 Pattern Problem

LeetCode 456. Given an arrayof n integers nums, a 132...

Summary Ranges Problem

LeetCode 228. You are given a sorted unique integer array...