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

1

2

5

7

1

 

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



Thanks for feedback.



Read More....
Check if an array is a min heap
Convert a sorted array into a binary search tree - recursive approach
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array
Merge two sorted arrays