Update Subarrays with K Different Integers.java

varunu28 · web-flow · commit a79f2a05a0be · 2024-03-30T08:30:07.000-07:00
diff --git a/Hard/Subarrays with K Different Integers.java b/Hard/Subarrays with K Different Integers.java
@@ -1,29 +1,23 @@
 class Solution {
-  public int subarraysWithKDistinct(int[] A, int K) {
-    return atMostK(A, K) - atMostK(A, K - 1);
-  }
-  
-  private int atMostK(int[] A, int K) {
-    int start = 0;
-    int end = 0;
-    int n = A.length;
-    Map<Integer, Integer> map = new HashMap<>();
-    int count = 0;
-    while (end < n) {
-      if (map.getOrDefault(A[end], 0) == 0) {
-        K--;
-      }
-      map.put(A[end], map.getOrDefault(A[end], 0) + 1);
-      while (K < 0) {
-        map.put(A[start], map.getOrDefault(A[start], 0) - 1);
-        if (map.get(A[start]) == 0) {
-          K++;
+    public int subarraysWithKDistinct(int[] nums, int k) {
+        return slidingWindowAtMost(nums, k) - slidingWindowAtMost(nums, k - 1);
+    }
+
+    private int slidingWindowAtMost(int[] nums, int k) {
+        Map<Integer, Integer> map = new HashMap<>();
+        int left = 0;
+        int count = 0;
+        for (int right = 0; right < nums.length; right++) {
+            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
+            while (map.size() > k) {
+                map.put(nums[left], map.get(nums[left]) - 1);
+                if (map.get(nums[left]) == 0) {
+                    map.remove(nums[left]);
+                }
+                left++;
+            }
+            count += right - left + 1;
         }
-        start++;
-      }
-      count += end - start + 1;
-      end++;
+        return count;
     }
-    return count;
-  }
 }
