Product of Array Except Self – DSA Problem Explained

Nidhi Sharma
4d
222
0
0

Article

Introduction

The Product of Array Except Self is a very popular DSA interview question. It is commonly asked because it tests your understanding of arrays, prefix calculations, and space optimization.

In this problem, you are asked to compute the product of all elements of an array except the current element, without using the division operator.

This article explains the solution in simple words, with clear examples and interview-ready code.

What is the Product of Array Except Self Problem?

You are given an integer array nums. You need to return a new array answer such that:

answer[i] is the product of all elements of nums except nums[i]
Division is not allowed

Example

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

Explanation

For index 0 → 2 × 3 × 4 = 24
For index 1 → 1 × 3 × 4 = 12
For index 2 → 1 × 2 × 4 = 8
For index 3 → 1 × 2 × 3 = 6

Why Division is Not Allowed

A simple solution using total product and division will fail in many cases:

If the array contains zero
Division-based solutions are often restricted in interviews

So, we must find an alternative approach.

Brute Force Approach (Not Recommended)

In the brute-force method, for each index, we multiply all other elements.

Drawbacks

Time Complexity becomes O(n²)
Very slow for large arrays

This approach is not suitable for interviews.

Optimized Approach Using Prefix and Suffix Product

The best solution uses prefix product and suffix product.

Idea

Prefix product stores product of elements to the left
Suffix product stores product of elements to the right
Final result is multiplication of prefix and suffix

This avoids division and reduces time complexity.

Step-by-Step Explanation

Steps:

Create an array answer initialized with 1
Traverse from left to right and store prefix product
Traverse from right to left and multiply suffix product
Store final result in answer

Dry Run Example

Array: [1, 2, 3, 4]

Prefix pass:

answer = [1, 1, 2, 6]

Suffix pass:

answer = [24, 12, 8, 6]

Final Answer = [24, 12, 8, 6]

Code Implementation

C++ Code

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

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

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

    return answer;
}

Java Code

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

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

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

    return answer;
}

Python Code

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

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

    return answer

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(1) (excluding output array)

This solution is efficient and interview-friendly.

Edge Cases to Consider

Array containing one or more zeros
Array with negative numbers
Array size is 1

Always test these cases.

Common Interview Variations

Product of array except self with division allowed
Product of array except self using recursion
Similar prefix-suffix based problems

Summary

The Product of Array Except Self problem is a classic DSA question that teaches you how to optimize array calculations without using division. By using prefix and suffix products, you can solve this problem efficiently in linear time and constant space. Understanding this approach will help you solve many related problems and perform confidently in coding interviews.