Find the duplicate value in an array

In this program, we have an array of int elements and one of the element is appearing twice. We want to find that element.

Example

The above array contains duplicate as 1 is appearing twice in an array.

We will return true if any value appears at least twice in the array, and return false if every element is distinct.

Approach

We are using Hashmap to solve this problem

1. Define one integer type Hashmap
2. Iterate the array and perform the following operations:
   • if hashmap contains the current element then return true;
   • If the hashmap does not contain the current element then put this element into hashmap
3. After iterating the whole array if no duplicate is found then simply return false.

Complexity

Time Complexity: O(n), where n is the size of the array

Space Complexity: O(1),  where n is the size of the array

Java Code

import java.util.*;


public class ContainsDuplicate {

    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return true;
            }
            map.put(nums[i], 1);
        }
        return false;
    }


    public static void main(String[] args) {

        int[] arr = new int[] { 1, 2, 5, 7, 1 };
        ContainsDuplicate elements = new ContainsDuplicate();


        boolean result = elements.containsDuplicate(arr);
        System.out.println("Given array " + Arrays.toString(arr)); 
        System.out.println("Contains duplicate : " + result);

    }
    
}

Output

Given array [1, 2, 5, 7, 1]
Contains duplicate : true