DSA-032 · Positive-factor window with a division guard

Subarray Product Less Than K

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 7663 deterministic checks. Learner drafts are not executed.

Understand the problem

Count nonempty contiguous subarrays whose mathematical product is strictly less than k, without overflowing during multiplication.

nums is non-null with 0–100,000 strictly positive int factors, each 1..Integer.MAX_VALUE. Both methods throw IllegalArgumentException for zero or negative factors, even when k≤1. Preserve the array.
k is any signed long. Products are positive, so return 0 when k≤1. For k>1 count all qualifying nonempty ranges, including overlapping ranges and ranges of ones.
Return a long count, at most n(n+1)/2=5000050000 for n=100000. The optimized product is always exact and below k after each completed iteration. Check a division threshold before multiplying; do not assume a long multiplication cannot overflow.

Examples

Input: nums=[10,5,2,6], k=100
Output: 8
The four singles plus [10,5], [5,2], [2,6], and [5,2,6] qualify; [10,5,2] equals the strict threshold and fails.
Input: nums=[1,1,1], k=2
Output: 6
Every nonempty interval has product one, so all six count.

Before you start

Array positions versus prefix boundaries and half-open intervals
Long arithmetic, frequency maps, and invariant reasoning

Recognize the structure

With positive integer factors, extending a range never lowers its product and removing a left factor never raises it. After finding the earliest valid start for each right endpoint, every later start is another valid suffix. Exact arithmetic is essential: overflow can reverse the threshold comparison.

Try before revealing

Hint 1

For one right endpoint, which starts produce valid suffixes?

Hint 2

How can product*x<k be checked without multiplying?

Hint 3

Shrink while product>(k-1)/x, multiply safely, and add right-left+1.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate products with BigInteger

For each start, multiply factors in BigInteger, count products below k, and stop at the first product≥k because later positive-integer factors cannot lower it. For [2,3],k=6, [2] and [3] qualify but [2,3] equals six and does not. This uses O(n²) arithmetic operations without relying on machine-product overflow behavior.

Improve the baseline

Handle impossible thresholds and barriers

Validate all factors first. For k≤1 no positive product qualifies. For k>1, a factor≥k makes every interval ending there invalid, so reset left=right+1 and product=1.

Make multiplication safe in advance

For a factor x<k, the desired product*x≤k-1 is equivalent to product≤floor((k-1)/x). Divide old left factors out while product exceeds this limit, then multiply. Since x<k, the limit is at least one, so even an empty previous window can satisfy it.

Count suffixes once

After including right, [left,right] is valid and every suffix beginning at left..right is valid. Add right-left+1; these are exactly the newly counted intervals with this ending position.

Why it is correct

Exact product invariant

Before processing right, product is the exact product of the previous retained interval [left,right), with the empty-product identity one. Dividing by a removed factor is exact because that factor belongs to this product.

Threshold and earliest start

For x<k, the division guard is mathematically equivalent to the strict product bound and guarantees the subsequent multiplication fits long. Each removed start is invalid with x and stays invalid for all future extensions. A barrier x≥k invalidates all starts through right. Thus left is the earliest possible valid start after each iteration.

Counting and termination

Removing factors≥1 cannot increase product, so all right-left+1 suffixes qualify and no earlier start does. Each interval has exactly one right endpoint, preventing duplicates. Both boundaries move forward at most n times, even when divisions by one do not change the product.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.math.BigInteger;
public final class Solution {
    private static void validate(int[] nums) {
        for (int value : nums) if (value <= 0) throw new IllegalArgumentException("positive factors required");
    }
    public static long numSubarrayProductLessThanK(int[] nums, long k) {
        validate(nums);
        if (k <= 1) return 0;
        int left = 0;
        long product = 1, count = 0;
        for (int right = 0; right < nums.length; right++) {
            int factor = nums[right];
            if (factor >= k) { left = right + 1; product = 1; continue; }
            long limit = (k - 1) / factor;
            while (product > limit) product /= nums[left++];
            product *= factor;
            count += right - left + 1;
        }
        return count;
    }
    public static long baseline(int[] nums, long k) {
        validate(nums);
        if (k <= 1) return 0;
        long count = 0;
        BigInteger threshold = BigInteger.valueOf(k);
        for (int start = 0; start < nums.length; start++) {
            BigInteger product = BigInteger.ONE;
            for (int end = start; end < nums.length; end++) {
                product = product.multiply(BigInteger.valueOf(nums[end]));
                if (product.compareTo(threshold) >= 0) break;
                count++;
            }
        }
        return count;
    }
}

Read the meaningful blocks

Compute k-1 only after k>1

