loading...

LeetCode 238. Product of Array Except Self

algobot76 profile image Kaitian Xie Updated on ・1 min read
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];

        for (int i = 0, temp = 1; i < len; i++) {
            ans[i] = temp;
            temp *= nums[i];
        }
        for (int i = len - 1, temp = 1; i >= 0; i--) {
            ans[i] *= temp;
            temp *= nums[i];
        }

        return ans;
    }
}

After the first for loop, nums[i] is equal to the product of the numbers from 0 to i - 1. At each iteration of the second for loop, nums[i] is multiplied by the product of the numbers from i + 1 to len - 1. Therefore, after the two for loops, nums[i] = nums[0] * nums[1] * ... * nums[i-1] * ... * nums[i+1] * ... * nums[len-1].

Time Complexity: O(n)

Extra Space: O(1)

Discussion

pic
Editor guide