grid47 Exploring patterns and algorithms
Aug 27, 2024
5 min read
Solution to LeetCode 713: Subarray Product Less Than K 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.
Problem
Approach
Steps
Complexity
Input: The input consists of an array `nums` of integers and an integer `k`.
Example: nums = [3, 4, 1, 2], k = 20
Constraints:
• 1 <= nums.length <= 3 * 10^4
• 1 <= nums[i] <= 1000
• 0 <= k <= 10^6
Output: Return the count of contiguous subarrays whose product of elements is strictly less than `k`.
Example: 6
Constraints:
• The result should be a non-negative integer representing the count of subarrays.
Goal: To efficiently calculate the number of contiguous subarrays with product less than `k`.
Steps:
• Use a sliding window technique to iterate through the array.
• Maintain a product variable to store the product of the current subarray.
• If the product exceeds `k`, move the left boundary of the window to reduce the product.
• For each valid window, the number of subarrays ending at the current position is added to the result.
Goal: The solution should handle the array size up to 30,000 and handle values within the given constraints.
Steps:
• The input array can contain up to 30,000 elements.
• Each element in the array is between 1 and 1000.
• The value of `k` is between 0 and 1,000,000.
Assumptions:
• The array contains positive integers and `k` is a non-negative integer.
• Input: nums = [3, 4, 1, 2], k = 20
• Explanation: The subarrays [3], [4], [1], [2], [3, 4], and [4, 1] have products less than 20, totaling 6 valid subarrays.
• Input: nums = [1, 1, 1], k = 5
• Explanation: All possible subarrays in this case have products less than 5, so the output is 6.
Approach: The problem can be solved efficiently using a sliding window technique to track the product of elements in subarrays.
Observations:
• Using a brute force approach by checking all possible subarrays would be too slow for large arrays.
• A sliding window approach can help reduce the time complexity.
• We will use a window where the product of the elements is maintained dynamically, updating it as the window slides over the array.
Steps:
• Initialize a variable to store the product of elements in the current window.
• Iterate through the array and maintain a right pointer to track the window's right boundary.
• When the product exceeds `k`, move the left pointer to reduce the product.
• Count all subarrays that end at the current right pointer and have a product less than `k`.
Empty Inputs:
• If the input array is empty, return 0.
Large Inputs:
• Ensure the solution works efficiently for large arrays, up to the size constraint of 30,000.
Special Values:
• If `k` is 0, the result should be 0 as no subarray can have a product less than 0.
Constraints:
• Handle cases where `k` is very large or very small relative to the elements in the array.
intnumSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k ==0) return0;
longlong prod =1;
int res =0, j =0;
for(int i =0; i < nums.size(); i++) {
prod *= nums[i];
while(prod >= k && j <= i) {
prod /= nums[j++];
}
res += (i - j +1);
}
return res;
}
1 : Function Declaration
intnumSubarrayProductLessThanK(vector<int>& nums, int k) {
Define the function 'numSubarrayProductLessThanK' which takes a vector of integers 'nums' and an integer 'k'.
2 : Edge Case Handling
if(k ==0) return0;
Handle the edge case where 'k' is 0, in which case no subarray product can be less than 0, thus return 0.
3 : Variable Initialization
longlong prod =1;
Initialize the product variable 'prod' to 1. This will hold the product of elements in the current subarray.
4 : Variable Initialization
int res =0, j =0;
Initialize 'res' to store the result (number of valid subarrays) and 'j' as the starting index of the sliding window.
5 : Loop
for(int i =0; i < nums.size(); i++) {
Loop through each element in the 'nums' array using the variable 'i' as the end index of the sliding window.
6 : Product Calculation
prod *= nums[i];
Multiply the current element 'nums[i]' with the running product 'prod'.
7 : Sliding Window Adjustment
Check and adjust the sliding window if the product exceeds 'k'.
8 : While Loop
while(prod >= k && j <= i) {
While the product exceeds or equals 'k', move the starting index 'j' to the right to reduce the product.
9 : Window Shrinking
prod /= nums[j++];
Divide the product by 'nums[j]' (the element at the starting index), and increment 'j' to shrink the window.
10 : Counting Valid Subarrays
res += (i - j +1);
For each valid subarray (where the product is less than 'k'), add the number of valid subarrays in the current window to 'res'.
11 : Return Statement
return res;
Return the total count of valid subarrays whose product is less than 'k'.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In the worst case, we process each element once while adjusting the window, making the time complexity linear.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses constant space, only requiring a few variables to maintain the window and the count.
