Longest Subarray with Bounded Distinct Elements and Sum
In modern data processing and analytics, identifying contiguous segments of data that adhere to specific constraints is a common requirement. For instance, analyzing log files for sequences of events that are within a certain "burst" limit (distinct event types) and do not exceed a total resource consumption threshold. This problem challenges you to find the longest such segment in a given array, combining constraints on both distinct elements and sum.
Implement a function findLongestSubarray that takes an array of integers nums, an integer k (maximum allowed distinct elements), and an integer targetSum (maximum allowed sum). Your function should return the length of the longest contiguous subarray nums[L...R] (where 0 <= L <= R < nums.length) that satisfies both of the following conditions:
nums[L...R] is at most k.nums[L...R] is less than or equal to targetSum.If no such subarray exists (e.g., nums is empty, or no single element satisfies the conditions), return 0.
nums: An array of integers. Can contain positive, negative, or zero values.k: An integer representing the maximum allowed distinct elements in a subarray.targetSum: An integer representing the maximum allowed sum for a subarray.nums should result in a return value of 0.nums can be any integer, including negative numbers. The sum constraint targetSum also applies to these.Examples
Example 1
Input:
nums = [1, 2, 1, 3, 2], k = 2, targetSum = 4
Output:
3
Note:
The subarray [1, 2, 1] has a sum of 4 and 2 distinct elements ({1, 2}). Both conditions are met, and its length is 3. Other valid subarrays exist (e.g., [1, 3]), but [1, 2, 1] is the longest.
Example 2
Input:
nums = [1, 2, 1, 2, 3, 1, 2], k = 3, targetSum = 10
Output:
5
Note:
The subarray [1, 2, 1, 2, 3] has a sum of 9 and 3 distinct elements ({1, 2, 3}). Both conditions are met, and its length is 5. No longer subarray satisfies these criteria.
Example 3
Input:
nums = [10, 2, 3, 4, 1], k = 4, targetSum = 15
Output:
4
Note:
The subarray [2, 3, 4, 1] has a sum of 10 and 4 distinct elements ({1, 2, 3, 4}). Both conditions are met, and its length is 4. The subarray [10, 2, 3, 4] has a sum of 19, which exceeds targetSum = 15, making it invalid despite having 4 distinct elements.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= k <= nums.length-10^14 <= targetSum <= 10^14O(N^2), ideally O(N).nums is not necessarily sorted.Map/HashMap).k and targetSum?O(N) time, O(N) space in worst case for frequency map).Loading editor...