MediumNo. 0713

Subarray Product Less Than K — LeetCode 713 Python Solution

Topics
Array, Binary Search, Prefix Sum, Sliding Window
Reading time
2 min

The 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

Input
nums = [10,5,2,6], k = 100
Output
8
Explanation
The 8 subarrays that have product less than 100 are:

Python solution

PythonSolution
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans = l = 0
        p = 1
        for r, x in enumerate(nums):
            p *= x
            while l <= r and p >= k:
                p //= nums[l]
                l += 1
            ans += r - l + 1
        return ans

Complexity

Time
O(n)where n is the length of the array
Space · auxiliary
O(1)

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 713. Subarray Product Less Than K is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 713. Subarray Product Less Than K?

LeetCode 713. Subarray Product Less Than K is rated Medium on LeetCode.

What is the time complexity of LeetCode 713. Subarray Product Less Than K?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 713. Subarray Product Less Than K?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 713. Subarray Product Less Than K cover?

LeetCode 713. Subarray Product Less Than K is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.