Subarray Product Less Than K - Practice Coding Problems

Subarray Product Less Than K - Problem

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.

Note: Since the product can grow very large, you need to consider edge cases like zeros and negative numbers.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,5,2,6], k = 100

› Output: 8

💡 Note: Valid subarrays: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]. Each has product < 100.

Example 2 — All Valid

$ Input: nums = [1,2,3], k = 0

› Output: 0

💡 Note: Since k=0, no subarray can have product < 0 (all elements are positive).

Example 3 — Large k

$ Input: nums = [1,1,1], k = 10

› Output: 6

💡 Note: All possible subarrays: [1], [1], [1], [1,1], [1,1], [1,1,1]. All have product 1 < 10.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[10,5,2,6] and threshold k=100

Process

Find all contiguous subarrays with product < k

Output

Count of valid subarrays = 8

Key Takeaway

🎯 Key Insight: Use sliding window technique - when window [left,right] is valid, all subarrays ending at right are also valid

Asked in

F Facebook 25 a Amazon 18 G Google 15

The key insight is using a sliding window approach where for each valid window ending at position right, there are exactly (right - left + 1) valid subarrays. Best approach is the sliding window with two pointers. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Two Pointers	O(n)	O(1)	Use two pointers to maintain a valid window and count subarrays efficiently
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and count those with product < k

Sliding Window - Two Pointers — Algorithm Steps

Initialize left and right pointers and product
Expand right pointer and multiply product
If product >= k, shrink from left until valid
Add (right - left + 1) to count for all subarrays ending at right

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Right

Move right pointer and multiply product

Shrink Left

If product >= k, move left pointer

Count Subarrays

Add (right - left + 1) valid subarrays ending at right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    if (k <= 1) return 0;
    
    int count = 0;
    int product = 1;
    int left = 0;
    
    for (int right = 0; right < numsSize; right++) {
        product *= nums[right];
        
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        
        count += right - left + 1;
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is visited at most twice (once by right, once by left pointer)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for pointers and product

✓ Linear Space

85.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window - Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler