LeetCode 713 solution

problem

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

• Input: nums = [10,5,2,6], k = 100
• Output: 8
• Explanation: The 8 subarrays that have product less than 100 are:
  [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6] Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

• Input: nums = [1,2,3], k = 0
• Output: 0

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

python

result = []
n = len(nums)
for i in range(1, n + 1):
    for j in range(n - i + 1):
        if functools.reduce(operator.mul, nums[j : j + i]) < k:
            result.append(nums[j : j + i])
print(result)

처음에는 combination을 전부 낸 다음에 이것들에 대해서 k 이하의 product인 것들만 뽑아내는 것인 방식을 생각했었다. 그러나 이러한 방식은 단순하게 생각해봐도 nums.length가 매우 큰 경우에는 매우 비효율적일 것으로 보인다.

실제로 매우 큰 경우의 수에 대해서 이렇게 코드를 짰을 때는 TLE(time limit exceed)가 뜬다. 시간 복잡도가 O(n^2) 이기 때문이다. 시간 복잡도를 O(n)으로 줄일 필요가 있다.

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1: return 0
        prod = 1
        result = left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod /= nums[left]
                left += 1
            result += right - left + 1
        return result

이렇게 코드를 수정하면 이제 정확하게 코드가 잘 동작한다. 이 코드는 left와 right 두 개의 포인터를 사용하여 서브 배열의 시작과 끝을 표시한다. prod는 현재 서브 배열의 곱을 저장하고, result는 곱이 k보다 작은 서브 배열의 수를 저장한다. right 포인터가 리스트를 순회하면서 prod가 k보다 크거나 같아지면 left 포인터를 이동시켜 prod가 k보다 작아지도록 한다. 이 과정을 반복하면서 각 right 위치에서 가능한 서브 배열의 수를 result에 더한다.