Leetcode Problem 1852. Distinct Numbers in Each Subarray

1852. Distinct Numbers in Each Subarray

Leetcode Solutions

Sliding Window with Frequency Map

  1. Initialize an empty frequency map (hash map) and an empty list ans to store the results.
  2. Iterate over the first k elements of nums and update the frequency map with the count of each number.
  3. Add the size of the frequency map to ans as it represents the number of distinct numbers in the first window.
  4. Iterate over the rest of the elements in nums starting from index k.
    • Decrement the frequency of the element that is no longer in the window (element at index i - k).
    • If the frequency of that element becomes 0, remove it from the frequency map.
    • Increment the frequency of the new element (element at index i).
    • If the new element is not in the frequency map, add it with a frequency of 1.
    • Add the current size of the frequency map to ans.
  5. Return the list ans.
UML Thumbnail

Brute Force with Sliding Subarrays

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...