Product of Array Except Self
Medium About 20 min Free, no account needed
For each index, return the product of all other elements, without division.
The brief
Given an integer array nums, return an array answer where answer[i] is the
product of every element except nums[i]. Do not use division.
The obvious approach recomputes a fresh product for every index, O(n²). The hidden
test uses 200,000 elements, so the quadratic version is too slow. You will need
ProductExceptSelf to run in O(n) (and remember, no division).
Starter code
using System;
public class Solution
{
// TODO: return an array where each position holds the product of all the other values.
public long[] ProductExceptSelf(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Subarray Sum Equals K Medium Free Count contiguous subarrays whose elements sum to a target k.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.
- Sum of Absolute Differences Medium Free For each element of a sorted array, the total distance to all the others.