# Leetcode 217: Contains Duplicate

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

## 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

### 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;
}
}
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.

Coding Interview QuestionsData Structures and AlgorithmsArraysBlind75

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Blind 75 LeetCode Problems: Detailed Solutions

💡More problems are on the way. Blind 75 is a curated collection of 75 coding problems commonly used by fast-paced startups and the top 1% of companies. List gained popularity among software engineers for tech interviews, especially at Google, Amazon, and Facebook (Meta). Arrays 1. Two Sum 2. Best Time

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!