Problem:
Subarrays with K Different Integers
Given a positive integer array and a target k, return the number of subarrays with distinct integers equal to k. The subarray elements need to be contiguous but not necessarily distinct.
For example,
given [1,2,3,1,2] and k = 2
the output is 4.
there are 4 subarrays with 2 distinct integers.
[1, 2] [2, 3] [3, 1], [1, 2]
given [1,2,3,1,2] and k = 3
the output is 5.
there are 5 subarrays with 3 distinct integers.
[1, 2, 3], [1, 2, 3, 1] [2, 3, 1] [2, 3, 1, 2] [3, 1, 2]
given [1,2,3,1,2] and k = 0
the output is 5.
given [1,2,3,1,2] and k = 10
the output is 0.
Solution:
This is a sliding window problem, quite similar to Longest Substring with At Most K Distinct Characters, here we are dealing with integer array instead of character array or string.
We put the left pointer and right pointer of the sliding window at initial position 0. Then we move the right pointer to expand the sliding window and move the left pointer to shrink the sliding window.
The right pointer is moved one step at a time, once the distinct integers in the sliding window is equal to k, we start to move the left pointer. Here we need to deal with the following situation:
1, 1, 1, 1, 1, 1, 2, 3, 4
All the subarrays with leading 1s are valid subarrays with distinct integers equal to 4. So we need 2 sliding windows that seak the begin and end of the 1s.
1, 1, 1, 1, 1, 1, 2, 3, 4
All the subarrays with leading 1s are valid subarrays with distinct integers equal to 4. So we need 2 sliding windows that seak the begin and end of the 1s.
For the datastructure that count the distinct integers in a sliding window, we can use a HashMap to record the repeating time for each integer.
import java.util.*;
class Solution {
public static void main(String...args) {
int[] arr = new int[]{1,2,3,1,2};
int k = 2;
System.out.println(subarrays(arr, k));
k = 3;
System.out.println(subarrays(arr, k));
k = 1;
System.out.println(subarrays(arr, k));
k = 10;
System.out.println(subarrays(arr, k));
}
public static int subarrays(int[] arr, int k) {
if(k <= 1 || arr == null) throw new RuntimeException("invalid parameter");
if(k == 1)
return arr.length;
int result = 0;
SlidingWindow win1 = new SlidingWindow();
SlidingWindow win2 = new SlidingWindow();
int lp1 = 0;
int lp2 = 0;
for(int i = 0; i < arr.length; i++) {
win1.add(arr[i]);
win2.add(arr[i]);
while(win1.getNumOfUnique() > k) {
win1.remove(arr[lp1++]);
}
while(win2.getNumOfUnique() >= k) {
win2.remove(arr[lp2++]);
}
result += lp2 - lp1;
}
return result;
}
private static class SlidingWindow {
private int numOfUnique = 0;
private Map<Integer, Integer> freq = new HashMap<>();
public void add(int i) {
freq.put(i, freq.getOrDefault(i, 1));
if(freq.get(i) == 1) {
numOfUnique++;
}
}
public void remove(int i) {
int count = freq.get(i);
if(count == 1) {
numOfUnique--;
freq.remove(i);
}
}
public int getNumOfUnique() {
return numOfUnique;
}
}
}
class Solution {
public static void main(String...args) {
int[] arr = new int[]{1,2,3,1,2};
int k = 2;
System.out.println(subarrays(arr, k));
k = 3;
System.out.println(subarrays(arr, k));
k = 1;
System.out.println(subarrays(arr, k));
k = 10;
System.out.println(subarrays(arr, k));
}
public static int subarrays(int[] arr, int k) {
if(k <= 1 || arr == null) throw new RuntimeException("invalid parameter");
if(k == 1)
return arr.length;
int result = 0;
SlidingWindow win1 = new SlidingWindow();
SlidingWindow win2 = new SlidingWindow();
int lp1 = 0;
int lp2 = 0;
for(int i = 0; i < arr.length; i++) {
win1.add(arr[i]);
win2.add(arr[i]);
while(win1.getNumOfUnique() > k) {
win1.remove(arr[lp1++]);
}
while(win2.getNumOfUnique() >= k) {
win2.remove(arr[lp2++]);
}
result += lp2 - lp1;
}
return result;
}
private static class SlidingWindow {
private int numOfUnique = 0;
private Map<Integer, Integer> freq = new HashMap<>();
public void add(int i) {
freq.put(i, freq.getOrDefault(i, 1));
if(freq.get(i) == 1) {
numOfUnique++;
}
}
public void remove(int i) {
int count = freq.get(i);
if(count == 1) {
numOfUnique--;
freq.remove(i);
}
}
public int getNumOfUnique() {
return numOfUnique;
}
}
}
The time complexity is O(N), the left pointers and right pointer only iterate the integer array once.
The space complexity is O(N), the HashMap could have size N.
