hard Subarrays with K Different Integers

Problem Statement

Given an array of integers nums and an integer k, return the number of subarrays with exactly k different integers.

A subarray is a contiguous part of an array.

Examples

Example 1:

• Input: nums = [4, 2, 4, 2, 5], k = 2
• Output: 7
• Explanation: The subarrays with exactly 2 different integers are [4, 2], [2, 4], [4, 2, 4], [2, 4, 2], [4, 2], [4, 2, 4, 2], and [2, 5].

Example 2:

• Input: nums = [2, 4, 1, 3, 1, 3], k = 3
• Output: 4
• Explanation: The subarrays with exactly 3 different integers are [2, 4, 1], [4, 1, 3], [4, 1, 3, 1], and [4, 1, 3, 1, 3].

Example 3:

• Input: nums = [4, 4, 4, 5, 5, 6], k = 1
• Output: 10
• Explanation: The subarrays with exactly 1 different integer are [4], [4], [4], [4, 4], [4, 4], [4, 4, 4], [5], [5], [5, 5] and [6].

Constraints:

• 1 <= nums.length <= 2 * 10⁴
• 1 <= nums[i], k <= nums.length

Solution

To solve this problem, we use a sliding window approach combined with a count array. The idea is to maintain a window that slides over the array while keeping track of the number of distinct integers in the window. By adjusting the window size dynamically, we can count the number of subarrays with exactly k distinct integers.

This method is efficient because it processes each element in the array once, making it linear in time complexity. The count array helps in tracking the frequency of each integer within the window, allowing us to efficiently manage the window boundaries.

Step-by-Step Algorithm

1. Initialization:

   • Create an array count of size nums.length + 1 to store the frequency of each element in the current window.
   • Initialize result to store the total number of subarrays with exactly k distinct integers.
   • Set left and right pointers to the start of the array.
   • Initialize windowCount to keep track of valid subarrays within the current window.

2. Expand the window:

   • While right is less than the length of nums, do the following:
     • Increment the count for the element at the right pointer and move the right pointer to the right.
     • If the element at right was not in the window before (its count was zero), decrement k.

3. Adjust the window:

   • If k becomes negative, it means the window has more than k distinct elements:
     • Move the left pointer to the right until the window has exactly k distinct elements again, decrementing the count of the element at the left pointer each time and incrementing k.
     • Reset windowCount to zero.

4. Count valid subarrays:

   • If k is zero, it means the window has exactly k distinct elements:
     • Move the left pointer to the right while the count of the element at left is greater than one, reducing the window size.
     • For each valid adjustment, increment windowCount.
     • Add windowCount + 1 to result.

5. Return the result:

   • The final value of result is the number of subarrays with exactly k distinct integers.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step with the input nums = [4, 2, 4, 2, 5] and k = 2.

1. Initialization:

   • count = [0, 0, 0, 0, 0, 0]
   • result = 0
   • left = 0
   • right = 0
   • windowCount = 0

2. First iteration (right = 0):

   • Increment count[4] → count = [0, 0, 0, 0, 1, 0]
   • Move right to 1
   • k becomes 1

3. Second iteration (right = 1):

   • Increment count[2] → count = [0, 0, 1, 0, 1, 0]
   • Move right to 2
   • k becomes 0
   • Count subarrays:
     • count[nums[0]] = count[0](0) > 1 is false, so no change in left
     • windowCount = 0
     • Add windowCount + 1 to result → result = 1

4. Third iteration (right = 2):

   • Increment count[4] → count = [0, 0, 1, 0, 2, 0]
   • Move right to 3
   • k is already 0.
   • Count subarrays:
     • count[nums[0]] = count[0](1) > 1 is true, decrement count[4] and move left to 1 → count = [0, 0, 1, 0, 1, 0]
     • windowCount = 1
     • Add windowCount + 1 to result → result = 3

5. Fourth iteration (right = 3):

   • Increment count[2] → count = [0, 0, 2, 0, 1, 0]
   • Move right to 4
   • k is already 0.
   • Count subarrays:
     • count[nums[1]] = count[2](2) > 1 is true, decrement count[2] and move left to 2 → count = [0, 0, 1, 0, 1, 0]
     • windowCount = 2
     • Add windowCount + 1 to result → result = 6

6. Fifth iteration (right = 4):

   • Increment count[5] → count = [0, 0, 1, 0, 1, 1]
   • Move right to 5
   • k becomes -1 (more than k distinct elements)
   • Adjust the window:
     • Decrement count[4] and move left to 3 → count = [0, 0, 1, 0, 0, 1]
     • k becomes 0
     • windowCount = 0
     • count[nums[3] = count[2](1) > 1 is false
     • Add windowCount + 1 to result → result = 7

The final result is 7, indicating there are 7 subarrays with exactly 2 distinct integers.

Code

public class Solution {

  public int subarraysWithKDistinct(int[] nums, int k) {
    // Array to count distinct values in the current window
    int[] count = new int[nums.length + 1];

    int result = 0; // Total number of subarrays with exactly k distinct integers
    int left = 0; // Left boundary of the window
    int right = 0; // Right boundary of the window
    int windowCount = 0; // Current number of valid subarrays in the window

    while (right < nums.length) {
      // Increase the count for the current element and move the right boundary
      if (count[nums[right++]]++ == 0) {
        // If this is a new distinct element, decrement k
        k--;
      }

      // If there are more than k distinct elements, adjust the window from the left
      if (k < 0) {
        // Reduce the count for the element at the left boundary and move the left boundary
        --count[nums[left++]];
        k++;
        windowCount = 0;
      }

      // If there are exactly k distinct elements, count the subarrays
      if (k == 0) {
        // Move the left boundary to reduce the window size while maintaining k distinct elements
        while (count[nums[left]] > 1) {
          --count[nums[left++]];
          windowCount++;
        }
        // Add the current number of valid subarrays to the result
        result += (windowCount + 1);
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 4, 2, 4, 2, 5 };
    int k1 = 2;
    System.out.println(solution.subarraysWithKDistinct(nums1, k1)); // Output: 7

    // Example 2
    int[] nums2 = { 2, 4, 1, 3, 1, 3 };
    int k2 = 3;
    System.out.println(solution.subarraysWithKDistinct(nums2, k2)); // Output: 4

    // Example 3
    int[] nums3 = { 4, 4, 4, 5, 5, 6 };
    int k3 = 1;
    System.out.println(solution.subarraysWithKDistinct(nums3, k3)); // Output: 10
  }
}

Complexity Analysis

Time Complexity

The algorithm operates in linear time relative to the input size. This is due to the following reasons:

• Both the right and left pointers move from the start to the end of the array, resulting in an overall time complexity, where n is the length of the input array nums.

Space Complexity

The space complexity is due to the use of the count array which stores the frequency of each element in the window. The size of the count array is proportional to the length of nums.