Frontend School

Longest Subarray with Bounded Distinct Elements and Sum

DSA
hard

Longest Subarray with Bounded Distinct Elements and Sum

Hard
Two Pointers
Sliding Window
Hash Map

Overview

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.

What you need to do / Task

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:

  1. The number of distinct elements within nums[L...R] is at most k.
  2. The sum of all elements within 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.

Input & output

  • Input:
    • 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.
  • Output:
    • An integer representing the length of the longest subarray satisfying both conditions.

Clarifications

  • An empty array nums should result in a return value of 0.
  • Elements in nums can be any integer, including negative numbers. The sum constraint targetSum also applies to these.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 1 <= k <= nums.length
  • -10^14 <= targetSum <= 10^14
  • The solution should aim for a time complexity better than O(N^2), ideally O(N).
  • The array nums is not necessarily sorted.

Out of scope

  • Handling non-integer inputs or non-array inputs.
  • Optimizations for extremely sparse frequency maps (e.g., using specialized data structures beyond Map/HashMap).
  • Parallel processing or distributed computation.

What interviewers evaluate

  • Correctness and edge cases: Does the solution correctly handle all specified conditions, including empty inputs, single-element arrays, and various combinations of k and targetSum?
  • Algorithmic efficiency: Is the chosen algorithm optimal in terms of time and space complexity for the given constraints? (Expect O(N) time, O(N) space in worst case for frequency map).
  • Code quality and readability: Is the code clean, well-structured, and easy to understand? Are variable names descriptive?
  • Problem-solving approach: How effectively does the candidate apply the Two Pointers/Sliding Window technique to manage multiple, interacting constraints?

Loading editor...