Find duplicates within a range k in an array

Posted in

Find duplicates within a range k in an array

Vinay Khatri
Last updated on September 19, 2022

    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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments