Rotate Image - Leet Code Solution
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
September 01, 2020
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
Lets talk about the simplest solution first.
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;
}
Its O(n^2)
Another simple solution is to sort the numbers first. Then, match consecutive numbers. If you find any pair having same value, return true.
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 for sorting is O(nlogn)
Total complexity is also O(nlogn)
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;
}
set.add(nums[i]);
}
return false;
}
Its O(n)
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…
Problem Statement Given an array, rotate the array to the right by k steps…
Problem Statement Given a string, determine if it is a palindrome, considering…
Problem Statement Given a non-empty array of integers, every element appears…
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…