Find the length of the longest subarray with atmost K occurrences of the integer X

0 0 7 minutes read

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(N²) 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 X
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 (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 code
int 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 X
import java.util.*;
 
class GFG{
 
// Function to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
static 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 code
public 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 X
using System;
 
class GFG{
 
// Function to find the length of the
// longest subarray which contains at-most
// K occurrences of the integer X
static 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 code
public 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:

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 zambiatek!