238. Product of Array Except Self
Product of Array Except Self (LeetCode 238) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Product Except Self (Prefix/Suffix Products) subpattern.
- Blind 75 · #7 of 75 · Arrays & Hashing
- NeetCode 150 · #7 of 150 · Arrays & Hashing
- NeetCode 250 · #16 of 250 · Arrays & Hashing
How to solve Product of Array Except Self
Product of Array Except Self is a Product of Array Except Self problem, part of Array/Matrix Manipulation Patterns. Master the prefix and suffix products technique to calculate product of array except self without division.
Work towards the solution in these steps:
- Think how you can efficiently utilize prefix and suffix products to calculate the product of all elements except self for each index. Can you pre-compute the prefix and suffix products in linear time to avoid redundant calculations?
- Can you minimize additional space usage by reusing memory or modifying the input array to store intermediate results?
The reference solution runs in O(n) time and O(1) space.
The Product of Array Except Self solution and editorial walks through the full approach with reference code.
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 <= 105
- -30 <= nums[i] <= 30
- The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Topics and companies
Topics: Array, Prefix Sum.
Reported in interviews at Facebook, Amazon, Apple, Asana, Lyft, Microsoft, Uber, Adobe, VMware, Nvidia, Oracle, Intel.
How to practise Product of Array Except Self on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Product of Array Except Self in the code editor, or read the Product of Array Except Self editorial for a worked solution with its approach and complexity analysis.
Where Product of Array Except Self sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Product Except Self (Prefix/Suffix Products) subpattern
- The full DSA patterns sheet
Problems related to Product of Array Except Self
Other problems that use the same Product Except Self (Prefix/Suffix Products) and Array/Matrix Manipulation Patterns techniques:
- Longest Mountain in Array — Medium, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Concatenation of Array — Easy, same pattern
- Contains Duplicate — Easy, same pattern
- Design HashSet — Easy, same pattern
Product of Array Except Self FAQ
What is the LeetCode number of Product of Array Except Self?
Product of Array Except Self is LeetCode problem 238, rated Medium.
What pattern is used to solve Product of Array Except Self?
Product of Array Except Self is a Product of Array Except Self problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Product Except Self (Prefix/Suffix Products) subpattern.
What is the time complexity of Product of Array Except Self?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Product of Array Except Self?
Product of Array Except Self has been reported in interviews at Facebook, Amazon, Apple, Asana, Lyft, Microsoft, Uber, Adobe, VMware, Nvidia, Oracle, Intel.