How hard is LeetCode 1852. Distinct Numbers in Each Subarray?

LeetCode 1852. Distinct Numbers in Each Subarray is rated Medium on LeetCode.

What is the time complexity of LeetCode 1852. Distinct Numbers in Each Subarray?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1852. Distinct Numbers in Each Subarray?

The Python solution on this page uses O(k) auxiliary space.

What topics does LeetCode 1852. Distinct Numbers in Each Subarray cover?

LeetCode 1852. Distinct Numbers in Each Subarray is tagged Array, Hash Table and Sliding Window on LeetCode.

Is LeetCode 1852. Distinct Numbers in Each Subarray a premium problem?

Yes. LeetCode 1852. Distinct Numbers in Each Subarray is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Distinct Numbers in Each Subarray — LeetCode 1852 Python Solution

MediumLeetCode PremiumArrayHash TableSliding Window

Problem: #1852
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

The problem

You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in every subarray of size k within nums.

Example

Input: nums = [1,2,3,2,2,1,3], k = 3
Output: [3,2,2,2,3]
Explanation: The number of distinct elements in each subarray goes as follows:

Python solution

Python

class Solution:
    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums[:k])
        ans = [len(cnt)]
        for i in range(k, len(nums)):
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            if cnt[nums[i - k]] == 0:
                cnt.pop(nums[i - k])
            ans.append(len(cnt))
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(k) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1852. Distinct Numbers in Each Subarray is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1852. Distinct Numbers in Each Subarray?: LeetCode 1852. Distinct Numbers in Each Subarray is rated Medium on LeetCode.
What is the time complexity of LeetCode 1852. Distinct Numbers in Each Subarray?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1852. Distinct Numbers in Each Subarray?: The Python solution on this page uses O(k) auxiliary space.
What topics does LeetCode 1852. Distinct Numbers in Each Subarray cover?: LeetCode 1852. Distinct Numbers in Each Subarray is tagged Array, Hash Table and Sliding Window on LeetCode.
Is LeetCode 1852. Distinct Numbers in Each Subarray a premium problem?: Yes. LeetCode 1852. Distinct Numbers in Each Subarray is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.