Quick Overview

Find the length of the shortest contiguous subarray of positive integers whose sum reaches a target when each distinct value is counted only once. A coding-screen problem that tests reasoning about contiguous ranges, bookkeeping for repeated values, and correct handling of the case where no subarray qualifies.

Shortest Subarray Whose Distinct-Value Sum Reaches a Target

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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 ```python 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** ```text 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** ```text 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** ```text 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.

Overview: Find the length of the shortest contiguous subarray of positive integers whose sum reaches a target when each distinct value is counted only once. A coding-screen problem that tests reasoning about contiguous ranges, bookkeeping for repeated values, and correct handling of the case where no subarray qualifies.

Read the full Oracle Software Engineer interview experience this question came from

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`. Return `0` if no subarray qualifies. The distinct sum of a subarray adds each different value once, however many times that value occurs in the subarray. For example, the distinct sum of `[3, 3, 2]` is `3 + 2 = 5`. Implement `shortest_distinct_sum_subarray(nums, target)`. ### 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, whether its copies are 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. The answer is a single integer. ### Example 1 ```text 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 ```text 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. ### 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 No input value, distinct sum or answer exceeds 2^31 - 1, so a 32-bit `int` is enough in Java and C++.

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

Input: ([5, 5, 1, 2, 6], 9)

Expected Output: 3

Explanation: Source Example 1: [1, 2, 6] reaches 9; [5, 5] has distinct sum 5, so the ordinary-sum answer 2 is wrong and the best pair [2, 6] reaches only 8.

Input: ([4, 4, 4, 3], 8)

Expected Output: 0

Explanation: Source Example 2: the largest distinct sum is 4 + 3 = 7, so nothing qualifies although an ordinary sum would accept [4, 4].

Hints

  1. The length counts every element but the distinct sum counts each value once: check your reasoning against [5, 5] and [4, 2, 2, 5] from the examples.
  2. Every value is positive. Ask how the distinct sum of a subarray can change when it gains or loses one element at an end.
  3. When an element leaves a subarray, its value stops contributing only if no other copy of that value is still inside.

Loading coding console...

Show the approach

Approach

Every value is positive, so the distinct sum is monotone under inclusion: adding an element to a subarray either adds a new value or changes nothing, and removing an element either drops a value whose last copy left or changes nothing. Hence for each right end r, if [l, r] qualifies then every [l', r] with l' <= l qualifies too, and the shortest qualifying subarray ending at r starts at the largest qualifying left index L(r); since extending to r + 1 cannot lower any distinct sum, L(r) never decreases as r grows. A sliding window over [left, right] keeps a count for every value (an array indexed by value, at most 10^4 + 1 entries) and the running distinct sum. Moving right in adds nums[right] to the sum only when its count goes from 0 to 1. Then, while the window's distinct sum is at least target, the window length is a candidate answer and nums[left] is removed; its value leaves the sum only when its count drops back to 0, because another copy may still be inside. Invariant: after the inner loop, [left, right] is the shortest suffix of [0, right] that could still be extended into a qualifying window, and every qualifying window ending at right whose start is at least the previous left has been measured. Each index enters and leaves the window at most once, so every minimal qualifying window is examined and the smallest recorded length is the answer; if nothing was recorded the answer is 0. Edge cases: a single element (1 when it is at least target, else 0), all-equal arrays (every distinct sum is that one value), repeated values adjacent or apart (the length counts every copy, the sum counts each value once), target above the distinct sum of the whole array (0), and target up to 10^9. All sums stay below 10^8, so 32-bit integers suffice.

Time complexity:
O(n + m), where n = len(nums) and m = max(nums) <= 10^4
Space complexity:
O(m) for the per-value counts