Solution Approach

The solution uses binary search with the standard template, combined with a sliding window counting function.

Template Structure:

left, right = min(nums), sum(nums)
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # count of subarrays with sum ≤ mid >= k
        first_true_index = mid
        right = mid - 1  # Search for smaller valid sum
    else:
        left = mid + 1

return first_true_index

The Feasibility Function:

Count subarrays with sum ≤ target using sliding window:

1. Initialize: window_sum = 0, left_ptr = 0, count = 0
2. For each right_ptr:
   • Add nums[right_ptr] to window_sum
   • While window_sum > target: shrink window from left
   • Add right_ptr - left_ptr + 1 to count (all valid subarrays ending at right_ptr)
3. Return count >= k

Why This Works:

We're finding the first (smallest) sum value where at least k subarrays exist. When feasible, we record first_true_index = mid and search left for potentially smaller values. When not feasible, we search right.

Time Complexity: O(n × log S) where S = sum(nums) - min(nums).

Space Complexity: O(1).

Example Walkthrough

Let's walk through finding the 4th smallest subarray sum for nums = [2, 1, 3] and k = 4.

Step 1: Initialize

• left = min(nums) = 1, right = sum(nums) = 6
• first_true_index = -1

Step 2: Binary search iterations

Iteration 1: left = 1, right = 6

• mid = (1 + 6) // 2 = 3
• Count subarrays with sum ≤ 3:
  • Position 0: sum = 2, count += 1 → total = 1
  • Position 1: sum = 2+1 = 3, count += 2 → total = 3
  • Position 2: sum = 3+3 = 6 > 3, shrink → sum = 3, count += 1 → total = 4
• count = 4 >= k = 4 ✓ feasible
• Update: first_true_index = 3, right = 3 - 1 = 2

Iteration 2: left = 1, right = 2

• mid = (1 + 2) // 2 = 1
• Count subarrays with sum ≤ 1:
  • Position 0: sum = 2 > 1, shrink → empty, count += 0
  • Position 1: sum = 1, count += 1 → total = 1
  • Position 2: sum = 1+3 = 4 > 1, shrink → sum = 3 > 1, shrink → empty
• count = 1 < k = 4 ✗ not feasible
• Update: left = 1 + 1 = 2

Iteration 3: left = 2, right = 2

• mid = (2 + 2) // 2 = 2
• Count subarrays with sum ≤ 2:
  • Position 0: sum = 2, count += 1
  • Position 1: sum = 2+1 = 3 > 2, shrink → sum = 1, count += 1 → total = 2
  • Position 2: sum = 1+3 = 4 > 2, shrink → sum = 3 > 2, shrink → empty
• count = 2 < k = 4 ✗ not feasible
• Update: left = 2 + 1 = 3

Step 3: Loop terminates

• left = 3 > right = 2
• Return first_true_index = 3

The 4th smallest subarray sum is 3.

Time and Space Complexity

Time Complexity: O(n * log(sum(nums) - min(nums)))

The algorithm uses binary search on the range [min(nums), sum(nums)]. The binary search range has a size of sum(nums) - min(nums), leading to O(log(sum(nums) - min(nums))) iterations.

For each binary search iteration, the helper function f(s) is called, which uses a sliding window approach to count the number of subarrays with sum ≤ s. This sliding window traversal takes O(n) time since each element is visited at most twice (once by pointer i and once by pointer j).

Therefore, the total time complexity is O(n * log(sum(nums) - min(nums))).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables l, r for binary search bounds
• Variables t, j, cnt, i, x in the helper function f
• The range object in bisect_left is a generator that doesn't create the full list

No additional data structures that scale with input size are used, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

The Pitfall: Using while left < right with right = mid instead of the standard while left <= right template.

Solution: Use the standard template:

left, right = min(nums), sum(nums)
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Incorrect Handling of Negative Numbers

The Pitfall: The sliding window technique only works when all numbers are positive.

Why it fails: With negative numbers, adding elements can decrease the sum, breaking the sliding window invariant.

Solution: This problem assumes positive numbers. For negative numbers, use a different approach (e.g., generate all sums and sort).

3. Integer Overflow

The Pitfall: The sum might exceed integer limits in languages with fixed integer sizes.

Solution: Use long in Java/C++ or be mindful of the constraints.