Shortest Subarray Whose Distinct-Value Sum Reaches a Target

Given an array of positive integers nums and a positive integer target, return the length of the shortest contiguous subarray whose distinct sum is at least target. The distinct sum of a subarray adds each different value once, however many times that value occurs in the subarray: the distinct sum of [3, 3, 2] is 3 + 2 = 5. Return 0 if no subarray qualifies.

Function Signature

def shortest_distinct_sum_subarray(nums: list[int], target: int) -> int:

Rules

• A subarray is a nonempty run of consecutive elements nums[i], nums[i + 1], ..., nums[j]. Its length is j - i + 1 and counts every element, including repeated ones.
• A value that occurs several times in the subarray, next to each other or apart, adds to the distinct sum once.
• Return the smallest length among all subarrays whose distinct sum is at least target, or 0 if there is none.

Constraints

• 1 <= len(nums) <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= target <= 10^9
• every distinct sum is below 10^8, so all values fit in a 32-bit signed integer

Examples

Example 1

Input: nums = [5, 5, 1, 2, 6], target = 9
Output: 3

[1, 2, 6] has distinct sum 9. No subarray of length 2 qualifies: as an ordinary sum [5, 5] would give 10, but its distinct sum is 5, and the best pair, [2, 6], reaches only 8.

Example 2

Input: nums = [4, 4, 4, 3], target = 8
Output: 0

An ordinary sum would accept [4, 4], but no subarray has a distinct sum above 4 + 3 = 7.

Example 3

Input: nums = [4, 2, 2, 5], target = 11
Output: 4

A distinct sum of 11 needs all three values 4, 2 and 5, and only the whole array contains both the 4 and the 5. Its length, 4, counts the repeated 2.