Problem

https://leetcode.com/problems/count-complete-subarrays-in-an-array/

Optimal Space & Time Complexity

- Time complexity: O(n)
- Space complexity: O(n)

---

Solutions

東

Hao

var countCompleteSubarrays = function(nums) {
    let left = 0;
    let right = 0;
    const distinctNums = new Set(nums);
    const distinctNumsCounter = new Map();
    let completeSubNumsCount = 0;

    while (right < nums.length) {
        distinctNumsCounter.set(nums[right], (distinctNumsCounter.get(nums[right]) || 0) + 1);

        while (distinctNumsCounter.size === distinctNums.size) {
            distinctNumsCounter.set(nums[left], distinctNumsCounter.get(nums[left]) - 1);
            distinctNumsCounter.get(nums[left]) === 0 && distinctNumsCounter.delete(nums[left]);

            left += 1;
            completeSubNumsCount += nums.length - right;
        }

        right += 1;
    }

    return completeSubNumsCount;
};

YC

SOL

---

Supplement / Discussion

東

Hao

https://leetcode.com/problems/count-complete-subarrays-in-an-array/solutions/3839312/100-sliding-window-video-counting-complete-subarrays-good-approach/

1. Use new Set() to get distinct elements
2. map.delete(key) is more readable than delete obj[key]
3. completeSubNumsCount += nums.length - right; make the algorithm could iterate n to include the possible solutions.

YC

SOL