Given two numbers K, X and an array arr[] containing N integers, the task is to find the length of the longest subarray such that it contains atmost ‘K’ occurrences of integer’X’.
Examples:
Input: K = 2, X = 2, arr[] = {1, 2, 2, 3, 4}
Output: 5
Explanation:
The longest sub-array is {1, 2, 2, 3, 4} which is the complete array as it contains at-most ‘2’ occurrences of the element ‘2’.
Input: K = 1, X = 2, arr[] = {1, 2, 2, 3, 4},
Output: 3
Explanation:
The longest sub-array is {2, 3, 4} as it contains at-most ‘1’ occurrence of the element ‘2’.
Naive Approach: The naive approach for this problem is to generate all possible subarrays for the given subarray. Then, for every subarray, find the largest subarray that contains at-most K occurrence of the element X. The time complexity for this approach is O(N2) where N is the number of elements in the array.
Efficient Approach: The idea is to solve this problem is to use the two pointer technique.
- Initialize two pointers ‘i’ and ‘j’ to -1 and 0 respectively.
- Keep incrementing ‘i’. If an element X is found, increase the count of that element by keeping a counter.
- If the count of X becomes greater than K, then decrease the count and also decrement the value of ‘j’.
- If the count of X becomes less than or equal to K, increment ‘i’ and make no changes to ‘j’.
- The indices ‘i’ and ‘j’ here represents the starting point and ending point of the subarray which is being considered.
- Therefore, at every step, find the value of |i – j + 1|. The maximum possible value for this is the required answer.
Below is the implementation of the above approach:
C++
// C++ program to find the length of the// longest subarray which contains at-most// K occurrences of the integer X#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subarray which contains at-most// K occurrences of the integer Xint longest(int a[], int n, int k, int x){ // Maximum initialized to zero int max = 0; // Both the pointers initialized to -1 int i = -1; int j = 0; // Variable to store the count of the // occurrence of the element 'x' int m1 = 0; // Iterate through the array once while (i < n) { // If the count is less than equal to K if (m1 <= k) { // Then increase 'i' i++; if (a[i] == x) { // If the integer 'x' is found, // increase the count. m1++; } } // If the count is greater than K else { // If the element 'x' is found, // then decrease the count if (a[j] == x) { m1--; } // Increment the value of j. // This signifies that we are looking // at another subarray j++; }// Find the maximum possible value// among the obtained values if (m1 <= k && i < n) { if (abs(i - j + 1) > max) { max = abs(i - j + 1); } } } return max;}// Driver codeint main(){ int arr[] = { 1, 2, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; int x = 2; cout << longest(arr, n, k, x); return 0;} |
Java
// Java program to find the length of the// longest subarray which contains at-most// K occurrences of the integer Ximport java.util.*;class GFG{// Function to find the length of the// longest subarray which contains at-most// K occurrences of the integer Xstatic int longest(int a[], int n, int k, int x){ // Maximum initialized to zero int max = 0; // Both the pointers initialized to -1 int i = -1; int j = 0; // Variable to store the count of the // occurrence of the element 'x' int m1 = 0; // Iterate through the array once while (i < n) { // If the count is less // than equal to K if (m1 <= k) { // Then increase 'i' i++; if (i < a.length && a[i] == x) { // If the integer 'x' is // found, increase the count. m1++; } } // If the count is greater than K else { // If the element 'x' is found, // then decrease the count if (j < a.length && a[j] == x) { m1--; } // Increment the value of j. // This signifies that we are // looking at another subarray j++; } // Find the maximum possible value // among the obtained values if (m1 <= k && i < n) { if (Math.abs(i - j + 1) > max) { max = Math.abs(i - j + 1); } } } return max;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 2, 2, 3, 4 }; int n = arr.length; int k = 2; int x = 2; System.out.print(longest(arr, n, k, x));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to find the length of the # longest subarray which contains at-most # K occurrences of the integer X # Function to find the length of the # longest subarray which contains at-most # K occurrences of the integer X def longest(a, n, k, x): # Maximum initialized to zero max = 0; # Both the pointers initialized to -1 i = -1; j = 0; # Variable to store the count of the # occurrence of the element 'x' m1 = 0; # Iterate through the array once while (i < n): # If the count is less than equal to K if (m1 <= k): if (a[i] == x): # If the integer 'x' is found, # increase the count. m1 += 1; # Then increase 'i' i += 1; # If the count is greater than K else : # If the element 'x' is found, # then decrease the count if (a[j] == x): m1 -= 1; # Increment the value of j. # This signifies that we are looking # at another subarray j += 1; # Find the maximum possible value # among the obtained values if (m1 <= k and i < n): if (abs(i - j + 1) > max): max = abs(i - j + 1); return max; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 2, 3, 4 ]; n = len(arr); k = 2; x = 2; print(longest(arr, n, k, x)); # This code is contributed by AnkitRai01 |
C#
// C# program to find the length of the// longest subarray which contains at-most// K occurrences of the integer Xusing System;class GFG{// Function to find the length of the// longest subarray which contains at-most// K occurrences of the integer Xstatic int longest(int []a, int n, int k, int x){ // Maximum initialized to zero int max = 0; // Both the pointers initialized to -1 int i = -1; int j = 0; // Variable to store the count of the // occurrence of the element 'x' int m1 = 0; // Iterate through the array once while (i < n) { // If the count is less // than equal to K if (m1 <= k) { // Then increase 'i' i++; if (i < a.Length && a[i] == x) { // If the integer 'x' is // found, increase the count. m1++; } } // If the count is greater than K else { // If the element 'x' is found, // then decrease the count if (j < a.Length && a[j] == x) { m1--; } // Increment the value of j. // This signifies that we are // looking at another subarray j++; } // Find the maximum possible value // among the obtained values if (m1 <= k && i < n) { if (Math.Abs(i - j + 1) > max) { max = Math.Abs(i - j + 1); } } } return max;} // Driver codepublic static void Main(string[] args){ int []arr = { 1, 2, 2, 3, 4 }; int n = arr.Length; int k = 2; int x = 2; Console.WriteLine(longest(arr, n, k, x));}}// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript program to find the length of the// longest subarray which contains at-most// K occurrences of the integer X // Function to find the length of the // longest subarray which contains at-most // K occurrences of the integer X function longest( a , n , k , x) { // Maximum initialized to zero var max = 0; // Both the pointers initialized to -1 var i = -1; var j = 0; // Variable to store the count of the // occurrence of the element 'x' var m1 = 0; // Iterate through the array once while (i < n) { // If the count is less // than equal to K if (m1 <= k) { // Then increase 'i' i++; if (i < a.length && a[i] == x) { // If the integer 'x' is // found, increase the count. m1++; } } // If the count is greater than K else { // If the element 'x' is found, // then decrease the count if (j < a.length && a[j] == x) { m1--; } // Increment the value of j. // This signifies that we are // looking at another subarray j++; } // Find the maximum possible value // among the obtained values if (m1 <= k && i < n) { if (Math.abs(i - j + 1) > max) { max = Math.abs(i - j + 1); } } } return max; } // Driver code var arr = [ 1, 2, 2, 3, 4 ]; var n = arr.length; var k = 2; var x = 2; document.write(longest(arr, n, k, x));// This code contributed by Princi Singh </script> |
Output:
5
Time Complexity: O(N), where N is the length of the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
