Find if Array contains Duplicate Number - Leet Code Solution

September 01, 2020

Problem Statement

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example

``````Input: [1,2,3,1]
Output: true``````

Brute Force Solution

Lets talk about the simplest solution first.

• You can have two loops
• Outer loop iterate over complete array
• Inner loop covers rest of the array
• Just check if rest of the array contains same number or not

Code

``````public boolean containsDuplicate_bruteforce(int[] nums) {
if (nums == null || nums.length == 0) return false;

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

Complexity

Its `O(n^2)`

Another Solution - Sorting

Another simple solution is to sort the numbers first. Then, match consecutive numbers. If you find any pair having same value, return true.

Code

``````public boolean containsDuplicate(int[] nums) {
if (nums == null || nums.length == 0) return false;

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

Complexity

Complexity for sorting is `O(nlogn)` Total complexity is also `O(nlogn)`

Another Solution using Extra Memory - HashSet

Lets utilize a HashSet. A HashSet is a data structure which contains all unique elements, and the complexity to search and adding an element is `O(1)`

``````public boolean containsDuplicate_extraMemory(int[] nums) {
if (nums == null || nums.length == 0) return false;

Set<Integer> set = new HashSet<>();
int l = nums.length;
for (int i=0; i<l; i++) {
if (set.contains(nums[i])) {
return true;
}
}
return false;
}``````

Complexity

Its `O(n)`

Similar Posts

Rotate Image - Leet Code Solution

Problem Statement You are given an n x n 2D matrix representing an image, rotate…

In this post, we will see some of the frequently used concepts/vocabulary in…

Rotate Array - Leet Code Solution

Problem Statement Given an array, rotate the array to the right by k steps…

Valid Palindrome - Leet Code Solution

Problem Statement Given a string, determine if it is a palindrome, considering…

Single Number - Leet Code Solution

Problem Statement Given a non-empty array of integers, every element appears…

Find the Median of Two Sorted Arrays - Leet Code Solution

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

Latest Posts

Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…