[LeetCode] 238. Product of Array Except Self (JS)

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

Product of Array Except Self - LeetCode

핵심 아이디어

• result[i]의 값은 왼쪽 부분(prefix)의 곱과 오른쪽 부분(postfix)의 곱을 곱한 것이다
  
  • prefix[i]와 postfix[i] 는 각자 이전 값에다 nums[i]를 곱하면 되기 때문에 O(1) 시간에 구할 수 있다
• result array에 prefix 값을 쓰고, 다시 반대로 읽으면서 postfix 값을 쓰면서 공간 복잡도를 O(1)으로 줄일 수 있다
  • result array는 어차피 답 출력할 때 써야 하는 array이므로 공간 복잡도 계산에 포함되지 않는다

 

복잡도

• 시간 복잡도: O(n)
  
  • 배열을 순방향, 역방향으로 2회 순회
  • 이전 값에 누적하며 곱하는 방식으로 prefix 구하기 O(n) + 반대 방향으로 postfix 곱하면서 채우기 O(n)
• 공간 복잡도: O(1)
  
  • 출력할 때 쓰는 result array를 활용 (공간 복잡도 계산 x)
  • prefix 변수 O(1), postfix 변수 O(1)

 

설명

 

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let result = Array(nums.length);
    
    let prefixProduct = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }
    
    let postfixProduct = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= postfixProduct;
        postfixProduct *= nums[i];
    }
    
    return result;
};

 

유튜브 NeetCode 해설 영상