One post tagged with "leetcode"

Day 1 - Contains Duplicate​

Description​

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.

Example 1:

input: nums = [1, 2, 3, 1]
output: false

Example 2:

input: nums = [1, 2, 3, 4]
output: false

Example 3:

input: nums = [1, 1, 1, 3, 3, 4, 3, 2 , 4, 2]
output: true

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Solution​

Approach 1 - Sorting​

Step 1: We will sort the array nums. If two numbers are the same, they will be placed next to each other. Step 2: We just need to check whether the two adjacent numbers are equal or not.

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

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

    return false;
  }
}

Complexity:

Time

sort => Dual-Pivot Quicksort O(n log n)
for => O(n)
`Result`: O(n log n + n) = O(n log n)

Space

O(1)

Approach 2 - HashSet​

We create a Set and add each element of the nums array into the set. If the insertion fails, it means the element is duplicated, and we return true. Otherwise, if we finish checking the entire array without any failure, it means the array has no duplicated.

class Solution {
  public boolean containsDuplicate(int[] nums) {
    Set<Integer> setNums = new HashSet<>();
    for (int num : nums) {
      if (!setNums.add(nums)) {
        return true;
      }
    }
    return false;
  }
}

Complexity

Time

for => O(n)

Space

Set => O(n)

Thank for reading!