What is the time complexity of Product of Array Except Self?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Product of Array Except Self?

This problem uses Array, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Product of Array Except Self?

Insight 1: The key is to realize that `answer[i]` can be expressed as the product of all elements to the left of `nums[i]` multiplied by the product of all elements to the right of `nums[i]`. Insight 2: Instead of explicitly calculating left and right products in separate arrays (which would violate O(1) extra space), we can compute them iteratively in place using the output array itself.

Which companies ask LeetCode 238. Product of Array Except Self in interviews?

This problem is frequently asked at Accenture, Asana, Autodesk, CEDCOSS, Cisco and 29 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Product of Array Except Self - LeetCode 238 Solution

Q: How to solve Product of Array Except Self?

The solution calculates the product of all elements to the left of each element in a single pass and stores it in the `answer` array. Then, it calculates the product of all elements to the right of each element in another pass, multiplying this right product with the corresponding element in the `answer` array, effectively achieving the desired product of elements except self. This avoids division and keeps the time complexity linear.

Product of Array Except Self - Complete Solution Guide

Product of Array Except Self is LeetCode problem 238, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 in

Detailed Explanation

The problem asks us to compute an array `answer` from a given integer array `nums` such that `answer[i]` is the product of all the elements in `nums` *except* `nums[i]`. We need to accomplish this in O(n) time and without using division. The product of any prefix or suffix is guaranteed to fit within a 32-bit integer, and the output array doesn't count toward extra space when considering space complexity.

Solution Approach

The solution calculates the product of all elements to the left of each element in a single pass and stores it in the `answer` array. Then, it calculates the product of all elements to the right of each element in another pass, multiplying this right product with the corresponding element in the `answer` array, effectively achieving the desired product of elements except self. This avoids division and keeps the time complexity linear.

Step-by-Step Algorithm

Step 1: Initialize an array `answer` of the same size as `nums` with all elements set to 1. This array will store the final result.
Step 2: Calculate the product of all elements to the left of each element. Iterate through the `nums` array from left to right, maintaining a `left_product`. For each index `i`, set `answer[i]` to the current `left_product`, then update `left_product` by multiplying it with `nums[i]`.
Step 3: Calculate the product of all elements to the right of each element. Iterate through the `nums` array from right to left, maintaining a `right_product`. For each index `i`, multiply `answer[i]` (which already contains the product of elements to the left) by the current `right_product`, then update `right_product` by multiplying it with `nums[i]`.
Step 4: Return the `answer` array.

Key Insights

Insight 1: The key is to realize that `answer[i]` can be expressed as the product of all elements to the left of `nums[i]` multiplied by the product of all elements to the right of `nums[i]`.
Insight 2: Instead of explicitly calculating left and right products in separate arrays (which would violate O(1) extra space), we can compute them iteratively in place using the output array itself.
Insight 3: Initialization of output array is crucial and should be carefully considered based on the overall calculations.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Prefix Sum.

Companies

Asked at: Accenture, Asana, Autodesk, CEDCOSS, Cisco, Disney, Docusign, Flipkart, Goldman Sachs, IBM, Infosys, Intuit, LinkedIn, Lyft, MakeMyTrip, Nutanix, Oracle, PayPal, Paytm, Ripple, Salesforce, Sigmoid, Snap, Tekion, Turing, Unity, Walmart Labs, Warnermedia, Wells Fargo, Yandex, ZS Associates, Zoho, eBay, tcs.

Product of Array Except Self | LeetCode 238

Medium

Array Prefix Sum

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = 1;
        }

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

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

        return answer;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 238: Product of Array Except Self - Detailed explanation and solution approaches.

Topics

Array Prefix Sum

Companies

AccentureAsanaAutodeskCEDCOSSCiscoDisneyDocusignFlipkart

Stats

Difficulty:Medium

Languages:4

Companies:34

Problem #:238

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Initialize an array `answer` of the same size as `nums` with all elements set to 1. This array will store the final result.
2
Step 2: Calculate the product of all elements to the left of each element. Iterate through the `nums` array from left to right, maintaining a `left_product`. For each index `i`, set `answer[i]` to the current `left_product`, then update `left_product` by multiplying it with `nums[i]`.
3
Step 3: Calculate the product of all elements to the right of each element. Iterate through the `nums` array from right to left, maintaining a `right_product`. For each index `i`, multiply `answer[i]` (which already contains the product of elements to the left) by the current `right_product`, then update `right_product` by multiplying it with `nums[i]`.
4
Step 4: Return the `answer` array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the input array twice. Both passes are linear in terms of the input size. The space complexity is O(1) because the output array is not considered extra space, and the only additional variables used (`left_product`, `right_product`) take constant space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Division (but forbidden)

Calculate the product of all elements in the array. Then, for each element, divide the total product by that element to get the desired result. This approach is straightforward but violates the constraint of not using division.

Time: O(n)Space: O(1)

Trade-offs: This is simpler to implement but is not allowed by the problem constraints.

✨

Key Insights

1Insight 1: The key is to realize that `answer[i]` can be expressed as the product of all elements to the left of `nums[i]` multiplied by the product of all elements to the right of `nums[i]`.
2Insight 2: Instead of explicitly calculating left and right products in separate arrays (which would violate O(1) extra space), we can compute them iteratively in place using the output array itself.
3Insight 3: Initialization of output array is crucial and should be carefully considered based on the overall calculations.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Input array contains zero(s). If there is one zero, all elements of the output will be zero, except the element corresponding to zero's index, which will be the product of all other elements. If there are two or more zeros, then the whole output will be an array of zeros. This solution correctly handles cases with one zero because the left and right products will still function as intended. With two or more zeros, the product excluding any element will always be zero, which the algorithm inherently produces.
Edge case 2: Input array contains large numbers. While the problem guarantees that products will fit into a 32-bit integer, intermediate calculations could potentially overflow if the numbers are close to the 32-bit limit. Choosing appropriate data types (like `long` in Java) can mitigate this risk, although in the provided code, this is not explicitly handled, adhering to the problem constraint that the final result fits in 32-bits.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using division. The problem explicitly forbids this, but it's a natural first thought for many.

✗Common mistake 2: Using extra space proportional to the input size. Creating separate arrays for left and right products would lead to O(n) space complexity, violating the follow-up question's constraint.

✗Common mistake 3: Incorrectly initializing the `answer` array or the `left_product` and `right_product` variables. This can lead to incorrect products being calculated.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data analysis where you need to calculate a statistic that excludes a specific data point. For example, calculating the average revenue per customer, excluding an outlier customer that skewed the average.

🏦Real-world scenario 2: Error detection and correction in data transmission. Calculating checksums or parity bits that are based on all data except a specific segment.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 29, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Product of Array Except Self"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether prefix sum techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?