Sliding Window : 5 (+HashMap)

Sliding Window : 5 (+HashMap)

Day 4/75:

Question: Length of Longest Subarray With at Most K Frequency -(Medium)

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.        

========== Please Feel free to Jump to Actual Approach============= Intuition: Initially, I considered obtaining the frequency of each element and determining the count of elements based on Min(k, map.get(nums[i])). Subsequently, I intended to add the keys to the answer list for (count) number of times and return the size of the list, assuming a straightforward approach. However, I missed the requirement for identifying the longest contiguous subarray where all elements have frequencies less than or equal to k.

Approach : ( Which doesn't work fully)

  1. You initialize a list list to store the elements of the longest good subarray.
  2. You initialize a HashMap map to store the frequency of each element in the input array.
  3. You iterate through the input array nums, updating the frequencies in the map.
  4. Then, you iterate through the keys of the map (unique elements in nums), and for each key, you determine the count as the minimum of k and the frequency of that element. You then add that key to the list count times.
  5. Finally, return size of list.

Code:

==================================================

Actual Approach: Best and Easy (SlidingWindow+HashMap)

Inuition:

By little more thinking, my instinct led me to consider same sliding window. Given that our objective is to identify the longest subarray adhering to a specific condition. Since the task is finding the longest subarray where each element's frequency remains within the threshold of k, employing a sliding window allows us to efficiently monitor the frequency of elements within a subarray as it dynamically adjusts.

Approach:

  1. Initialize two pointers, start and end, marking the boundaries of window.
  2. HashMap to store the frequency of elements within the current subarray.
  3. Traverse through the array from left to right, incrementing the end pointer. Update the frequency of nums[end] in the map.
  4. If the frequency of nums[end] > k, shrink the window from the start until the frequency of the newly inserted element decreases by one.
  5. Continuously update the maximum length of the good subarray, if necessary.

Finally, return the maximum length discovered.

Complexity:

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


要查看或添加评论,请登录

Suyash Awathe的更多文章

  • Tree: Add One Row to Tree

    Tree: Add One Row to Tree

    Day 17: Problem Statement: Given the root of a binary tree and two integers val and depth, add a row of nodes with…

  • Monotonic Array / TwoPointer :Trapping Rain Water: Most Asked !!

    Monotonic Array / TwoPointer :Trapping Rain Water: Most Asked !!

    Day 16/75 : Problem : Trapping Rain Water -(Hard) Given n non-negative integers representing an elevation map where the…

  • Stack: April POTD

    Stack: April POTD

    Question: Remove K Digits -(Medium) Given string num representing a non-negative integer num, and an integer k, return…

  • Queue-Array: April POTD

    Queue-Array: April POTD

    Day 14/75: Question: Reveal Cards In Increasing Order -(Medium) You are given an integer array . There is a deck of…

    1 条评论
  • Array: 9 April POTD

    Array: 9 April POTD

    Day 13/75: Question: Time Needed to Buy Tickets -(Easy) There are people in a line queuing to buy tickets, where the…

  • Queue : April POTD

    Queue : April POTD

    Day 12/75: Question: Number of Students Unable to Eat Lunch -(Easy) The school cafeteria offers circular and square…

    1 条评论
  • String : Parentheses : April-POTD

    String : Parentheses : April-POTD

    Day 11/75: Question: Minimum Remove to Make Valid Parentheses -(Medium) Given a string s of , and lowercase English…

    3 条评论
  • String : 5April POTD

    String : 5April POTD

    Day 10/75: Question: Make The String Great -(Easy) Given a string of lower and upper case English letters. A good…

  • String Parentheses : 4April POTD

    String Parentheses : 4April POTD

    Day 9/75: Question: Maximum Nesting Depth of the Parentheses -(Easy) A string is a valid parentheses string (denoted…

  • BackTracking : WordSearch :4April POTD

    BackTracking : WordSearch :4April POTD

    Day 9/75: Question: Word Search -(Medium) Given an m x n grid of characters board and a string word, return true if…

    1 条评论

社区洞察

其他会员也浏览了