|
Given an array a[] of size n and integer k. The task is to count a number of different pairs of indexes where values at a given index are the same and both indexes are at least k indices apart.
Examples:
Input: n = 5, k = 2 a = {1, 2, 2, 1, 2}
Output: 3
Explanation: Possible pairs are found in indices
- (0, 3) where distance, 3-0 >= 2
- (1, 4) where distance, 4-1 >= 2
- (2, 4) where distance, 4-2 >= 2
Input: n = 4, k = 1, a = {1, 1, 1, 1}
Output: 6
Explanation: All pairs can be considered.
Approach: This can be solved with the following idea:
Using a map data structure, for each value store it’s indices in map. Iterate in map, for each index find next index which is k index apart and increment in the count.
Below are the steps involved:
- Initialize a map where:
- Key: Integer
- Value: Vector of Integer, which will help to store the indices.
- Iterate in array a:
- Insert the indexes to their respective values.
- Iterate in the map:
- For each value:
- Using lower_bound, we can find how many pairs possible for each index.
- Increment in the count.
- Return count, as the number of pairs possible.
Below is the implementation of the code:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
long long findPairs(vector<int> a, int n, int k)
{
map<int, vector<int> > m;
int i = 0;
while (i < a.size()) {
m[a[i]].push_back(i);
i++;
}
int count = 0;
for (auto a : m) {
vector<int> v = a.second;
int j = 0;
while (j < v.size()) {
int index
= lower_bound(v.begin(), v.end(), v[j] + k)
- v.begin();
count += v.size() - index;
j++;
}
}
return count;
}
int main()
{
int n = 5;
int k = 2;
vector<int> a = { 1, 2, 1, 2, 1 };
cout << findPairs(a, n, k);
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class GFG {
static long findPairs(List<Integer> a, int n, int k)
{
Map<Integer, List<Integer> > m = new HashMap<>();
int i = 0;
while (i < a.size()) {
m.computeIfAbsent(a.get(i),
key -> new ArrayList<>())
.add(i);
i++;
}
int count = 0;
for (Map.Entry<Integer, List<Integer> > entry :
m.entrySet()) {
List<Integer> v = entry.getValue();
int j = 0;
while (j < v.size()) {
int index = lowerBound(v, v.get(j) + k);
count += v.size() - index;
j++;
}
}
return count;
}
static int lowerBound(List<Integer> list, int target)
{
int low = 0, high = list.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (list.get(mid) < target) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
public static void main(String[] args)
{
int n = 5;
int k = 2;
List<Integer> a = Arrays.asList(1, 2, 1, 2, 1);
System.out.println(findPairs(a, n, k));
}
}
|
Python3
from collections import defaultdict
from bisect import bisect_left
def find_pairs(a, n, k):
m = defaultdict(list)
i = 0
while i < len(a):
m[a[i]].append(i)
i += 1
count = 0
for value, indices in m.items():
j = 0
while j < len(indices):
index = bisect_left(indices, indices[j] + k)
count += len(indices) - index
j += 1
return count
def main():
n = 5
k = 2
a = [1, 2, 1, 2, 1]
print(find_pairs(a, n, k))
if __name__ == "__main__":
main()
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
static long FindPairs(List<int> a, int n, int k)
{
Dictionary<int, List<int>> m = new Dictionary<int, List<int>>();
int i = 0;
while (i < a.Count)
{
if (!m.ContainsKey(a[i]))
{
m[a[i]] = new List<int>();
}
m[a[i]].Add(i);
i++;
}
int count = 0;
foreach (var entry in m)
{
List<int> v = entry.Value;
int j = 0;
while (j < v.Count)
{
int index = LowerBound(v, v[j] + k);
count += v.Count - index;
j++;
}
}
return count;
}
static int LowerBound(List<int> list, int target)
{
int low = 0, high = list.Count;
while (low < high)
{
int mid = low + (high - low) / 2;
if (list[mid] < target)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
public static void Main(string[] args)
{
int n = 5;
int k = 2;
List<int> a = new List<int> { 1, 2, 1, 2, 1 };
Console.WriteLine(FindPairs(a, n, k));
}
}
|
Javascript
function findPairs(a, n, k) {
let m = new Map();
let i = 0;
while (i < a.length) {
if (!m.has(a[i])) {
m.set(a[i], []);
}
m.get(a[i]).push(i);
i++;
}
let count = 0;
for (let [key, value] of m) {
let v = value;
let j = 0;
while (j < v.length) {
let index = lowerBound(v, v[j] + k);
count += v.length - index;
j++;
}
}
return count;
}
function lowerBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
function main() {
let n = 5;
let k = 2;
let a = [1, 2, 1, 2, 1];
console.log(findPairs(a, n, k));
}
main();
|
Time Complexity: O(N*logN),where N is the size of the
Auxiliary Space: O(N)
|
