MediumNo. 0713
Subarray Product Less Than K — LeetCode 713 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Binary Search, Prefix Sum, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
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
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 ansComplexity
- 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
| No. | Problem | Difficulty |
|---|---|---|
| 0209 | Minimum Size Subarray Sum | Medium |
| 0862 | Shortest Subarray with Sum at Least K | Hard |
| 1004 | Max Consecutive Ones III | Medium |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard |
| 2302 | Count Subarrays With Score Less Than K | Hard |
| 2398 | Maximum Number of Robots Within Budget | Hard |
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.