[LC] 238. Product of Array Except Self

[seungriyou]

https://leetcode.com/problems/product-of-array-except-self/

Approach

constraint에 주의해야 한다.

• O(n) time
• O(1) extra space (except output array)
• no division operation

따라서 두 방향으로 순회를 진행하면서, 지나온 원소들의 곱을 변수(prod)로 트래킹하며 result array를 업데이트 해주면 된다.

1. -> 방향 순회: 현재 원소의 왼쪽에 있는 원소들의 곱을 result에 append 하고 곱 업데이트 (prefix product)
2. <- 방향 순회: 현재 원소의 오른쪽에 있는 원소들의 곱을 result에 append 하고 곱 업데이트 (suffix product)

[!note] 실제 인터뷰 상황을 가정하고 이 문제를 푸는 글: https://leetcode.com/problems/product-of-array-except-self/solutions/1342916/3-minute-read-mimicking-an-interview

Complexity

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