Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc.

Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies.

Problem statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Test case #1

Input: nums = [1,2,3,1]
Output: true

Test case #2

Input: nums = [1,2,3,4]
Output: false

Thought Process

My first thoughts when looking at this problem and the questions I have are:

1. So, if two integers are repeating, which one should I return?
2. What are the constraints? Do you have any time & space constraints for this problem?

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are

1. Naive approach
2. Sorting the array
3. Memoization / Hash table approach

Approach 1: Naive / Linear search

Intuition

In this approach, we iterate through the nums array twice to find the pair of elements that are duplicates.

Algorithm

1. Iterate through each element of the array using a loop with index i from 0 to length - 1.For each i, go to the next step.
   • Within the outer loop, iterate through the remaining elements of the array using a loop with index j from i + 1 to length - 1.
   • For each j, If nums[i] is equal to nums[j], return true indicating that duplicates are found.
2. If the entire array has been checked and no duplicates are found, return false.

class Solution {
    public boolean containsDuplicate(int[] nums) {
       for(int i = 0; i < nums.length; i++) {
           for(int j = i + 1; j < nums.length; j++) {
               if(nums[i] == nums[j]) {
                   return true;
               }
           }
       }
       return false;
    }
}

Complexity Analysis

Time complexity: Time is O(N^2), where N is the number of elements in the prices array. We are traversing the entire array twice.

For an array of n integers, there are n(n−1)/2 pairs of integers. Hence, the time is quadratic.

Space complexity: Space is O(1), no extra space is allocated.

Approach 2: Sorting

Intuition

Isn't sorting an easy approach? We sort the nums array, and the duplicate elements are next to each other. A linear iteration through the array is enough to find the duplicate value.

Algorithm

1. Sort the integer array using Arrays.sort method. Sorts the array into ascending numerical order
2. Use a for-loop from 0 to nums.length - 2. We run into ArrayIndexOutOfBoundsException if we run the loop until nums.length - 1.
3. Check if the current and next index are the same, nums[i] == numd[i + 1].

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time complexity: Time is O(NLogN), where N is the number of elements in the prices array. nlogn is for sorting the array, in here the once Java uses is Dual-Pivot Quicksort.

Space complexity: Space is O(1), no extra space is allocated. We sorted the input array.

✅ Approach 3: Memoization [Accepted]

Intuition

We store each element in the hash table, and when we find an already existing value in hashtable, we return true as per problem statement.

Algorithm

1. Create a hash table named hs to store unique elements.
2. Use a loop to iterate through each element of the input array nums.
   1. For each element, check if it is already present in the HashSet (hs) using hs.contains(nums[i]).
   2. If the element is found in the HashSet, return true immediately.
3. If the element is not found in the HashSet, add it to the HashSet using hs.add(nums[i]).
4. If the loop completes without finding any duplicates, return false, indicating that there are no duplicate elements in the array.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hs = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (hs.contains(nums[i])) {
                return true;
            }
            hs.add(nums[i]);
        }
        return false;
    }
}

Complexity Analysis

Time complexity: Time is O(N), where N is the number of elements in the prices array.

Space complexity: Space is O(N), for storing the N elements in the hashtable.