CODEWITHSUNDEEP
algorithmsub-array
heheNhaha
heheNhaha

Reputation: 25

How to get the number of the Subarray with at least K different numbers?

The question is: "Given an array A only contains integers Return the number of subarrays that contain at least k different numbers. Subarrays cannot be duplicated."

Example:

input array = {1, 2, 3, 4, 2} k = 3

output: 4

Explanation:

the number of the Subarray with at least K different numbers should be 4, which are [1, 2, 3] [2, 3, 4] [3, 4, 2] [1, 2, 3, 4]

Right now what I can do is just find about the number of the subarray with exactly K different numbers:

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 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;
    }
}

But when the input be: array = {1, 2, 3, 4, 2} k = 2 my code will not work correctly, but I don't know where to change. Any thoughts? Thanks!

Update: thanks to @MBo and others' answers, I used 2 pointers to fix this problem, but still cannot get the right answer with: array = {1, 2, 3, 4, 2} k = 3 -> output: 6 (should be 4)

It looks like there are some duplicated substrings be counted, but I don't know how to fix it.

class Solution {
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 2};
        int k = 3;
        int res = helper(A, k);
        System.out.println(res);
        // output is 6, but should be 4
    }
    
    private static int helper(int[] A, int k) {
        if (A == null || A.length == 0) return 0;
    
        int n = A.length;
        int res = 0;
        int differentNumbers = 0;

        Map<Integer, Integer> counter = new HashMap<>();
        int j = 0;  // j - 1 is the right point


        for (int i = 0; i < n; i ++) {
            while (j < n && differentNumbers < k) {
                int numOfThisNumber = counter.getOrDefault(A[j], 0);
                counter.put(A[j], numOfThisNumber + 1);
                if (counter.get(A[j]) == 1) {
                    differentNumbers ++;
                }
                j ++;
            }
            if (differentNumbers == k) {
                res += n - j + 1;
            }

            counter.put(A[i], counter.get(A[i]) - 1);
            if (counter.get(A[i]) == 0) {
                differentNumbers --;
            }
        }
        return res; 
    }
}

Upvotes: 1

Views: 4508

Answers (1)

MBo
MBo

Reputation: 80187

You can combine your hashmap approach with method of two pointers (indices).

Set both indices into 0 and move right one, updating hashmap counts for values at the right end of interval until hashmap size reaches K. Fix right index.

Now move left index, decreasing counts corresponding to the values at left end. Before every step (including left=0) add size-right to result, because all subarrays starting from left and ending after right, do contain needed number of elements.

When some count becomes 0, remove value from hashmap, and fix left index.

Repeat with right index and so on.

Upvotes: 4

Related Questions