What is the brute force approach and complexity for Count Subarrays With Score Less Than K?

For each start, extend right with a running sum until the score reaches k with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Count Subarrays With Score Less Than K?

Keep the longest window ending at right with score < k; add its length with optimal time complexity O(N) and space complexity O(1).

Count Subarrays With Score Less Than K

Q: How do you identify the pattern for Count Subarrays With Score Less Than K?

Look for key signals in the prompt: "number of subarrays" indicates Counting problem → add a block per right end.; "score strictly less than k" indicates An upper limit. If the score is monotonic, shrinking always fixes it.; "positive integers" indicates Makes sum × length grow with the window. Without positivity, the window would not be safe.; "k up to 10^15" indicates Overflow warning: sum, score and answer all need long long..

Hard·LeetCode #2302 Pro OnlyPattern Transfer

LeetCode

Problem Statement

The score of an array is its sum multiplied by its length. For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) × 5 = 75.

You are given an array of positive integers nums and an integer k. Count how many non-empty contiguous subarrays have a score strictly less than k.

Input

An integer array nums (every element ≥ 1) and a 64-bit integer k.

Output

The number of subarrays with score < k (as a 64-bit integer).

Example 1

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

Output: 6

The subarrays [2], [1], [4], [3], [5] and [2, 1] (score 3 × 2 = 6) are below 10. For example [2, 1, 4] scores 7 × 3 = 21, which is too big.

Example 2

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

Output: 5

Every subarray except [1, 1, 1] (score 3 × 3 = 9) has a score below 5: three single 1's (score 1) and two [1, 1]'s (score 4).

Constraints

• 1 ≤ nums.length ≤ 10^5
• 1 ≤ nums[i] ≤ 10^5
• 1 ≤ k ≤ 10^15
• A sum can reach 10^10 and a score 10^15; the answer can reach 5·10^9. Use long long everywhere.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“number of subarrays”

→ Counting problem → add a block per right end.

“score strictly less than k”

→ An upper limit. If the score is monotonic, shrinking always fixes it.

“positive integers”

→ Makes sum × length grow with the window. Without positivity, the window would not be safe.

“k up to 10^15”

→ Overflow warning: sum, score and answer all need long long.

Approach Complexity Ladder

Brute Force — grow from every startO(N²)O(1)

For each start, extend right with a running sum until the score reaches k

Better — prefix sums + binary searchO(N log N)O(N)

For each right end, binary search the smallest start with score < k

Optimal — sliding window on sum × lengthO(N)O(1)

Keep the longest window ending at right with score < k; add its length

Brute Force Intuition

Fix a start, grow the end, keep a running sum. The score is sum × length. Count each subarray while its score is below k, and stop at the first one that is not: from there the score only grows.

Recognition rule for this sub-pattern:

Count subarrays that satisfy a rule. "At most": for each right end, every start from left to right works, so add (right − left + 1). "At least": once the window is good, every longer one is too, so add left (or n − right).

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Count Subarrays Where Max Element Appears at Least K Times