Leet_Code/0238_product_of_array_except_self.py at master · Kcheung42/Leet_Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# ------------------------------------------------------------------------------
# Question: 0238_product_of_array_except_self.py
# ------------------------------------------------------------------------------
# tags:[medium, array]
'''
Given an array nums of n integers where n > 1,  return an array
output such that output[i] is equal to the product of all the elements of nums
except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or
suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not
count as extra space for the purpose of space complexity analysis.)

'''

# ------------------------------------------------------------------------------
# Solutions
# ------------------------------------------------------------------------------

from typing import *
import functools
import unittest


class Solution:
    '''
    Time: O(n)
    Space: O(n)

    Input:  [4,5,1,8,2]
    Output: [80, 64, 320, 40, 160]

    n = [4  5  1   8  2]
    L = [1  4  20 20 160]
    R = [80  16 16  2 1]
    Result[i] = L[i] * R[i]
    '''
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        L = [1] * n
        R = [1] * n
        for i in range(1, n):
            L[i] = nums[i-1] * L[i-1]
        for i in range(n - 2, -1, -1):
            R[i] = nums[i+1] * R[i+1]
        result = [L[i] * R[i] for i in range(n)]
        return (result)


class Solution2:
    '''
    Time: O(n)
    Space: O(1)
    '''
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1]
        for i in range(1, n):
            ans = ans + [nums[i - 1] * ans[-1]]
        print(ans)
        R = 1
        for i in range(n - 2, -1, -1):
            R *= nums[i + 1]
            print(R)
            ans[i] *= R
        print(ans)
        return (ans)


# ------------------------------------------------------------------------------
# Tests
# ------------------------------------------------------------------------------

class TestSolution(unittest.TestCase):
    def test_simple(self):
        s = Solution()
        nums = [4, 5, 1, 8, 2, 10, 6]
        result = s.productExceptSelf(nums)
        self.assertEqual(result, [4800, 3840, 19200, 2400, 9600, 1920, 3200])

    def test_simple2(self):
        s = Solution()
        nums = [4, 5, 1, 8, 2]
        result = s.productExceptSelf(nums)
        self.assertEqual(result, [80, 64, 320, 40, 160])


class TestSolution2(unittest.TestCase):
    def test_simple2(self):
        s = Solution2()
        nums = [4, 5, 1, 8, 2]
        result = s.productExceptSelf(nums)
        self.assertEqual(result, [80, 64, 320, 40, 160])


unittest.main(verbosity=2)