2799. Count Complete Subarrays in an Array

Array Hash Table Sliding Window Counting

Time: O(n)

Space: O(n)

Intuition

Count subarrays where each element appears at least twice? Or count "complete" subarrays with all k distinct values. Count subarrays containing all distinct elements of nums.

Algorithm

1Let k = distinct elements in nums. Count subarrays with exactly k distinct elements.
2Sliding window: when window has k distinct values: all extensions to right are valid.

Common Pitfalls

•Total distinct k. Subarrays with all k = n*(n+1)/2 - subarrays with < k distinct. Sliding window.

2799.cs

// Approach: Sliding window; shrink left while subarray still contains all distinct elements.
// Time: O(n) Space: O(n)

public class Solution
{
    public int CountCompleteSubarrays(int[] nums)
    {
        const int MAX = 2000;
        int totalDistinct = nums.Distinct().Count();
        int ans = 0;
        int distinct = 0;
        int[] count = new int[MAX + 1];

        int l = 0;
        foreach (int num in nums)
        {
            if (++count[num] == 1)
                ++distinct;
                
            while (distinct == totalDistinct)
            {
                if (--count[nums[l++]] == 0)
                    --distinct;
            }

            ans += l;
        }

        return ans;
    }
}

Was this solution helpful?