Skip to content

Latest commit

 

History

History
127 lines (106 loc) · 3.61 KB

992. Subarrays with K Different Integers.md

File metadata and controls

127 lines (106 loc) · 3.61 KB

Difficulty : Hard

Related Topics : Two PointersHashTableSliding Window


Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

  • 1 <= A.length <= 20000
  • 1 <= A[i] <= A.length
  • 1 <= K <= A.length

Solution

  • mine
    • Java
      • Sliding Window Runtime: 48 ms, faster than 50.68%, Memory Usage: 65.8 MB, less than 15.24% of Java online submissions
        // O(N)time
        // O(K)space
        public int subarraysWithKDistinct(int[] A, int K) {
            Map<Integer, Integer> map = new HashMap<>();
            int res = 0, l = 0, count = 0, remove = -1;
            for (int a : A) {
                map.put(a, map.getOrDefault(a, 0) + 1);
                if (map.size() >= K && a != remove) {
                    count = 0;
                }
                while (map.size() == K) {
                    count++;
                    int t = map.getOrDefault(A[l], 0);
                    t--;
                    if (t == 0) {
                        remove = A[l];
                        map.remove(A[l]);
                    } else {
                        map.put(A[l], t);
                    }
                    l++;
                }
                res += count;
            }
            return res;
        }
        

  • the most votes
    • Sliding Window Runtime: 9 ms, faster than 80.63%, Memory Usage: 52.9 MB, less than 16.35% of Java online submissions

      the explanation link.

      // O(N)time
      // O(N)space
      public int subarraysWithKDistinct(int[] A, int K) {
          int res = 0, prefix = 0;
          int[] m = new int[A.length + 1];
          for (int i = 0, j = 0, cnt = 0; i < A.length; ++i) {
              if (m[A[i]]++ == 0) ++cnt;
              if (cnt > K) {
                  --m[A[j++]];
                  --cnt;
                  prefix = 0;
              }
              while (m[A[j]] > 1) {
                  ++prefix;
                  --m[A[j++]];
              }
              if (cnt == K) res += prefix + 1;
          }
          return res;
      }
      
    • Sliding Window Runtime: 95 ms, faster than 12.58%, Memory Usage: 93.4 MB, less than 5.09% of Java online submissions

      // O(N)time
      // O(K)space
      public int subarraysWithKDistinct(int[] A, int K) {
          return atMostK(A, K) - atMostK(A, K - 1);
      }
      int atMostK(int[] A, int K) {
          int i = 0, res = 0;
          Map<Integer, Integer> count = new HashMap<>();
          for (int j = 0; j < A.length; ++j) {
              if (count.getOrDefault(A[j], 0) == 0) K--;
              count.put(A[j], count.getOrDefault(A[j], 0) + 1);
              while (K < 0) {
                  count.put(A[i], count.get(A[i]) - 1);
                  if (count.get(A[i]) == 0) K++;
                  i++;
              }
              res += j - i + 1;
          }
          return res;
      }