This avoids underflow for Long.MIN_VALUE and makes the division threshold meaningful.

Reset before dividing a barrier

A single factor≥k cannot be repaired by removing earlier factors. Reset the empty-product state and count nothing for that endpoint.

Guard, then multiply

Multiplying first and checking afterward can already have lost information. The guard ensures product*factor≤k-1≤Long.MAX_VALUE-1.

Complexity

O(n) time including validation and amortized left removals; O(1) auxiliary space. Count uses long even though both pointers fit int.

The baseline uses O(n²) BigInteger multiplications/comparisons and O(1) simultaneously live product objects. For k>1 it stops at the first invalid product, so a multiplied candidate has fewer than 95 bits under the long-threshold/int-factor bounds. This is not an unbounded-product complexity claim.

Exact-state walkthroughs

Reveal normal and boundary traces

Shrink before multiplying, then count valid suffixes

Input: {"nums":[10,5,2,6],"k":100} · Result: 8

Step 1 of 11: Validate positive factors and resolve thresholds at most one.

The empty-product identity is one. Every nonempty product is positive.

Positive factors — incoming factor enters after the guard

0: 10
1: 5
2: 2
3: 6

State after this step
Variable	Value
values	`[10,5,2,6]`
left	`0`
right	`-1`
product	`1`
count	`0`
k	`100`

