DDSA Solutions

2799. Count Complete Subarrays in an Array

MediumView on LeetCode
ArrayHash TableSliding WindowCounting
Time: O(n)
Space: O(n)

Problem Overview

Count subarrays where each element appears at least twice?

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

  1. 1Let k = distinct elements in nums. Count subarrays with exactly k distinct elements.
  2. 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
C#
// 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?

Related Problems