Jobs

Interviews

Discussions

Subarray Product Less Than K

#17 Most AskedMedium

Subarray Product Less Than K #17 Most Asked

Medium

SoFi

5 views

Topics:

ArraysSliding WindowsTwo Pointers

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⁶

Try coding it in LeetCode

Subarray Product Less Than K

#17 Most AskedMedium

Subarray Product Less Than K #17 Most Asked

Medium

SoFi

5 views

Topics:

ArraysSliding WindowsTwo Pointers

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⁶

Try coding it in LeetCode

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:

Are the elements in `nums` guaranteed to be positive integers?
Is `k` guaranteed to be a positive integer, and what is its potential range?
What should be returned if no subarrays satisfy the condition (i.e., the count is zero)?
Can the input array `nums` be empty?
Are there any constraints on the size of the input array `nums` or the magnitude of its elements?

Brute Force Solution

Approach

The brute force approach involves considering every possible contiguous group of numbers within the given collection. For each group, we calculate the product of its numbers and check if that product is less than the specified limit.

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

Take the very first number by itself and see if its value is less than the limit.
Then, consider the first two numbers together. Calculate their product and check if it's less than the limit.
Continue this by taking the first three numbers, then the first four, and so on, calculating the product each time and comparing it to the limit.
Once you've examined all possible groups starting from the very first number, shift your focus. Start by considering just the second number by itself, and check if its value is less than the limit.
Next, look at the second and third numbers together. Compute their product and see if it's under the limit.
Keep extending this group, taking the second through fourth numbers, then the second through fifth, and so on, always calculating the product and comparing it to the limit.
Repeat this process for every possible starting number in the collection, creating all possible contiguous groups and checking their products against the limit.
Count up all the groups whose number product was found to be less than the limit.

Code Implementation

def subarray_product_less_than_k_brute_force(product_numbers, limit_value):
    count_of_valid_subarrays = 0

    # Iterate through each possible starting number for a subarray.
    for starting_index in range(len(product_numbers)):
        current_product = 1
        # For each starting number, extend the subarray to the right.
        for ending_index in range(starting_index, len(product_numbers)):
            current_product *= product_numbers[ending_index]

            # If the product of the current subarray is less than the limit, increment our count.
            if current_product < limit_value:
                count_of_valid_subarrays += 1
            else:
                # If the product exceeds the limit, any further extension of this subarray will also exceed it.
                break

    return count_of_valid_subarrays

Big(O) Analysis

Time Complexity

O(n^2) – The described brute force approach involves iterating through all possible contiguous subarrays. The outer loop selects the starting element of a subarray, and the inner loop extends the subarray to the right, calculating the product at each step. If the input array has n elements, there are n choices for the starting element. For each starting element, the inner loop can run up to n times. This nested structure, where for each of the n potential starting points we perform up to n multiplications and comparisons, results in approximately n * n/2 operations. Therefore, the time complexity is O(n^2).

Space Complexity

O(1) – The provided brute force approach iterates through all possible subarrays and calculates their products. The only extra memory used consists of a few scalar variables to store the current product, loop indices, and the final count. These variables occupy a constant amount of memory, regardless of the input size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

This problem asks us to count how many groups of consecutive numbers have a product smaller than a given number. The clever approach involves a 'sliding window' to efficiently explore these groups without recalculating products from scratch.

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

Imagine you have a window that starts at the beginning of the number sequence.
As you expand the right side of the window, you keep track of the product of all the numbers currently inside the window.
If this product becomes too large (greater than or equal to the given number), you shrink the left side of the window until the product is small enough again.
Every time you successfully expand the window to the right without the product becoming too large, you've found new valid groups of numbers.
The trick is that when you add a new number to the right and the product is still valid, all the new consecutive groups ending with that new number are also valid.
You then add the count of these newly found valid groups to your total.
You continue this process, sliding and resizing the window across the entire sequence of numbers.
By doing this, you efficiently discover and count all the groups whose product is less than the target number.

Code Implementation

def count_subarray_product_less_than_k(numbers_list, target_product):
    count_of_valid_subarrays = 0
    current_window_product = 1
    left_window_boundary = 0

    for right_window_boundary in range(len(numbers_list)):
        current_window_product *= numbers_list[right_window_boundary]

        # Shrink the window from the left if the product exceeds the target.
        while current_window_product >= target_product and left_window_boundary <= right_window_boundary:
            current_window_product //= numbers_list[left_window_boundary]
            left_window_boundary += 1

        # All subarrays ending at the current right_window_boundary are valid.
        # The number of such subarrays is (right_window_boundary - left_window_boundary + 1).
        count_of_valid_subarrays += (right_window_boundary - left_window_boundary + 1)

    return count_of_valid_subarrays

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a sliding window approach where both the left and right pointers traverse the array at most once. The right pointer iterates through each of the n elements, expanding the window. The left pointer, in the worst case, also traverses the array once to shrink the window when the product exceeds k. Since each element is visited by both pointers a constant number of times, the total number of operations is directly proportional to the size of the input array n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The solution uses a constant amount of extra space. This is because it only requires a few variables to store the current product (e.g., 'current_product'), the left boundary of the sliding window (e.g., 'left'), and the total count of valid subarrays (e.g., 'count'). The size of the input array (N) does not affect the number of additional variables used by the algorithm. Therefore, the auxiliary space complexity remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Empty input array nums	An empty array should result in a count of 0, as no subarrays can be formed.
Input array with a single element	If the single element is less than k, it forms one valid subarray; otherwise, the count is 0.
k is 1 or less	Since nums contains positive integers, no subarray product can be less than or equal to 1, thus the count will always be 0.
All elements in nums are greater than or equal to k	In this scenario, no single-element subarray will satisfy the condition, and thus no larger subarrays will either, resulting in a count of 0.
Large input array nums leading to potential integer overflow	We must use a data type that can handle large products, or carefully manage the product calculation to avoid overflow, possibly by using logarithms if appropriate, or by ensuring intermediate products don't exceed the limits.
Input array with many identical values	The sliding window approach naturally handles repeated values by adjusting window boundaries, ensuring each contiguous subarray is considered correctly.
Input array with extremely large numbers	Similar to potential overflow, extremely large numbers might require specific handling for product calculation or comparison to prevent precision issues or overflow.
No subarrays satisfy the condition	The algorithm should correctly return 0 if no contiguous subarray has a product strictly less than k.

Empty input array nums

How to Handle:

An empty array should result in a count of 0, as no subarrays can be formed.

Input array with a single element

How to Handle:

If the single element is less than k, it forms one valid subarray; otherwise, the count is 0.

k is 1 or less

How to Handle:

Since nums contains positive integers, no subarray product can be less than or equal to 1, thus the count will always be 0.

All elements in nums are greater than or equal to k

How to Handle:

In this scenario, no single-element subarray will satisfy the condition, and thus no larger subarrays will either, resulting in a count of 0.

Large input array nums leading to potential integer overflow

How to Handle:

We must use a data type that can handle large products, or carefully manage the product calculation to avoid overflow, possibly by using logarithms if appropriate, or by ensuring intermediate products don't exceed the limits.

Input array with many identical values

How to Handle:

The sliding window approach naturally handles repeated values by adjusting window boundaries, ensuring each contiguous subarray is considered correctly.

Input array with extremely large numbers

How to Handle:

Similar to potential overflow, extremely large numbers might require specific handling for product calculation or comparison to prevent precision issues or overflow.

No subarrays satisfy the condition

How to Handle:

The algorithm should correctly return 0 if no contiguous subarray has a product strictly 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:

Are the elements in `nums` guaranteed to be positive integers?
Is `k` guaranteed to be a positive integer, and what is its potential range?
What should be returned if no subarrays satisfy the condition (i.e., the count is zero)?
Can the input array `nums` be empty?
Are there any constraints on the size of the input array `nums` or the magnitude of its elements?

Brute Force Solution

Approach

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

Take the very first number by itself and see if its value is less than the limit.
Then, consider the first two numbers together. Calculate their product and check if it's less than the limit.
Continue this by taking the first three numbers, then the first four, and so on, calculating the product each time and comparing it to the limit.
Once you've examined all possible groups starting from the very first number, shift your focus. Start by considering just the second number by itself, and check if its value is less than the limit.
Next, look at the second and third numbers together. Compute their product and see if it's under the limit.
Keep extending this group, taking the second through fourth numbers, then the second through fifth, and so on, always calculating the product and comparing it to the limit.
Repeat this process for every possible starting number in the collection, creating all possible contiguous groups and checking their products against the limit.
Count up all the groups whose number product was found to be less than the limit.

Code Implementation

def subarray_product_less_than_k_brute_force(product_numbers, limit_value):
    count_of_valid_subarrays = 0

    # Iterate through each possible starting number for a subarray.
    for starting_index in range(len(product_numbers)):
        current_product = 1
        # For each starting number, extend the subarray to the right.
        for ending_index in range(starting_index, len(product_numbers)):
            current_product *= product_numbers[ending_index]

            # If the product of the current subarray is less than the limit, increment our count.
            if current_product < limit_value:
                count_of_valid_subarrays += 1
            else:
                # If the product exceeds the limit, any further extension of this subarray will also exceed it.
                break

    return count_of_valid_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a window that starts at the beginning of the number sequence.
As you expand the right side of the window, you keep track of the product of all the numbers currently inside the window.
If this product becomes too large (greater than or equal to the given number), you shrink the left side of the window until the product is small enough again.
Every time you successfully expand the window to the right without the product becoming too large, you've found new valid groups of numbers.
The trick is that when you add a new number to the right and the product is still valid, all the new consecutive groups ending with that new number are also valid.
You then add the count of these newly found valid groups to your total.
You continue this process, sliding and resizing the window across the entire sequence of numbers.
By doing this, you efficiently discover and count all the groups whose product is less than the target number.

Code Implementation

def count_subarray_product_less_than_k(numbers_list, target_product):
    count_of_valid_subarrays = 0
    current_window_product = 1
    left_window_boundary = 0

    for right_window_boundary in range(len(numbers_list)):
        current_window_product *= numbers_list[right_window_boundary]

        # Shrink the window from the left if the product exceeds the target.
        while current_window_product >= target_product and left_window_boundary <= right_window_boundary:
            current_window_product //= numbers_list[left_window_boundary]
            left_window_boundary += 1

        # All subarrays ending at the current right_window_boundary are valid.
        # The number of such subarrays is (right_window_boundary - left_window_boundary + 1).
        count_of_valid_subarrays += (right_window_boundary - left_window_boundary + 1)

    return count_of_valid_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array nums	An empty array should result in a count of 0, as no subarrays can be formed.
Input array with a single element	If the single element is less than k, it forms one valid subarray; otherwise, the count is 0.
k is 1 or less	Since nums contains positive integers, no subarray product can be less than or equal to 1, thus the count will always be 0.
All elements in nums are greater than or equal to k	In this scenario, no single-element subarray will satisfy the condition, and thus no larger subarrays will either, resulting in a count of 0.
Large input array nums leading to potential integer overflow	We must use a data type that can handle large products, or carefully manage the product calculation to avoid overflow, possibly by using logarithms if appropriate, or by ensuring intermediate products don't exceed the limits.
Input array with many identical values	The sliding window approach naturally handles repeated values by adjusting window boundaries, ensuring each contiguous subarray is considered correctly.
Input array with extremely large numbers	Similar to potential overflow, extremely large numbers might require specific handling for product calculation or comparison to prevent precision issues or overflow.
No subarrays satisfy the condition	The algorithm should correctly return 0 if no contiguous subarray has a product strictly less than k.

Empty input array nums

How to Handle:

An empty array should result in a count of 0, as no subarrays can be formed.

Input array with a single element

How to Handle:

If the single element is less than k, it forms one valid subarray; otherwise, the count is 0.

k is 1 or less

How to Handle:

Since nums contains positive integers, no subarray product can be less than or equal to 1, thus the count will always be 0.

All elements in nums are greater than or equal to k

How to Handle:

In this scenario, no single-element subarray will satisfy the condition, and thus no larger subarrays will either, resulting in a count of 0.

Large input array nums leading to potential integer overflow

How to Handle:

Input array with many identical values

How to Handle:

The sliding window approach naturally handles repeated values by adjusting window boundaries, ensuring each contiguous subarray is considered correctly.

Input array with extremely large numbers

How to Handle:

Similar to potential overflow, extremely large numbers might require specific handling for product calculation or comparison to prevent precision issues or overflow.

No subarrays satisfy the condition

How to Handle:

The algorithm should correctly return 0 if no contiguous subarray has a product strictly less than k.

0/17 SoFi questions completed

0/17 completed