Solution-Length of Longest Subarray With at Most K Frequency
<p>[TOC]</p>
<h2>Solution</h2>
<hr>
<h3>Overview</h3>
<p>The given problem involves working with an integer array <code>nums</code> and an integer <code>k</code>. The task is to find the length of the longest subarray, referred to as a "good" subarray, where the frequency of each element in the subarray is less than or equal to <code>k</code>. In other words, we are looking for a contiguous sequence of elements in the array where the count of each distinct element does not exceed the given threshold <code>k</code>.</p>
<p>Applications of this problem are scenarios where you need to analyze data with certain constraints on the frequency of elements. For example, in network traffic analysis, one might be interested in finding the longest sequence of time intervals where the frequency of certain events does not exceed a specified threshold. This problem can be relevant in various domains where analyzing and controlling the frequency of occurrences is crucial for meaningful insights or operations.</p>
<hr>
<h3>Approach 1: Counting and Sliding Window</h3>
<h4>Intuition</h4>
<p>In approaching the given problem, the key objective is to find the length of the longest contiguous subarray, termed as "good," based on the constraint that the frequency of each element within this subarray should be less than or equal to a given value, denoted as <code>k</code>. The solution lies in understanding the nature of the array and devising a strategy to efficiently identify and track the eligible subarrays.</p>
<p>A crucial insight is recognizing that the goodness of a subarray is intricately tied to the frequency distribution of its elements. To efficiently capture this information, a mechanism is needed to monitor the frequency of each encountered element during the traversal of the array.</p>
<p>Given the need to find the longest good subarray, an intuitive approach is to utilize a sliding window technique. This involves defining two pointers, which dynamically adjust their positions based on the evolving conditions of the array. The sliding window allows us to efficiently maintain the goodness of the subarray by adjusting its size dynamically as we iterate over <code>nums</code>.</p>
<p>Now, let's delve into the loop structure. The loop will iterate through each element of the array, updating the frequency of each encountered element. This counter is pivotal, as it stores the essential information about the array's composition.</p>
<p>Within this loop, there is a conditional check to ensure that the frequency of the current element does not violate the given constraint <code>k</code>. If, at any point, the frequency surpasses <code>k</code>, it indicates a breach of the goodness condition. To rectify this, a second pointer is used to shrink the window from the left, effectively reducing the frequency of elements until the goodness condition is restored.</p>
<p>The decision to check <code>frequency[nums[end]] > k</code> in the while loop is grounded in the fact that <code>frequency[nums[end]]</code> has already been updated within the <code>for</code> loop. This means that only the frequency of the current element (<code>nums[end]</code>) <strong>could</strong> be greater than <code>k</code> and thus is being assessed for compliance with the goodness condition. This sequence in the code ensures that the check is precise, targeting the specific element causing the potential violation.</p>
<p>Throughout this process, the length of the current subarray meeting the goodness criteria is continuously updated. The maximum length encountered so far is stored as the final answer.</p>
<p><img src="https://imgproxy.citrusreader.com/2eZAB3Lsk5IPJ_7hafMG3owkJC9zpiitc0sQKcM0lpk/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTEucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/4DLreIESu13vNsI5rpnoTEFZEeNG2idFiqMKPmJkHMA/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTIucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/9cXykhdOvGgvWphQ0K-V5z6Y_Nin5PgPQa1GTJMUj9E/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTMucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/1mYC1_zPYjZSaCKzMhjfcE2hQx6ztmTN75FFuF4QOjI/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTQucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/BMv6beiIZ_eoJIC1A-ScCi9Kuk2KU1DYKvFhCQudW2E/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTUucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/__tzonvHVyhhuSB72cmDhINeC4GTDsrXfyu9HSK2Bbs/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTYucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/A_tmS5-sidEwPd-VXZPR4BV04V9Wc0bXtjtYlB9U_U8/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTcucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/mX9C2NFNO9IIcWFsF5lR2-l4fslq71l4faX1NmVC10s/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTgucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/5QoACEyD2Y_j-BgabLx75_Anua0usptTLZHPJEwZGmI/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTkucG5n" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/rwg60F-2fQ8EKISliqfUUXRzbGiQ-3mEEt520QeI59M/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTEwLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/XDIgkCYN_VXBoNdWpUGQX1k7ep2OlyXTKDQ8UGpRsCw/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTExLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/n8oaRKkrAI2rVwJbVRG-4eWT3i19g5vbicrIrkQLcH8/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTEyLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/3MJm_JbL-_HU9r3qfuban9gymDpA-FSoNYV7lrJwgFA/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTEzLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/5h66UALtsL9S5QoKi5FcJ5T9s_LeGdjHZ6V8LnWT9Xo/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE0LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/-dMUcHzRdjokUM6uycnTFrxTRnrwjx7893_tC99jCV8/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE1LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/a4iCC5-HYOo1gB6ug9AIKxhFXWcLwJ6A1QMmqRnT1jc/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE2LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/SYpTFXMVCBJTUASZ50DxVqxJ5ouX3BuPfqJ9IA1QBws/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE3LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/KkEwY9T-4MbACfNG8LNdFQXDuqU7uHZZjyun65BLcP4/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE4LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/dOiDiIZRb4TjKIBOKCTaI73wQh29f0QlHsljOz8RYNI/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTE5LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/_1Kt2tec98xtf2Fqox4PjuEgtYKd8zpmDAbe93L4MMs/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTIwLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/8czD4azbJgStS2VAVxp_i942cO4dYnJ7cttSwCAAlOI/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTIxLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/4Cf7MXZpy12CWdZteaVqdVBu87QOfzNU-kUAvySFt_k/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTIyLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/Z1lg7fyJUNuozQlgBRwVwp66QlkhCNaYTgWy_1o4Xjw/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTIzLnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/Dht1QNvM4xJ2ILdqSjGVDL-n3Xq8v1rGvJf7au6yM7Y/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTI0LnBuZw" alt="pic" referrerpolicy="no-referrer"><br>
<img src="https://imgproxy.citrusreader.com/8JCeria5U5ywmCeKObXTwb7z2BBeCT8pLHBS9CFzxmE/raw:1/aHR0cHM6Ly9sZWV0Y29kZS5jb20vcHJvYmxlbXMvRmlndXJlcy8yOTU4LzI5NTgtMS8yOTU4LTI1LnBuZw" alt="pic" referrerpolicy="no-referrer"></p>
<h4>Algorithm</h4>
<ol>
<li>Initialize variables <code>ans</code> and <code>start</code>. Variable <code>ans</code> will store the length of the longest good subarray, and <code>start</code> will be used to track the start of the current subarray.</li>
<li>Create an unordered map named <code>frequency</code> to keep track of the frequency of elements in the array.</li>
<li>Iterate through the elements of the input array <code>nums</code> using a for loop with index <code>end</code>.</li>
<li>Increment the frequency count of the current element <code>nums[end]</code> in the <code>frequency</code> dictionary.</li>
<li>Enter a while loop to handle the condition where the frequency of the current element <code>nums[end]</code> exceeds the given threshold <code>k</code>. In this loop:
<ul>
<li>Move the start of the subarray (<code>start</code>) one position forward.</li>
<li>Decrement the frequency count of the element at index <code>start</code> (start of the current subarray) in the <code>frequency</code> dictionary.</li>
<li>Repeat this process until the frequency of <code>nums[end]</code> in the current subarray becomes less than or equal to <code>k</code>.</li>
</ul>
</li>
<li>Update the length of the longest good subarray (<code>ans</code>) by taking the maximum of its current value and the difference between the current index <code>end</code> and the start index <code>start</code>.</li>
<li>Continue the loop until all elements in the array are processed.</li>
<li>Return the final value of <code>ans</code> as the length of the longest good subarray.</li>
</ol>
<h4>Implementation</h4>
<p>###cpp</p>
<pre><code class="language-cpp">class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
int ans = 0, start = -1;
unordered_map<int, int> frequency;
for (int end = 0; end < nums.size(); end++) {
frequency[nums[end]]++;
while (frequency[nums[end]] > k) {
start++;
frequency[nums[start]]--;
}
ans = max(ans, end - start);
}
return ans;
}
};
</code></pre>
<p>###java</p>
<pre><code class="language-java">class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int ans = 0, start = -1;
Map<Integer, Integer> frequency = new HashMap();
for (int end = 0; end < nums.length; end++) {
frequency.put(nums[end], frequency.getOrDefault(nums[end], 0) + 1);
while (frequency.get(nums[end]) > k) {
start++;
frequency.put(nums[start], frequency.get(nums[start]) - 1);
}
ans = Math.max(ans, end - start);
}
return ans;
}
}
</code></pre>
<p>###python3</p>
<pre><code class="language-python3">class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
ans, start = 0, -1
frequency = Counter()
for end in range(len(nums)):
frequency[nums[end]] += 1
while frequency[nums[end]] > k:
start += 1
frequency[nums[start]] -= 1
ans = max(ans, end - start)
return ans
</code></pre>
<h4>Complexity Analysis</h4>
<p>Let $N$ be the length of <code>nums</code>.</p>
<ul>
<li>
<p>Time complexity: $O(N)$.</p>
<ul>
<li>The outer loop iterates through each element in the array exactly once, as indicated by the range from 0 to the length of <code>nums</code> in the <code>for</code> loop.</li>
<li>Inside this loop, the <code>while</code> loop with the <code>start</code> pointer performs a sliding window operation. However, note that the <code>start</code> pointer is increased and <code>frequency[nums[start]]</code> is decreased within this loop. The <code>start</code> pointer is never decreased after it is increased in the while loop. Hence, once an element is processed in the <code>while</code> loop, it will not be revisited. Therefore, each element is processed at most twice: once during the outer loop and at most once during the <code>while</code> loop.</li>
<li>In the worst case, the <code>while</code> loop could iterate through the entire length of the array during its lifetime. However, since each element is processed at most twice, the total number of iterations across all elements is linear, making the time complexity of the algorithm $O(N)$.</li>
</ul>
</li>
<li>
<p>Space complexity: $O(N)$. The data structure used to store <code>frequency</code> incurs a space complexity of $O(N)$, since in the worst case the array <code>nums</code> can have all unique elements.</p>
</li>
</ul>
<hr>
<h3>Approach 2: Counting and Sliding Window without Nested Loops</h3>
<h4>Intuition</h4>
<p>We have already discussed using sliding window and counting to solve this problem. Now let's develop an approach without nested loops.</p>
<p>Firstly, we initialize two pointers, one marking the <code>start</code> and the other marking the <code>end</code> of the window. As we iterate through the array, we gradually expand the window by moving the <code>end</code> pointer forward. At each step, we update a data structure to keep track of the frequency of elements within the current window. We also maintain an integer that signifies the count of characters with a frequency greater than <code>k</code></p>
<p>Now, here's the crucial insight for this approach: we never shrink the size of the window. Instead, we only expand or move it. Why? Because we aim to find the longest good subarray, meaning once we've encountered a good subarray, we want to keep exploring larger subarrays to maximize the length.</p>
<p>As we process the array, we expand the window by adding the next element; we update the frequency of this element, then we check if its frequency would become <code>k + 1</code>. Why do we do this? If the frequency of the current element were to exceed <code>k</code>, it means we're introducing a "bad" element into the window because the frequency of all elements must be less than or equal to <code>k</code>. If the frequency of the current element is equal to <code>k + 1</code>, we must increment the count of characters with a frequency greater than <code>k</code>.</p>
<p>If we detect a breach in the "goodness" condition (count of characters with a frequency greater than <code>k</code> > 0), we move the window from the <code>start</code>. As we process new elements, the same size window is slid, instead of expanded, with each iteration, until the window meets the "goodness" condition again. If the frequency of the element at <code>start</code> is equal to <code>k</code> after decrementing its frequency, we decrement the count of characters with a frequency greater than <code>k</code>. When this count is zero, we can continue as we did before we found a "bad" element, expanding the window with each new element. This process ensures that the size of our current window is equal to the largest "good" subarray encountered so far.</p>
<p>It's worth noting that since we don't decrease the size of the window, this doesn't guarantee that all explored subarrays of the current size are good. However, it does indicate that we've encountered at least one good subarray of that size in the past. And since our goal is to find the length of the longest good subarray, this information suffices.</p>
<h4>Algorithm</h4>
<p><strong>Algorithm: Longest Good Subarray</strong></p>
<ol>
<li>Initialize variables <code>n</code> to store the length of the input array <code>nums</code>, <code>frequency</code> as a Counter to keep track of the frequency of elements, <code>start</code> to mark the start index of the subarray, and <code>chars_with_freq_over_k</code> to count the number of elements with frequency exceeding <code>k</code>.</li>
<li>Iterate through the array <code>nums</code> using a sliding window approach, with <code>start</code> and <code>end</code> pointers to define the current subarray.</li>
<li>Increment the frequency of the element at index <code>end</code> in the <code>frequency</code> Counter.</li>
<li>If the frequency of the element at index <code>end</code> becomes equal to <code>k + 1</code>, increment <code>chars_with_freq_over_k</code> to track the count of elements exceeding frequency <code>k</code>.</li>
<li>If there are elements with frequency exceeding <code>k</code>:
<ul>
<li>Decrement the frequency of the element at index <code>start</code> in the <code>frequency</code> counter as it moves out of the current window.</li>
<li>If the frequency of the element at index <code>start</code> becomes equal to <code>k</code>, decrement <code>chars_with_freq_over_k</code> as it no longer exceeds frequency <code>k</code>.</li>
<li>Increment the <code>start</code> pointer to move the window forward.</li>
</ul>
</li>
<li>Continue the process until the entire array is traversed.</li>
<li>Return the length of the longest good subarray, which is calculated by subtracting the <code>start</code> index from the total length of the array.</li>
</ol>
<h4>Implementation</h4>
<p>###cpp</p>
<pre><code class="language-cpp">class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> frequency;
int start = 0;
int charsWithFreqOverK = 0;
for (int end = 0; end < n; end++) {
frequency[nums[end]]++;
if (frequency[nums[end]] == k + 1) {
charsWithFreqOverK++;
}
if (charsWithFreqOverK > 0) {
frequency[nums[start]]--;
if (frequency[nums[start]] == k) {
charsWithFreqOverK--;
}
start++;
}
}
return n - start;
}
};
</code></pre>
<p>###java</p>
<pre><code class="language-java">class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int n = nums.length;
Map<Integer, Integer> frequency = new HashMap();
int start = 0;
int charsWithFreqOverK = 0;
for (int end = 0; end < n; end++) {
frequency.put(nums[end], frequency.getOrDefault(nums[end], 0) + 1);
if (frequency.get(nums[end]) == k + 1) {
charsWithFreqOverK++;
}
if (charsWithFreqOverK > 0) {
frequency.put(nums[start], frequency.get(nums[start]) - 1);
if (frequency.get(nums[start]) == k) {
charsWithFreqOverK--;
}
start++;
}
}
return n - start;
}
}
</code></pre>
<p>###python3</p>
<pre><code class="language-python3">class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
frequency = Counter()
start = 0
chars_with_freq_over_k = 0
for end in range(n):
frequency[nums[end]] += 1
if frequency[nums[end]] == k + 1:
chars_with_freq_over_k += 1
if chars_with_freq_over_k:
frequency[nums[start]] -= 1
if frequency[nums[start]] == k:
chars_with_freq_over_k -= 1
start += 1
return n - start
</code></pre>
<h4>Complexity Analysis</h4>
<p>Let $N$ be the length of <code>nums</code>.</p>
<ul>
<li>
<p>Time complexity: $O(N)$. We perform one pass over the given array <code>nums</code>. This incurs a time complexity of $O(N)$.</p>
</li>
<li>
<p>Space complexity: $O(N)$. The data structure used to store <code>frequency</code> incurs a space complexity of $O(N)$ since, in the worst case, the array <code>nums</code> can have all unique elements.</p>
</li>
</ul>
<hr>