BL
U

44. Product of Array Except Self

Med.

Problem Description

Given an array of NN integers, return an array such that output[i] equals the product of all elements of the original array except nums[i], without using the division operator.

Input Format

  • •Line 1: An integer NN (2≤N≤1052 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print NN space-separated integers.

Example 1:
Input:
4
1 2 3 4
Output:
24 12 8 6
Explanation: Products: 2*3*4=24, 1*3*4=12, 1*2*4=8, 1*2*3=6.
Example 2:
Input:
5
-1 1 0 -3 3
Output:
0 0 9 0 0
Explanation: Elements containing zero.
Example 3:
Input:
2
5 2
Output:
2 5
Explanation: For [5, 2], product except self is [2, 5].
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online