LeetCode 713: Subarray Product Less Than K Solution

Master LeetCode problem 713 (Subarray Product Less Than K), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

713. Subarray Product Less Than K

Medium

Array Binary Search Sliding Window Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach. We maintain a window that grows from left to right while the product of elements within the window is less than k. If the product exceeds k, we shrink the window from the left until the product is less than k again. At each step, we count the number of valid subarrays that can be formed with the current window.

Algorithm

Initialize variables count and prod to keep track of the count of valid subarrays and the product of elements in the window respectively.
Initialize left and right pointers to 0.
Iterate right from 0 to the length of the array:
- Update prod by multiplying it with nums[right].
- While prod is greater than or equal to k, divide prod by nums[left] and increment left to shrink the window.
- Add the count of valid subarrays to count (size of the current window).
Return the final count.

Time Complexity

The time complexity of this algorithm is O(n) where n is the length of the input array nums.

Space Complexity

The space complexity is O(1) as we are using only a constant amount of extra space.

Solution Code

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        
        int prod = 1, count = 0, left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 713 (Subarray Product Less Than K)?

This page provides optimized solutions for LeetCode problem 713 (Subarray Product Less Than K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 713 (Subarray Product Less Than K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 713 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 713 in Java, C++, or Python.

Back to LeetCode Solutions