See the affected Java block

 1 import java.math.BigInteger;
 2 public final class Solution {
 3     private static void validate(int[] nums) {
 4         for (int value : nums) if (value <= 0) throw new IllegalArgumentException("positive factors required");
 5     }
 6     public static long numSubarrayProductLessThanK(int[] nums, long k) {
 7         validate(nums);
 8         if (k <= 1) return 0;
 9         int left = 0;
10         long product = 1, count = 0;
11         for (int right = 0; right < nums.length; right++) {
12             int factor = nums[right];
13             if (factor >= k) { left = right + 1; product = 1; continue; }
14             long limit = (k - 1) / factor;
15             while (product > limit) product /= nums[left++];
16             product *= factor;
17             count += right - left + 1;
18         }
19         return count;
20     }
21     public static long baseline(int[] nums, long k) {
22         validate(nums);
23         if (k <= 1) return 0;
24         long count = 0;
25         BigInteger threshold = BigInteger.valueOf(k);
26         for (int start = 0; start < nums.length; start++) {
27             BigInteger product = BigInteger.ONE;
28             for (int end = start; end < nums.length; end++) {
29                 product = product.multiply(BigInteger.valueOf(nums[end]));
30                 if (product.compareTo(threshold) >= 0) break;
31                 count++;
32             }
33         }
34         return count;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate positive factors and resolve thresholds at most one.
The empty-product identity is one. Every nonempty product is positive.
values
[10,5,2,6]
left
0
right
-1
product
1
count
0
k
100
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[10,5,2,6]
left
0
right
0
product
1
count
0
k
100
factor
10
limit
9
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[10,5,2,6]
left
0
right
0
product
10
count
1
k
100
factor
10
limit
9
added
1
phase
"count"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[10,5,2,6]
left
0
right
1
product
10
count
1
k
100
factor
5
limit
19
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[10,5,2,6]
left
0
right
1
product
50
count
3
k
100
factor
5
limit
19
added
2
phase
"count"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[10,5,2,6]
left
0
right
2
product
50
count
3
k
100
factor
2
limit
49
phase
"guard"
Divide out one old factor before including the new one.
Division is exact, and only an invalid starting boundary is discarded. Factors equal to one may leave product unchanged while left still advances.
values
[10,5,2,6]
left
1
right
2
product
5
count
3
k
100
factor
2
limit
49
outgoing
10
phase
"shrink"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[10,5,2,6]
left
1
right
2
product
10
count
5
k
100
factor
2
limit
49
added
2
phase
"count"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[10,5,2,6]
left
1
right
3
product
10
count
5
k
100
factor
6
limit
16
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[10,5,2,6]
left
1
right
3
product
60
count
8
k
100
factor
6
limit
16
added
3
phase
"count"
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
8

Reset at a factor too large for the threshold

Input: {"nums":[1,1,100,2,3],"k":10} · Result: 6

Step 1 of 11: Validate positive factors and resolve thresholds at most one.

The empty-product identity is one. Every nonempty product is positive.

Positive factors — incoming factor enters after the guard

0: 1
1: 1
2: 100
3: 2
4: 3

State after this step
Variable	Value
values	`[1,1,100,2,3]`
left	`0`
right	`-1`
product	`1`
count	`0`
k	`10`

See the affected Java block

 1 import java.math.BigInteger;
 2 public final class Solution {
 3     private static void validate(int[] nums) {
 4         for (int value : nums) if (value <= 0) throw new IllegalArgumentException("positive factors required");
 5     }
 6     public static long numSubarrayProductLessThanK(int[] nums, long k) {
 7         validate(nums);
 8         if (k <= 1) return 0;
 9         int left = 0;
10         long product = 1, count = 0;
11         for (int right = 0; right < nums.length; right++) {
12             int factor = nums[right];
13             if (factor >= k) { left = right + 1; product = 1; continue; }
14             long limit = (k - 1) / factor;
15             while (product > limit) product /= nums[left++];
16             product *= factor;
17             count += right - left + 1;
18         }
19         return count;
20     }
21     public static long baseline(int[] nums, long k) {
22         validate(nums);
23         if (k <= 1) return 0;
24         long count = 0;
25         BigInteger threshold = BigInteger.valueOf(k);
26         for (int start = 0; start < nums.length; start++) {
27             BigInteger product = BigInteger.ONE;
28             for (int end = start; end < nums.length; end++) {
29                 product = product.multiply(BigInteger.valueOf(nums[end]));
30                 if (product.compareTo(threshold) >= 0) break;
31                 count++;
32             }
33         }
34         return count;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate positive factors and resolve thresholds at most one.
The empty-product identity is one. Every nonempty product is positive.
values
[1,1,100,2,3]
left
0
right
-1
product
1
count
0
k
10
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[1,1,100,2,3]
left
0
right
0
product
1
count
0
k
10
factor
1
limit
9
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[1,1,100,2,3]
left
0
right
0
product
1
count
1
k
10
factor
1
limit
9
added
1
phase
"count"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[1,1,100,2,3]
left
0
right
1
product
1
count
1
k
10
factor
1
limit
9
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[1,1,100,2,3]
left
0
right
1
product
1
count
3
k
10
factor
1
limit
9
added
2
phase
"count"
Reset after a barrier factor.
Every interval ending at this factor is invalid. The retained interval becomes empty.
values
[1,1,100,2,3]
left
3
right
2
product
1
count
3
k
10
factor
100
added
0
phase
"barrier"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[1,1,100,2,3]
left
3
right
3
product
1
count
3
k
10
factor
2
limit
4
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[1,1,100,2,3]
left
3
right
3
product
2
count
4
k
10
factor
2
limit
4
added
1
phase
"count"
Compute a threshold before any multiplication.
product currently describes [left,right), excluding the incoming factor. A product at most limit can be multiplied safely.
values
[1,1,100,2,3]
left
3
right
4
product
2
count
4
k
10
factor
3
limit
3
phase
"guard"
Multiply safely and count every valid ending suffix.
The exact product is below k. Every start from left through right qualifies, and earlier starts do not.
values
[1,1,100,2,3]
left
3
right
4
product
6
count
6
k
10
factor
3
limit
3
added
2
phase
"count"
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
6

Test the contract

Input: nums=[], k=10
Output: 0
No nonempty interval.
Input: nums=[1,2], k=1
Output: 0
Strictly positive products cannot be below one.
Input: nums=[100,2,3], k=10
Output: 3
The barrier splits the sequence; [2], [3], [2,3] qualify.
Input: nums=[0,1], k=0
Output: IllegalArgumentException
Validation precedes the low-threshold shortcut.

Common mistakes and counterexamples

Multiply in long before checking

Counterexample: For [2147483647,2147483647,3] and k=Long.MAX_VALUE, the third combined product exceeds long range.

Shrink using floor((k-1)/factor) before multiplication.

Count only one valid interval per endpoint

Counterexample: For [1,1],k=2, the second endpoint owns both [1] and [1,1].

Add the number of valid suffix starts, right-left+1.

Apply the same proof to zeros or negatives

Counterexample: A later zero could make an earlier product below k after it previously failed; negative factors reverse order.

Reject them here and derive a different method for a broader domain.

Follow-ups

Allow zeros.

For positive k, every interval containing a zero has product zero and qualifies. One approach counts those intervals separately and runs the positive algorithm on zero-free segments. k≤0 needs separate semantics; the current early return cannot simply be reused.

Use logarithms.

Products become sums of logs, but floating-point rounding can misclassify strict equality near k. An exact integer contract requires an error analysis and correction strategy; the division guard avoids approximation entirely.

Return the longest valid range.

Use the same exact earliest-valid-start state but maximize its length instead of summing suffix counts. Returning every interval can require quadratic output and cannot inherit the constant-space counting claim.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 151/20,000 characters

Self-review

I prove both positivity and strictness assumptions.I guard multiplication before computing it.I count suffixes and keep a long answer.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.