Jobs

Interviews

Discussions

Subarray Product Less Than K

Medium

Apple

11 views

Topics:

ArraysSliding Windows

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 * 10⁴
1 <= nums[i] <= 1000
0 <= k <= 10⁶

Subarray Product Less Than K

Medium

Apple

11 views

Topics:

ArraysSliding Windows

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 * 10⁴
1 <= nums[i] <= 1000
0 <= k <= 10⁶

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array and the integer `k`? Can `k` ever be zero or negative?
Can the input array `nums` be empty or null?
Are all numbers in `nums` guaranteed to be positive, as the problem description states?
If no subarrays have a product less than `k`, what should I return?
How large can the input array `nums` be?

Brute Force Solution

Approach

The brute force method involves checking every possible group of numbers to see if their product is less than a target value. We'll look at all possible starting points and then consider groups of increasing size from each of those points.

Here's how the algorithm would work step-by-step:

Start with the first number in the list.
See if this single number is less than the target value.
Next, take the first and second numbers together, and multiply them. See if this product is less than the target value.
Then, take the first, second, and third numbers together, and multiply them. Check if the product is less than the target value.
Keep adding numbers to the group from the start, one at a time, and checking the product against the target.
Once you've gone through all the groups that start with the first number, move on to the second number.
Repeat the same process, checking the second number alone, then the second and third, then the second, third and fourth, and so on.
Continue this process, starting at each number in the list, until you've checked all possible groups.
Count all the groups of numbers whose product is less than the target value.

Code Implementation

def sub_array_product_less_than_k_brute_force(numbers, target):
    count = 0

    # Iterate through each starting index of the subarray
    for start_index in range(len(numbers)):
        current_product = 1

        # Iterate through each possible end index for the subarray
        for end_index in range(start_index, len(numbers)):
            current_product *= numbers[end_index]

            # Check if the current product is less than the target
            if current_product < target:
                count += 1

    return count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays. For an input array of size n, the outer loop iterates n times, representing the starting index of a subarray. The inner loop, in the worst case, iterates up to n times for each starting index, calculating the product of the subarray. Therefore, the algorithm performs approximately n * n/2 operations, leading to a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force algorithm does not use any auxiliary data structures like arrays, hash maps, or sets. It only uses a few variables to keep track of the current product, starting index, and ending index while iterating through subarrays. The number of these variables does not depend on the size of the input array (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

The fastest way to solve this is to use a 'sliding window' technique. We expand a range of numbers until their product is too big, then shrink it back down until it's small enough again. By keeping track of the size of these valid ranges, we can count all the subarrays quickly.

Here's how the algorithm would work step-by-step:

Start with an empty range of numbers from the list.
Gradually add numbers to the right end of the range, and multiply them together to keep a running product.
If the running product becomes too big (greater than or equal to the target value), start removing numbers from the left end of the range until the product is small enough again.
Every time the range is valid (product is less than the target), calculate how many subarrays are in that range and add that to our total count. A valid range of size 'n' contains 'n' subarrays that meet the product criteria.
Continue moving the right end of the range through the list of numbers, expanding and shrinking the range as needed.
The final count is the total number of subarrays whose product is less than the target value.

Code Implementation

def subArrayProductLessThanK(numbers, target):
    if target <= 1:
        return 0

    left_index = 0
    current_product = 1
    sub_array_count = 0

    for right_index, number in enumerate(numbers):
        current_product *= number

        # Shrink the window if product too large
        while current_product >= target:
            current_product /= numbers[left_index]
            left_index += 1

            # Maintain window invariant

        # Add the number of valid subarrays ending at right_index.
        sub_array_count += right_index - left_index + 1

    return sub_array_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The solution uses a sliding window approach where we iterate through the input array of size n with a right pointer. While the right pointer always moves forward, the left pointer only moves forward to reduce the product when it exceeds k. In the worst case, the left pointer might move forward as many times as the right pointer, resulting in at most 2n operations. Therefore, the time complexity is O(n) since the number of operations is proportional to the input size n.

Space Complexity

O(1) – The sliding window algorithm described uses a constant amount of extra space. It primarily uses variables to store the left and right boundaries of the window and the running product. These variables require a fixed amount of memory regardless of the size N of the input array. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately because there are no subarrays to evaluate.
k is less than or equal to 0	Return 0 immediately since product of positive numbers is always positive and therefore never less than a non-positive k.
Array contains a single element and k is greater than the element	Return 1, as the single element subarray satisfies the condition.
Array contains a single element and k is less than or equal to the element	Return 0, as the single element subarray does not satisfy the condition.
Array contains all 1s and k is greater than 1	The number of subarrays is n*(n+1)/2 where n is array length.
Array contains very large numbers such that product easily overflows	Use long data type to prevent integer overflow during product calculation.
k is a very large number, close to the maximum value that integer can hold.	The sliding window might expand until integer overflow or memory exhaustion occurs, necessitating long data type use.
All numbers in array are greater than or equal to k	Return 0, as no subarray will have a product less than k.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array and the integer `k`? Can `k` ever be zero or negative?
Can the input array `nums` be empty or null?
Are all numbers in `nums` guaranteed to be positive, as the problem description states?
If no subarrays have a product less than `k`, what should I return?
How large can the input array `nums` be?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the list.
See if this single number is less than the target value.
Next, take the first and second numbers together, and multiply them. See if this product is less than the target value.
Then, take the first, second, and third numbers together, and multiply them. Check if the product is less than the target value.
Keep adding numbers to the group from the start, one at a time, and checking the product against the target.
Once you've gone through all the groups that start with the first number, move on to the second number.
Repeat the same process, checking the second number alone, then the second and third, then the second, third and fourth, and so on.
Continue this process, starting at each number in the list, until you've checked all possible groups.
Count all the groups of numbers whose product is less than the target value.

Code Implementation

def sub_array_product_less_than_k_brute_force(numbers, target):
    count = 0

    # Iterate through each starting index of the subarray
    for start_index in range(len(numbers)):
        current_product = 1

        # Iterate through each possible end index for the subarray
        for end_index in range(start_index, len(numbers)):
            current_product *= numbers[end_index]

            # Check if the current product is less than the target
            if current_product < target:
                count += 1

    return count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty range of numbers from the list.
Gradually add numbers to the right end of the range, and multiply them together to keep a running product.
If the running product becomes too big (greater than or equal to the target value), start removing numbers from the left end of the range until the product is small enough again.
Every time the range is valid (product is less than the target), calculate how many subarrays are in that range and add that to our total count. A valid range of size 'n' contains 'n' subarrays that meet the product criteria.
Continue moving the right end of the range through the list of numbers, expanding and shrinking the range as needed.
The final count is the total number of subarrays whose product is less than the target value.

Code Implementation

def subArrayProductLessThanK(numbers, target):
    if target <= 1:
        return 0

    left_index = 0
    current_product = 1
    sub_array_count = 0

    for right_index, number in enumerate(numbers):
        current_product *= number

        # Shrink the window if product too large
        while current_product >= target:
            current_product /= numbers[left_index]
            left_index += 1

            # Maintain window invariant

        # Add the number of valid subarrays ending at right_index.
        sub_array_count += right_index - left_index + 1

    return sub_array_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately because there are no subarrays to evaluate.
k is less than or equal to 0	Return 0 immediately since product of positive numbers is always positive and therefore never less than a non-positive k.
Array contains a single element and k is greater than the element	Return 1, as the single element subarray satisfies the condition.
Array contains a single element and k is less than or equal to the element	Return 0, as the single element subarray does not satisfy the condition.
Array contains all 1s and k is greater than 1	The number of subarrays is n*(n+1)/2 where n is array length.
Array contains very large numbers such that product easily overflows	Use long data type to prevent integer overflow during product calculation.
k is a very large number, close to the maximum value that integer can hold.	The sliding window might expand until integer overflow or memory exhaustion occurs, necessitating long data type use.
All numbers in array are greater than or equal to k	Return 0, as no subarray will have a product less than k.