Given an arrays arr[] integer and a positive integer k , find the number of subarray which contains atleast k pairs with equal value. The pair is defined as two indices (i, j) such that i < j and arr[i] = arr[j] within the same subarray.
Example:
Input: arr[] = [2, 1, 4 , 5, 2, 1] , k = 1
Output: 3
Explanation: The valid subarrays that contain at least one pair of equal elements are:[2, 1, 4, 5, 2],[2, 1, 4, 5, 2, 1], and[1, 4, 5, 2, 1].Input: arr[] = [1, 2, 3. 4. 5] , k = 2
Output: 0
Explanation: All elements are distinct, so no valid subarray exists.Input: arr[] = [ 2, 1, 4, 2, 5, 2 , 6, 2, 6] , k = 3
Output: 10
Table of Content
[Naive Approach] - Try all Possible Subarrays - O(n^3) Time and O(1) Space
The idea is to check every possible subarray of the given array. For each subarray, we count how many pairs of equal elements it contains. While expanding a subarray by adding a new element, we compare this new element with all the elements that already exist in the current subarray. If the new element matches any previous element, it forms a pair, so we increase the pair count. If the total number of equal pairs in that subarray becomes greater than or equal to K, we count that subarray as a valid one.
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends
int countKPairsSubarray(vector<int> &arr, int k)
{
int n = arr.size();
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++)
{
// Counts equal pairs in current subarray
int cur = 0;
// Extend the subarray ending index
for (int j = i; j < n; j++)
{
// Check if v[j] forms a pair with any previous element
for (int p = i; p < j; p++)
{
if (arr[p] == arr[j])
cur++;
}
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
int main()
{
vector<int> arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
cout << result << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
class GfG {
//Driver Code Ends
static int countKPairsSubarray(int[] arr, int k) {
int n = arr.length;
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++) {
// Counts equal pairs in current subarray
int cur = 0;
// Extend the subarray ending index
for (int j = i; j < n; j++) {
// Check if arr[j] forms a pair with any previous element
for (int p = i; p < j; p++) {
if (arr[p] == arr[j])
cur++;
}
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
//Driver Code Starts
System.out.println(result);
}
}
//Driver Code Ends
def countKPairsSubarray(arr, k):
n = len(arr)
result = 0
# Fix the starting index of the subarray
for i in range(n):
# Counts equal pairs in current subarray
cur = 0
# Extend the subarray ending index
for j in range(i, n):
# Check if arr[j] forms a pair with any previous element
for p in range(i, j):
if arr[p] == arr[j]:
cur += 1
# If pairs are at least k, count this subarray
if cur >= k:
result += 1
return result
#Driver Code Starts
if __name__=="__main__":
arr = [2, 1, 4, 5, 2, 1]
k = 1
print(countKPairsSubarray(arr, k))
#Driver Code Ends
//Driver Code Starts
using System;
class GfG {
//Driver Code Ends
static int CountKPairsSubarray(int[] arr, int k) {
int n = arr.Length;
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++) {
// Counts equal pairs in current subarray
int cur = 0;
// Extend the subarray ending index
for (int j = i; j < n; j++) {
// Check if arr[j] forms a pair with any previous element
for (int p = i; p < j; p++) {
if (arr[p] == arr[j])
cur++;
}
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
static void Main() {
int[] arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = CountKPairsSubarray(arr, k);
Console.WriteLine(result);
}
}
//Driver Code Ends
function countKPairsSubarray(arr, k) {
let n = arr.length;
let result = 0;
// Fix the starting index of the subarray
for (let i = 0; i < n; i++) {
// Counts equal pairs in current subarray
let cur = 0;
// Extend the subarray ending index
for (let j = i; j < n; j++) {
// Check if arr[j] forms a pair with any previous element
for (let p = i; p < j; p++) {
if (arr[p] === arr[j])
cur++;
}
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
// Driver code
let arr = [2, 1, 4, 5, 2, 1];
let k = 1;
console.log(countKPairsSubarray(arr, k));
//Driver Code Ends
Output
3
[Better Approach] - Using Hashmap - O(n^2) Time and O(n) Space
Instead of comparing the newly added element with every previous element inside the subarray (which causes the extra inner loop), keep a frequency map of how many times each value already appears in the current subarray.When you append a new element x, it will form exactly freq[x] new equal pairs (one with each previous occurrence of x). So you can update the pair count in O(1) (amortized) per extension:
//Driver Code Starts
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
//Driver Code Ends
int countKPairsSubarray(vector<int> &arr, int k)
{
int n = arr.size();
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++)
{
// Counts equal pairs in current subarray
int cur = 0;
// to track the count of an element
unordered_map<int, int> freq;
// Extend the subarray ending index
for (int j = i; j < n; j++)
{
// new valid pairs
cur += freq[arr[j]];
// update the current frequency
freq[arr[j]]++;
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
int main()
{
vector<int> arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
cout << result << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.HashMap;
class GfG {
//Driver Code Ends
static int countKPairsSubarray(int[] arr, int k) {
int n = arr.length;
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++) {
// Counts equal pairs in current subarray
int cur = 0;
// to track the count of an element
HashMap<Integer, Integer> freq = new HashMap<>();
// Extend the subarray ending index
for (int j = i; j < n; j++) {
// new valid pairs
cur += freq.getOrDefault(arr[j], 0);
// update the current frequency
freq.put(arr[j], freq.getOrDefault(arr[j], 0) + 1);
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
public static void main(String[] args) {
int[] arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
System.out.println(result);
}
}
//Driver Code Ends
#Driver Code Starts
from collections import defaultdict
#Driver Code Ends
def countKPairsSubarray(arr, k):
n = len(arr)
result = 0
# Fix the starting index of the subarray
for i in range(n):
# Counts equal pairs in current subarray
cur = 0
# to track the count of an element
freq = defaultdict(int)
# Extend the subarray ending index
for j in range(i, n):
# new valid pairs
cur += freq[arr[j]]
# update the current frequency
freq[arr[j]] += 1
# If pairs are at least k, count this subarray
if cur >= k:
result += 1
return result
#Driver Code Starts
if __name__=="__main__":
arr = [2, 1, 4, 5, 2, 1]
k = 1
print(countKPairsSubarray(arr, k))
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
class GfG {
//Driver Code Ends
static int CountKPairsSubarray(int[] arr, int k) {
int n = arr.Length;
int result = 0;
// Fix the starting index of the subarray
for (int i = 0; i < n; i++) {
// Counts equal pairs in current subarray
int cur = 0;
// to track the count of an element
Dictionary<int, int> freq = new Dictionary<int, int>();
// Extend the subarray ending index
for (int j = i; j < n; j++) {
// new valid pairs
if (freq.ContainsKey(arr[j]))
cur += freq[arr[j]];
// update the current frequency
if (freq.ContainsKey(arr[j]))
freq[arr[j]]++;
else
freq[arr[j]] = 1;
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
static void Main() {
int[] arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = CountKPairsSubarray(arr, k);
Console.WriteLine(result);
}
}
//Driver Code Ends
function countKPairsSubarray(arr, k) {
let n = arr.length;
let result = 0;
// Fix the starting index of the subarray
for (let i = 0; i < n; i++) {
// Counts equal pairs in current subarray
let cur = 0;
// to track the count of an element
let freq = {};
// Extend the subarray ending index
for (let j = i; j < n; j++) {
// new valid pairs
cur += (freq[arr[j]] || 0);
// update the current frequency
freq[arr[j]] = (freq[arr[j]] || 0) + 1;
// If pairs are at least k, count this subarray
if (cur >= k)
result++;
}
}
return result;
}
//Driver Code Starts
// Driver code
let arr = [2, 1, 4, 5, 2, 1];
let k = 1;
console.log(countKPairsSubarray(arr, k));
//Driver Code Ends
Output
3
[Expected Approach] - Using Sliding Window and Hashmap - O(n) Time and O(n) Space
We keep a sliding window (a continuous subarray) and a frequency map of values inside it. When we add a number, it creates as many new equal pairs as its current count in the map, so we update the pair total immediately. As soon as the window has ≥ k pairs, every longer subarray ending at that right index is also valid - count them all at once, then move the left side forward and update counts to look for more. Each element enters and leaves the window only once, so the algorithm runs in linear time
Steps
- Use freq to track counts inside the current window and cur for the number of equal pairs.
- Move the right pointer i from 0 to n-1.
- On adding arr[i], do cur += freq[arr[i]] then freq[arr[i]]++.
- While cur >= K, add (n - i) to the answer.
- Then remove the leftmost element by doing freq[arr[j]]-- and cur -= freq[arr[j]], and increment j.
- Continue until i reaches the end.
//Driver Code Starts
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
//Driver Code Ends
int countKPairsSubarray(vector<int> &arr, int k)
{
int n = arr.size();
// stores frequency of elements in current window
unordered_map<int, int> freq;
// left pointer of sliding window
int j = 0;
int result = 0;
// number of equal pairs in current window
int cur = 0;
for (int i = 0; i < n; i++)
{
// new pairs formed by arr[i]
cur += freq[arr[i]];
// update frequency
freq[arr[i]]++;
// shrink window while we have at least k pairs
while (cur >= k)
{
// all subarrays ending from i to n-1 are valid
result += (n - i);
// remove left element from window
freq[arr[j]]--;
cur -= freq[arr[j]];
j++;
}
}
return result;
}
//Driver Code Starts
int main()
{
vector<int> arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
cout << result << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.HashMap;
class GfG {
//Driver Code Ends
static int countKPairsSubarray(int[] arr, int k) {
int n = arr.length;
// stores frequency of elements in current window
HashMap<Integer, Integer> freq = new HashMap<>();
// left pointer of sliding window
int j = 0;
int result = 0;
// number of equal pairs in current window
int cur = 0;
for (int i = 0; i < n; i++) {
// new pairs formed by arr[i]
cur += freq.getOrDefault(arr[i], 0);
// update frequency
freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
// shrink window while we have at least k pairs
while (cur >= k) {
// all subarrays ending from i to n-1 are valid
result += (n - i);
// remove left element from window
freq.put(arr[j], freq.get(arr[j]) - 1);
cur -= freq.get(arr[j]);
j++;
}
}
return result;
}
//Driver Code Starts
public static void main(String[] args) {
int[] arr = {2, 1, 4, 5, 2, 1};
int k = 1;
int result = countKPairsSubarray(arr, k);
System.out.println(result);
}
}
//Driver Code Ends
from collections import defaultdict
def countKPairsSubarray(arr, k):
n = len(arr)
# stores frequency of elements in current window
freq = defaultdict(int)
# left pointer of sliding window
j = 0
result = 0
# number of equal pairs in current window
cur = 0
for i in range(n):
# new pairs formed by arr[i]
cur += freq[arr[i]]
# update frequency
freq[arr[i]] += 1
# shrink window while we have at least k pairs
while cur >= k:
# all subarrays ending from i to n-1 are valid
result += (n - i)
# remove left element from window
freq[arr[j]] -= 1
cur -= freq[arr[j]]
j += 1
return result
#Driver Code Starts
if __name__=="__main__":
arr = [2, 1, 4, 5, 2, 1]
k = 1
print(countKPairsSubarray(arr, k))
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
class GfG
{
//Driver Code Ends
static int CountKPairsSubarray(int[] arr, int k)
{
int n = arr.Length;
// stores frequency of elements in current window
Dictionary<int, int> freq = new Dictionary<int, int>();
// left pointer of sliding window
int j = 0;
int result = 0;
// number of equal pairs in current window
int cur = 0;
for (int i = 0; i < n; i++)
{
// new pairs formed by arr[i]
if (freq.ContainsKey(arr[i]))
cur += freq[arr[i]];
else
freq[arr[i]] = 0;
// update frequency
freq[arr[i]]++;
// shrink window while we have at least k pairs
while (cur >= k)
{
// all subarrays ending from i to n-1 are valid
result += (n - i);
// remove left element from window
freq[arr[j]]--;
cur -= freq[arr[j]];
j++;
}
}
return result;
}
//Driver Code Starts
static void Main()
{
int[] arr = { 2, 1, 4, 5, 2, 1 };
int k = 1;
int result = CountKPairsSubarray(arr, k);
Console.WriteLine(result);
}
}
//Driver Code Ends
function countKPairsSubarray(arr, k) {
let n = arr.length;
// stores frequency of elements in current window
let freq = new Map();
// left pointer of sliding window
let j = 0;
let result = 0;
// number of equal pairs in current window
let cur = 0;
for (let i = 0; i < n; i++) {
// new pairs formed by arr[i]
cur += freq.get(arr[i]) || 0;
// update frequency
freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
// shrink window while we have at least k pairs
while (cur >= k) {
// all subarrays ending from i to n-1 are valid
result += (n - i);
// remove left element from window
freq.set(arr[j], freq.get(arr[j]) - 1);
cur -= freq.get(arr[j]);
j++;
}
}
return result;
}
//Driver Code Starts
// Driver code
let arr = [2, 1, 4, 5, 2, 1];
let k = 1;
console.log(countKPairsSubarray(arr, k));
//Driver Code Ends
Output
3