Given an array arr[] of length N and an integer K. The task is to find the minimum length of subarray such that at least one element of the subarray is repeated exactly K times in that subarray. If no such subarray exists, print -1.
Examples:
Input: arr[] = {1, 2, 1, 2, 1}, K = 2
Output: 3
Explanation: Subarray [1,2,1], have K = 2 occurrences of 1Input: arr[] = {2, 2, 2, 3, 4}, K = 3
Output: 3
Brute Force/Naive Approach: Brute force approach is to iterate over all possible subarrays of the array, and for each subarray, count the occurrence of each element. If an element occurs exactly K times, then the length of the subarray is a candidate for the minimum length subarray.
- Initialize a variable mn to INT_MAX, which will store the minimum length subarray.
- Loop through each starting index i in the array, from 0 to N-1.
- Initialize a variable count to 0, which will count the occurrence of the element arr[i].
- Loop through each ending index j in the array, from i to N-1.
- If the current element arr[j] is the same as arr[i], increment the count.
- If the count is equal to K, update mn to the minimum value between mn and j-i+1 (the length of the current subarray).
- Continue looping until all subarrays with starting index i have been checked.
- After looping through all starting indices, if mn is still equal to INT_MAX, there is no subarray with an element occurring exactly K times. Return -1.
- Otherwise, return mn as the length of the minimum length subarray with an element occurring exactly K times.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to return the minimum length of// subarray having an element exactly K timesint minLengthKRepetitions(int* arr, int& N, int& K){ int mn = INT_MAX; for (int i = 0; i < N; i++) { int count = 0; for (int j = i; j < N; j++) { if (arr[j] == arr[i]) { count++; } if (count == K) { mn = min(mn, j - i + 1); break; } } } return (mn == INT_MAX) ? -1 : mn;}// Driver codeint main(){ int arr[] = { 1, 2, 2, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; cout << minLengthKRepetitions(arr, N, K); return 0;} |
Java
import java.util.*;public class Main { // Function to return the minimum length of // subarray having an element exactly K times public static int minLengthKRepetitions(int[] arr, int N, int K) { int mn = Integer.MAX_VALUE; for (int i = 0; i < N; i++) { int count = 0; for (int j = i; j < N; j++) { if (arr[j] == arr[i]) { count++; } if (count == K) { mn = Math.min(mn, j - i + 1); break; } } } return (mn == Integer.MAX_VALUE) ? -1 : mn; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 2, 2, 1 }; int N = arr.length; int K = 3; System.out.println(minLengthKRepetitions(arr, N, K)); }}// This code is cntributed by shivregkec |
Python3
import sys# Function to return the minimum length of# subarray having an element exactly K timesdef minLengthKRepetitions(arr, N, K): mn = sys.maxsize for i in range(N): count = 0 for j in range(i, N): if arr[j] == arr[i]: count += 1 if count == K: mn = min(mn, j - i + 1) break return -1 if mn == sys.maxsize else mn# Driver codearr = [1, 2, 2, 2, 1]N = len(arr)K = 3print(minLengthKRepetitions(arr, N, K))# This code is contributed by shivhack999 |
C#
using System;public class MainClass { // Function to return the minimum length of // subarray having an element exactly K times public static int MinLengthKRepetitions(int[] arr, ref int N, ref int K) { int mn = int.MaxValue; for (int i = 0; i < N; i++) { int count = 0; for (int j = i; j < N; j++) { if (arr[j] == arr[i]) { count++; } if (count == K) { mn = Math.Min(mn, j - i + 1); break; } } } return (mn == int.MaxValue) ? -1 : mn; } // Driver code public static void Main() { int[] arr = { 1, 2, 2, 2, 1 }; int N = arr.Length; int K = 3; Console.WriteLine( MinLengthKRepetitions(arr, ref N, ref K)); }}// This code is contributed by user_dtewbxkn77n |
Javascript
// Function to return the minimum length of// subarray having an element exactly K timesfunction minLengthKRepetitions(arr, K) { let mn = Number.MAX_VALUE; const N = arr.length; for (let i = 0; i < N; i++) { let count = 0; for (let j = i; j < N; j++) { if (arr[j] === arr[i]) { count++; } if (count === K) { mn = Math.min(mn, j - i + 1); break; } } } return mn === Number.MAX_VALUE ? -1 : mn;}// Driver codeconst arr = [1, 2, 2, 2, 1];const K = 3;console.log(minLengthKRepetitions(arr, K)); |
Output:
3
Time Complexity: O(N*N)
Auxiliary Space: O(1)
Efficient Approach: In this problem, observe that the smallest length will be achieved when we have exactly one element in the subarray which has K frequency which means subarray will look something like [X . . . X] where X is an element of array arr. Now, follow the steps below to solve this problem:
- Create an array of pairs, such that the number (i.e. arr[i]) is the first element and its index (i.e. i) is second.
- Sort this array.
- Now, create a variable mn to store the answer and initialize it with INT_MAX.
- Now, traverse the array from i = 0 to i = (N – K) and in each iteration:
- If the element at i and (i+K-1) is equal then make mn equal to the minimum out of mn and the difference between the indexes of the following.
- Return mn as the final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum length of// subarray having an element exactly K timesint minLengthKRepetitions(int* arr, int& N, int& K){ pair<int, int> indices[N]; int mn = INT_MAX, i; for (i = 0; i < N; i++) { indices[i].first = arr[i]; indices[i].second = i; } sort(indices, indices + N); for (i = 0; i <= N - K; i++) { if (indices[i].first == indices[i + K - 1].first) mn = min(mn, indices[i + K - 1].second - indices[i].second + 1); } return (mn == INT_MAX) ? -1 : mn;}// Driver codeint main(){ int arr[] = { 1, 2, 2, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; cout << minLengthKRepetitions(arr, N, K); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG { // Function to return the minimum length of // subarray having an element exactly K times public static int minLengthKRepetitions(int[] arr, int N, int K) { int[][] indices = new int[N][2] ; int mn = Integer.MAX_VALUE, i; for (i = 0; i < N; i++) { indices[i][0] = arr[i]; indices[i][1] = i; } //Arrays.sort(indices); for (i = 0; i <= N - K; i++) { if (indices[i][0] == indices[i + K - 1][0]) mn = Math.min(mn, indices[i + K - 1][1] - indices[i][1] + 1); } return (mn == Integer.MAX_VALUE) ? -1 : mn; } // Driver code public static void main (String[] args) { int[] arr = { 1, 2, 2, 2, 1 }; int N = arr.length; int K = 3; System.out.println(minLengthKRepetitions(arr, N, K)); }}// This code is contributed by Shubham Singh |
Python3
# Python program for the above approach# Function to return the minimum length of# subarray having an element exactly K timesdef minLengthKRepetitions(arr, N, K): indices = [[0,0] for i in range(N)] mn = 2**32 for i in range(N): indices[i][0] = arr[i] indices[i][1] = i indices.sort() for i in range(N - K + 1): if (indices[i][0] == indices[i + K - 1][0]): mn = min(mn, indices[i + K - 1][1] - indices[i][1] + 1) return -1 if(mn == 2**32) else mn# Driver codearr = [1, 2, 2, 2, 1]N = len(arr)K = 3print(minLengthKRepetitions(arr, N, K))# This code is contributed by Shubham Singh |
C#
// C# code to implement the above approachusing System;public class GFG{ // Function to return the minimum length of // subarray having an element exactly K times public static int minLengthKRepetitions(int[] arr, int N, int K) { int[,] indices = new int[N,2] ; int mn = Int32.MaxValue, i; for (i = 0; i < N; i++) { indices[i, 0] = arr[i]; indices[i, 1] = i; } //Arrays.sort(indices); for (i = 0; i <= N - K; i++) { if (indices[i,0] == indices[i + K - 1,0]) mn = Math.Min(mn, indices[i + K - 1,1] - indices[i,1] + 1); } return (mn == Int32.MaxValue) ? -1 : mn; } // Driver code static public void Main () { int[] arr = { 1, 2, 2, 2, 1 }; int N = arr.Length; int K = 3; Console.Write(minLengthKRepetitions(arr, N, K)); }}// This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript code for the above approach // Function to return the minimum length of // subarray having an element exactly K times function minLengthKRepetitions(arr, N, K) { let indices = []; let mn = Number.MAX_VALUE, i; for (i = 0; i < N; i++) { indices.push({ first: arr[i], second: i }) } indices.sort(function (a, b) { return a.first - b.first; }); for (i = 0; i <= N - K; i++) { if (indices[i].first == indices[i + K - 1].first) mn = Math.min(mn, indices[i + K - 1].second - indices[i].second + 1); } return (mn == Number.MAX_VALUE) ? -1 : mn; } // Driver code let arr = [1, 2, 2, 2, 1]; let N = arr.length; let K = 3; document.write(minLengthKRepetitions(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
