713. Subarray Product Less Than K
Subarray Product Less Than K (LeetCode 713) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Subarray Product Less Than K
Subarray Product Less Than K is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- For each j, let opt(j) be the smallest i so that nums[i] * nums[i+1] * ... * nums[j] is less than k. opt is an increasing function.
The reference solution runs in O(n) time and O(1) space.
The Subarray Product Less Than K solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Array, Binary Search, Sliding Window, Prefix Sum.
Reported in interviews at Bloomberg, Google, LinkedIn.
How to practise Subarray Product Less Than K on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Subarray Product Less Than K in the code editor, or read the Subarray Product Less Than K editorial for a worked solution with its approach and complexity analysis.
Where Subarray Product Less Than K sits in the DSA pattern sheet
Problems related to Subarray Product Less Than K
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Subarray Product Less Than K FAQ
What is the LeetCode number of Subarray Product Less Than K?
Subarray Product Less Than K is LeetCode problem 713, rated Medium.
What pattern is used to solve Subarray Product Less Than K?
Subarray Product Less Than K is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Subarray Product Less Than K?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Subarray Product Less Than K?
Subarray Product Less Than K has been reported in interviews at Bloomberg, Google, LinkedIn.