Count Subarrays With Score Less Than K - Practice Coding Problems

Count Subarrays With Score Less Than K - Problem

The score of an array is defined as the product of its sum and its length.

For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) × 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: Subarrays: [2] score=2×1=2<10 ✓, [2,1] score=3×2=6<10 ✓, [2,1,3] score=6×3=18≥10 ✗, [1] score=1×1=1<10 ✓, [1,3] score=4×2=8<10 ✓, [3] score=3×1=3<10 ✓. Total: 5 valid subarrays.

Example 2 — Small K Value

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

› Output: 5

💡 Note: Subarrays: [1] score=1×1=1<5 ✓, [1,1] score=2×2=4<5 ✓, [1,1,1] score=3×3=9≥5 ✗, [1] score=1×1=1<5 ✓, [1,1] score=2×2=4<5 ✓, [1] score=1×1=1<5 ✓. Total: 5 valid subarrays.

Example 3 — Large K Value

$ Input: nums = [1,2], k = 100

› Output: 3

💡 Note: All subarrays have score < 100: [1] score=1×1=1<100 ✓, [1,2] score=3×2=6<100 ✓, [2] score=2×1=2<100 ✓. Total: 3 valid subarrays.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10¹⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[2,1,3] and threshold k=10

Calculate Scores

For each subarray: score = sum × length

Count Valid

Count subarrays where score < k

Key Takeaway

🎯 Key Insight: Score grows faster than linearly due to multiplication by length, enabling early termination optimization

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is using the monotonic property: if a subarray has score ≥ k, extending it left will only make the score larger. Best approach uses sliding window with early termination - for each right endpoint, find valid left boundaries until score becomes too large. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window Optimization	O(n²)	O(1)	Use two pointers to maintain a valid window and count subarrays efficiently
Two Pointers with Early Termination	O(n²)	O(1)	Optimized sliding window that uses the monotonic property of scores
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and count those with score < k

Sliding Window Optimization — Algorithm Steps

Initialize left and right pointers at 0
Expand right pointer and add elements to current sum
While score ≥ k, shrink window from left
For each position, add count of valid subarrays ending here

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Right End

For each position as right boundary

Expand Left

Try all possible left boundaries moving backwards

Count Valid

Count subarrays until score becomes too large

Code -

solution.c — C

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

int solution(int* nums, int numsSize, long long k) {
    int count = 0;
    
    for (int right = 0; right < numsSize; right++) {
        long long currentSum = 0;
        for (int left = right; left >= 0; left--) {
            currentSum += nums[left];
            int length = right - left + 1;
            long long score = currentSum * length;
            if (score < k) {
                count++;
            } else {
                break; // No point checking longer subarrays from this left
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop can run up to n times in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for pointers, sum, and count

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 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 Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler