Find duplicates within a range k in an array

Problem

You are given an array of integers and a number k. You need to check if duplicates exist within distance of k in an array.

Sample Input

[1, 2, 1, 3]  k = 2

Sample Output

True

Approach

We can store the value of an element as a key and its index as the value in a map. If we come to an element that has duplicates and any of the duplicates come within range k in an array, we find the duplicates within a given range. The time complexity of this approach is O(N) and space complexity is also O(N) due to the creation of a map.

C++ Programming

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
 
bool solve(vector<int> &arr, int k)
{

    unordered_map<int, int> mp;
 
    for (int i = 0; i < arr.size(); i++)
    {

        if (mp.find(arr[i]) != mp.end())
        {

            if (i - mp[arr[i]] <= k) {
                return true;
            }
        }
 
        mp[arr[i]] = i;
    }

    return false;
}
 
int main()
{
    vector<int> arr = { 1, 2, 1, 3 };
    int k = 2;
 
    if (solve(arr, k)) {
        cout << "True";
    }
    else {
        cout << "False";
    }
 
    return 0;
}

Output

True

Python Programming

def solve(arr, k):
 
    mp = {}
 
    for i, element in enumerate(arr):
 
        
        if element in mp:
 
            if i - mp.get(element) <= k:
                return True
 
        mp[element] = i
 
    return False
 
arr = [1, 2, 1, 3]
k = 2
 
if solve(arr, k):
    print("True")
else:
    print("False")

Output

True

Java Programming

import java.util.HashMap;
import java.util.Map;
 
class Main
{
    public static boolean solve(int[] arr, int k)
    {

        Map<Integer, Integer> mp = new HashMap<>();
 
        for (int i = 0; i < arr.length; i++)
        {
            if (mp.containsKey(arr[i]))
            {
                if (i - mp.get(arr[i]) <= k) {
                    return true;
                }
            }
 
            mp.put(arr[i], i);
        }
 
        return false;
    }
 
    public static void main(String[] args)
    {
        int[] arr = {1, 2, 1, 3 };
        int k = 2;
 
        if (solve(arr, k)) {
            System.out.println("True");
        }
        else {
            System.out.println("False");
        }
    }
}

Output

True

People are also reading:

• 4–Sum Problem | Quadruplets with a given sum
• WAP to print the truth table for XY+Z
• Find the smallest window in an array sorting which will make the entire array sorted
• WAP to print three numbers in descending order
• Print all triplets that form a geometric progression
• Most Asked Pattern Programs in C
• Find the smallest subarray length whose sum of elements is >= k
• Python Program to Find LCM
• Longest Subarray with Contiguous Elements
• How to Check if a Python String Contains Another String?