Bounded Subarray Length — Problem Statement & Solution Guide

ArraysMediumSliding Window

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Use a sliding window with two pointers, maintaining the product incrementally; expand right, divide out left when product > threshold, updating the answer – O(n) time.

TopicArrays

PatternSliding Window

TimeO(n)

SpaceO(1)

Problem Description

You are given an array of positive integers values and a positive integer threshold. Determine the greatest possible length of a contiguous sub‑array whose elements’ product does not exceed threshold. If the array is empty or every sub‑array has a product larger than threshold, return 0. The solution must run in linear time relative to the size of values.

DSA Pattern Breakdown

"Bounded Subarray Length"

medium

WHY DOES IT MATTER?

Sliding‑window transforms a seemingly quadratic sub‑array search into a linear scan by exploiting the monotonic nature of the product when extending or shrinking a contiguous segment.

OPTIMIZATION CHALLENGE

The key insight is that the product of a window can be updated in O(1) when moving pointers: multiply by the incoming element, divide by the outgoing element. This eliminates the need to recompute the product from scratch for each window.

REAL-WORLD CONNECTION

Think of a network bandwidth throttler that permits a burst of traffic as long as the cumulative data transferred stays under a quota; the throttler expands the burst window until the quota is hit, then slides the window forward, discarding old packets—mirroring the two‑pointer product window.

During an interview, write the division step carefully and guard against division by zero; using a 64‑bit integer or double helps avoid overflow, and resetting the window after a zero simplifies the logic.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the maximum length of a contiguous sub‑array whose product stays ≤ threshold. A naïve solution enumerates every possible sub‑array, computes its product, and tracks the longest valid one. This requires O(n²) time because each of the O(n²) windows must be examined, which quickly becomes infeasible for n up to 10⁵ or larger. Moreover, repeated multiplication can overflow even 64‑bit integers, so careful handling is needed. The optimal paradigm is the sliding‑window (two‑pointer) technique applied to multiplicative constraints. By maintaining a window [left,right] and the product of its elements, we can expand right while the product ≤ threshold; when it exceeds, we shrink from the left, dividing out values[left] until the constraint is restored. Because each element enters and leaves the window at most once, the overall runtime is linear, O(n), and only O(1) extra space is required.

Interview Questions on This Problem

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

A zero forces any product that includes it to be zero, which is always ≤ threshold (assuming threshold ≥ 0). Treat zero as a reset point: whenever you encounter a zero, set left = right+1 and product = 1, then continue expanding the window after the zero.

Q2Can you modify the algorithm to return the actual sub‑array indices instead of just the length?

Yes. Keep track of the best window’s left and right indices whenever you update the maximum length. After the scan, return those indices (or the slice) alongside the length.

Q3What changes are needed if the constraint becomes a sum ≤ threshold instead of a product?

The same sliding‑window pattern works, but you add values[right] to a running sum and subtract values[left] when shrinking. Since addition is monotonic, the window adjustment logic is identical, yielding O(n) time.

Examples

Example 1

Input

{"values":[2,3,5,7],"threshold":30}

Output

Explanation: Start with the leftmost element and expand the window while the product stays ≤30. The window [2,3,5] has product 2·3·5=30 and length 3. Extending to include 7 makes the product 210>30, so the window contracts from the left, but any further window is shorter. No longer valid window exists, thus the answer is 3.

Example 2

Input

{"values":[10,5,2,6],"threshold":100}

Output

Explanation: Window expansion yields products: [10]=10, [10,5]=50, [10,5,2]=100 (length 3). Adding 6 makes the product 600>100, so the leftmost element (10) is removed, product becomes 60 for window [5,2,6] (length 3). All other windows are length 2 or less, so the maximum length is 3.

Example 3

Input

{"values":[11,13,17],"threshold":10}

Output

Explanation: The smallest element is 11, which already exceeds the threshold. Consequently every possible sub‑array has a product >10, so the required length is 0.

Constraints

1 <= values.length <= 100000
1 <= values[i] <= 10^9
1 <= threshold <= 10^18

Optimal Approach & Strategy

Use a sliding window with two pointers, maintaining the product incrementally; expand right, divide out left when product > threshold, updating the answer – O(n) time.

Brute Force Approach

Check every possible start index, compute the product for each end index until it exceeds the threshold, and record the longest valid length – O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function boundedSubarrayLength(values, threshold) {
    if (!values || values.length === 0 || threshold < 1) {
        return 0;
    }

    let product = 1;
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < values.length; right++) {
        product *= values[right];

        while (product > threshold && left <= right) {
            product /= values[left];
            left++;
        }

        if (product <= threshold) {
            maxLength = Math.max(maxLength, right - left + 1);
        }
    }

    return maxLength;
}

// Example usage
const values = [2, 3, 5, 7];
const threshold = 30;
console.log(boundedSubarrayLength(values, threshold));

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int boundedSubarrayLength(const vector<int>& values, int threshold) {
    if (values.empty() || threshold < 1) {
        return 0;
    }

    long long product = 1;
    int left = 0;
    int maxLength = 0;

    for (int right = 0; right < values.size(); ++right) {
        product *= values[right];

        while (product > threshold && left <= right) {
            product /= values[left];
            ++left;
        }

        if (product <= threshold) {
            maxLength = max(maxLength, right - left + 1);
        }
    }

    return maxLength;
}

int main() {
    vector<int> values = {2, 3, 5, 7};
    int threshold = 30;
    cout << boundedSubarrayLength(values, threshold) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int boundedSubarrayLength(int[] values, int threshold) {
        if (values == null || values.length == 0 || threshold < 1) {
            return 0;
        }

        long product = 1;
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < values.length; right++) {
            product *= values[right];

            while (product > threshold && left <= right) {
                product /= values[left];
                left++;
            }

            if (product <= threshold) {
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] values = {2, 3, 5, 7};
        int threshold = 30;
        System.out.println(boundedSubarrayLength(values, threshold));
    }
}

def bounded_subarray_length(values, threshold):
    if not values or threshold < 1:
        return 0

    product = 1
    left = 0
    max_length = 0

    for right in range(len(values)):
        product *= values[right]

        while product > threshold and left <= right:
            product //= values[left]
            left += 1

        if product <= threshold:
            max_length = max(max_length, right - left + 1)

    return max_length

# Example usage
if __name__ == "__main__":
    values = [2, 3, 5, 7]
    threshold = 30
    print(bounded_subarray_length(values, threshold))

function boundedSubarrayLength(values, threshold) {
    if (!values || values.length === 0 || threshold < 1) {
        return 0;
    }

    let product = 1;
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < values.length; right++) {
        product *= values[right];

        while (product > threshold && left <= right) {
            product /= values[left];
            left++;
        }

        if (product <= threshold) {
            maxLength = Math.max(maxLength, right - left + 1);
        }
    }

    return maxLength;
}

// Example usage
const values = [2, 3, 5, 7];
const threshold = 30;
console.log(boundedSubarrayLength(values, threshold));

Asked in Top Tech Interviews

Flipkart

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.