How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Find k-th smallest subarray sum | TikTok Coding Question

Quick Overview

This question evaluates algorithmic problem-solving skills in array processing, specifically understanding of subarray sum properties, selection and ranking of values, and computational complexity analysis.

Find k-th smallest subarray sum

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given an integer array `nums` of length `n` where all elements are **positive** integers, and an integer `k`. Consider all **non-empty contiguous subarrays** of `nums`. Each subarray has a sum. Return the **k-th smallest** subarray sum (1-indexed) among all subarrays. ## Input - `nums`: array of positive integers - `k`: integer (1-indexed rank) ## Output - An integer: the k-th smallest subarray sum ## Constraints - `1 <= n <= 2 * 10^4` - `1 <= nums[i] <= 10^4` - `1 <= k <= n * (n + 1) / 2` ## Example - `nums = [2, 1, 3]`, `k = 4` - Subarray sums: `[2, 3, 6, 1, 4, 3]` - Sorted: `[1, 2, 3, 3, 4, 6]` - 4th smallest is `3` - Output: `3` ## Notes - Because `n` can be large, an `O(n^2)` approach that enumerates all subarrays is too slow.

Quick Answer: This question evaluates algorithmic problem-solving skills in array processing, specifically understanding of subarray sum properties, selection and ranking of values, and computational complexity analysis.

You are given an array of positive integers nums and an integer k. Consider every non-empty contiguous subarray of nums and compute its sum. Return the k-th smallest subarray sum when all of these sums are sorted in non-decreasing order. Because the number of subarrays is O(n^2), a direct enumeration approach is too slow for the given constraints.

Constraints

1 <= len(nums) <= 2 * 10^4
1 <= nums[i] <= 10^4
1 <= k <= len(nums) * (len(nums) + 1) // 2
All elements in nums are positive integers

Examples

Input: ([2, 1, 3], 4)

Expected Output: 3

Explanation: The subarray sums are [2, 3, 6, 1, 4, 3]. Sorted they become [1, 2, 3, 3, 4, 6], so the 4th smallest sum is 3.

Input: ([5], 1)

Expected Output: 5

Explanation: There is only one non-empty subarray, [5], so its sum is the 1st smallest.

Input: ([1, 1, 1], 5)

Expected Output: 2

Explanation: The subarray sums are [1, 2, 3, 1, 2, 1]. Sorted they are [1, 1, 1, 2, 2, 3], and the 5th smallest is 2.

Input: ([4, 2, 1], 6)

Expected Output: 7

Explanation: The subarray sums are [4, 6, 7, 2, 3, 1]. Sorted they are [1, 2, 3, 4, 6, 7], so the 6th smallest is 7.

Hints

Instead of generating every subarray sum, binary search on the answer value.
For a fixed limit x, count how many subarrays have sum <= x using a sliding window. This works in linear time because all numbers are positive.

Last updated: May 11, 2026

Loading coding console...