algoadvance

Leetcode 713. Subarray Product Less Than K

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.

Clarifying Questions

1. What are the constraints on the input values?
   • The length of the array nums will be between 1 and 3 * 10^4.
   • Each element in nums will be between 1 and 1000.
   • k will be between 1 and 10^6.
2. Are there any specific edge cases to consider?
   • If k is less than or equal to 1, there can’t be any valid subarray since all elements in the array are at least 1. We should return 0 in such cases.
   • Single-element subarrays should also be considered, where the element itself should be less than k.

Strategy

To solve this problem efficiently, we can use a sliding window (or two-pointer) technique. Here’s the plan:

1. Initialize Pointers and Variables:
   • We need two pointers, left and right, to represent the current window of subarrays.
   • A variable product will keep track of the product of all elements in the current window.
2. Expand and Shrink Window:
   • Iterate the right pointer from the start to the end of the array.
   • For each right pointer position, multiply product by nums[right].
   • While product is greater than or equal to k, move the left pointer to the right and divide product by nums[left] to shrink the window.
   • All subarrays ending at right and starting from any position between left and right are valid subarrays. Thus, add right - left + 1 to the count of valid subarrays.
3. Counting Valid Subarrays:
   • This counts the number of valid subarrays and gives us the desired result.

Code

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

Time Complexity

• Time Complexity:
  • The algorithm processes each element of the array at most twice (once by the right pointer and at most once by the left pointer). Thus, the time complexity is O(n), where n is the length of the array.
• Space Complexity:
  • The space complexity is O(1) since we are using a constant amount of extra space regardless of the input size.

This approach ensures that we efficiently count all subarrays with a product less than k by leveraging the sliding window technique to keep the product of the current window in check.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?