Product of Array Except Self - Practice Coding Problems

Product of Array Except Self - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: [24,12,8,6]

💡 Note: For index 0: product = 2×3×4 = 24. For index 1: product = 1×3×4 = 12. For index 2: product = 1×2×4 = 8. For index 3: product = 1×2×3 = 6.

Example 2 — With Zero

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

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

💡 Note: Since there's a 0 in the array, all positions except index 2 will have product 0. At index 2 (skipping the 0): product = (-1)×1×(-3)×3 = 9.

Example 3 — Small Array

$ Input: nums = [2,3]

› Output: [3,2]

💡 Note: For index 0: skip nums[0]=2, product = 3. For index 1: skip nums[1]=3, product = 2.

Constraints

2 ≤ nums.length ≤ 10⁵
-30 ≤ nums[i] ≤ 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,2,3,4] - need product excluding each element

Calculate Products

For each position, multiply all other elements

Result Array

Output [24,12,8,6] where each element is product of all others

Key Takeaway

🎯 Key Insight: Product except current = (left products) × (right products), allowing O(n) time solution

Asked in

G Google 45 a Amazon 38 f Facebook 32 A Apple 28

The key insight is that the product except current element equals the product of all left elements times the product of all right elements. The optimal approach uses the output array to store left products first, then traverses right-to-left to multiply by right products. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass - Left and Right Products	O(n)	O(n)	Calculate left products, then right products in separate passes
Space Optimized - Single Array	O(n)	O(1)	Use output array to store left products, then traverse right to calculate final result
Brute Force - Nested Loops	O(n²)	O(1)	For each position, multiply all other elements

Two Pass - Left and Right Products — Algorithm Steps

Create left array with products of elements to the left
Create right array with products of elements to the right
Multiply left[i] * right[i] for final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Left Products

Product of all elements to the left of each position

Calculate Right Products

Product of all elements to the right of each position

Multiply Together

left[i] × right[i] gives final answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* left = (int*)malloc(numsSize * sizeof(int));
    int* right = (int*)malloc(numsSize * sizeof(int));
    int* answer = (int*)malloc(numsSize * sizeof(int));
    
    // Initialize arrays
    for (int i = 0; i < numsSize; i++) {
        left[i] = 1;
        right[i] = 1;
    }
    
    // Fill left array
    for (int i = 1; i < numsSize; i++) {
        left[i] = left[i-1] * nums[i-1];
    }
    
    // Fill right array
    for (int i = numsSize-2; i >= 0; i--) {
        right[i] = right[i+1] * nums[i+1];
    }
    
    // Combine results
    for (int i = 0; i < numsSize; i++) {
        answer[i] = left[i] * right[i];
    }
    
    free(left);
    free(right);
    return answer;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, count, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate loops through the array, each taking O(n) time

✓ Linear Growth

Space Complexity

O(n)

Extra arrays for left and right products, each of size n

⚡ Linearithmic Space

89.5K Views

Very High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass - Left and Right Products — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler