Subarray Product Validator — Problem Statement & Solution Guide

Two PointersMediumSliding Window

TimeO(N)

SpaceO(1)

Problem Description

You are provided with an array nums consisting of positive integers and a positive integer K. Your objective is to compute the total number of contiguous subarrays where the product of all elements within the subarray is strictly less than K.

A contiguous subarray is defined as a sequence of consecutive elements from the original array. For instance, in the array [2, 3, 4], the subarray [2, 3] is valid, but [2, 4] is not, as the elements are not adjacent.

The input consists of the array nums and the integer K. The output must be a single integer representing the count of all subarrays that satisfy the product condition. Note that the product of an empty subarray is not considered, and all elements in nums are strictly positive.

DSA Pattern Breakdown

"Subarray Product Validator"

medium

WHY DOES IT MATTER?

The sliding window (two‑pointer) pattern is essential for problems that require counting or evaluating contiguous segments under a monotonic constraint. It converts quadratic enumeration into linear traversal, which is a cornerstone technique for high‑throughput interview problems.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that with all positive integers, the product only grows when the right pointer moves right and only shrinks when the left pointer moves right, enabling us to maintain a valid window in O(1) amortized time per element.

REAL-WORLD CONNECTION

Think of a network traffic monitor that tracks the total data transmitted over a moving time window. As new packets arrive, the monitor adds their size; if the total exceeds a quota, it slides the window forward, discarding older packets—mirroring the product‑based sliding window in this problem.

During an interview, keep a running product variable and update it incrementally; never recompute the product from scratch when moving the left pointer—this small detail prevents hidden O(N^2) behavior.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the count of contiguous subarrays whose product is strictly less than a given threshold K. A naive solution would enumerate every possible subarray, compute its product, and compare it to K, resulting in O(N^2) time for an array of length N. This quickly becomes infeasible for N up to 10^5 because the number of subarrays grows quadratically and the product can overflow typical integer ranges, requiring careful handling.

The optimal solution leverages the sliding window (two‑pointer) technique. Because all numbers are positive, the product of a window expands monotonically when we extend the right pointer and shrinks monotonically when we move the left pointer. By maintaining a window [left, right] whose product stays below K, we can count all subarrays ending at right in O(1) time: they are exactly (right‑left+1). When the product reaches or exceeds K, we increment left until the invariant (product < K) is restored. This yields a linear O(N) algorithm with O(1) extra space.

The key insight is that positivity guarantees the product behaves like a cumulative sum in the classic "subarray sum < K" problem, allowing us to slide the window without missing any valid subarrays. This transforms an otherwise combinatorial enumeration into a single pass over the array.

Interview Questions on This Problem

Q1How would you modify the sliding window solution if the array could contain zeros?

Zeros reset the product to zero, which is always < K (assuming K > 0). When a zero is encountered, we can treat it as a window break: set product = 1, move left = right + 1, and continue counting subarrays starting after the zero. The overall algorithm remains O(N).

Q2Can you adapt this algorithm to count subarrays with product <= K instead of < K?

Yes. Change the while condition from product >= K to product > K, and adjust the counting formula accordingly. The rest of the sliding window logic stays identical.

Q3What would be the impact on time complexity if the numbers could be negative?

With negative numbers the product no longer has monotonic behavior; extending the window can flip the sign and magnitude unpredictably, breaking the two‑pointer invariant. In that case, the sliding window no longer works, and we would need a more complex approach (e.g., using prefix products and a balanced BST) which typically runs in O(N log N).

Examples

Example 1

Input

nums = [2, 3, 4], K = 6

Output

Explanation: We evaluate all contiguous subarrays: 1. [2]: Product = 2 < 6 (Valid) 2. [3]: Product = 3 < 6 (Valid) 3. [4]: Product = 4 < 6 (Valid) 4. [2, 3]: Product = 6 (Not strictly less than 6, Invalid) 5. [3, 4]: Product = 12 (Invalid) 6. [2, 3, 4]: Product = 24 (Invalid) Total valid subarrays: 3.

Example 2

Input

nums = [1, 2, 3], K = 10

Output

Explanation: We evaluate all contiguous subarrays: 1. [1]: Product = 1 < 10 (Valid) 2. [2]: Product = 2 < 10 (Valid) 3. [3]: Product = 3 < 10 (Valid) 4. [1, 2]: Product = 2 < 10 (Valid) 5. [2, 3]: Product = 6 < 10 (Valid) 6. [1, 2, 3]: Product = 6 < 10 (Valid) Total valid subarrays: 6.

Example 3

Input

nums = [5, 5, 5], K = 25

Output

Explanation: We evaluate all contiguous subarrays: 1. [5]: Product = 5 < 25 (Valid) 2. [5]: Product = 5 < 25 (Valid) 3. [5]: Product = 5 < 25 (Valid) 4. [5, 5]: Product = 25 (Not strictly less than 25, Invalid) 5. [5, 5]: Product = 25 (Invalid) 6. [5, 5, 5]: Product = 125 (Invalid) Total valid subarrays: 3.

Example 4

Input

nums = [1, 1, 1, 1], K = 2

Output

Explanation: Since all elements are 1, the product of any subarray is 1, which is strictly less than 2. Total subarrays in an array of length 4 is n*(n+1)/2 = 4*5/2 = 10. All 10 subarrays are valid.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
1 <= K <= 10^9

Optimal Approach & Strategy

Use a sliding window with two pointers, maintaining the product of the current window. Expand the right pointer, shrink the left pointer while the product >= K, and add (right‑left+1) to the answer for each right position. This runs in O(N) time and O(1) space.

Brute Force Approach

Enumerate every possible subarray, compute its product, and increment a counter if the product is less than K. This requires O(N^2) time and O(1) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

/**
 * @param {number[]} nums
 * @param {number} K
 * @return {number}
 */
function countSubarrays(nums, K) {
    if (K <= 1) return 0;
    let prod = 1;
    let left = 0;
    let result = 0;
    for (let right = 0; right < nums.length; ++right) {
        prod *= nums[right];
        while (prod >= K && left <= right) {
            prod /= nums[left];
            left++;
        }
        result += right - left + 1;
    }
    return result;
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long K) {
        if (K <= 1) return 0;
        long long prod = 1;
        long long result = 0;
        int left = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            prod *= nums[right];
            while (prod >= K && left <= right) {
                prod /= nums[left];
                ++left;
            }
            result += right - left + 1;
        }
        return result;
    }
};

class Solution {
    public long countSubarrays(int[] nums, long K) {
        if (K <= 1) return 0;
        long prod = 1;
        long result = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= K && left <= right) {
                prod /= nums[left];
                left++;
            }
            result += right - left + 1;
        }
        return result;
    }
}

from typing import List

def count_subarrays(nums: List[int], K: int) -> int:
    if K <= 1:
        return 0
    prod = 1
    left = 0
    result = 0
    for right, val in enumerate(nums):
        prod *= val
        while prod >= K and left <= right:
            prod //= nums[left]
            left += 1
        result += right - left + 1
    return result

/**
 * @param {number[]} nums
 * @param {number} K
 * @return {number}
 */
function countSubarrays(nums, K) {
    if (K <= 1) return 0;
    let prod = 1;
    let left = 0;
    let result = 0;
    for (let right = 0; right < nums.length; ++right) {
        prod *= nums[right];
        while (prod >= K && left <= right) {
            prod /= nums[left];
            left++;
        }
        result += right - left + 1;
    }
    return result;
}

Asked in Top Tech Interviews

Salesforce

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Subarray Product Validator Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Subarray Product Validator — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor