D
DevExCode

LeetCode 1852: Distinct Numbers in Each Subarray Solution

Master LeetCode problem 1852 (Distinct Numbers in Each Subarray), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1852. Distinct Numbers in Each Subarray

Medium
ArrayHash TableSliding Window

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach with a data structure to keep track of the distinct numbers in each subarray. We can use a HashMap to store the counts of each number in the current subarray.

  1. Initialize an empty HashMap to store the counts of numbers in the current window and a counter to keep track of the distinct numbers.
  2. Initialize two pointers left and right at the start of the array.
  3. Iterate over the array using the right pointer:
    • Increment the count of the current number in the HashMap.
    • If the count becomes 1, increment the distinct number counter.
    • If the window size is greater than nums[i], decrement the count of the number at left pointer.
      • If the count becomes 0, decrement the distinct number counter.
      • Move the left pointer to the right.
    • Calculate the distinct numbers in the current subarray and store it in the result array.
  4. Return the result array.

Solution Code

class Solution {
    public int[] distinctNumbers(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int[] result = new int[nums.length - k + 1];
        int distinctCount = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            countMap.put(nums[right], countMap.getOrDefault(nums[right], 0) + 1);
            if (countMap.get(nums[right]) == 1) {
                distinctCount++;
            }

            if (right - left + 1 > k) {
                countMap.put(nums[left], countMap.get(nums[left]) - 1);
                if (countMap.get(nums[left]) == 0) {
                    distinctCount--;
                }
                left++;
            }

            if (right - left + 1 == k) {
                result[left] = distinctCount;
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1852 (Distinct Numbers in Each Subarray)?

This page provides optimized solutions for LeetCode problem 1852 (Distinct Numbers in Each Subarray) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 1852 (Distinct Numbers in Each Subarray) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1852 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1852 in Java, C++, or Python.

Back to LeetCode Solutions