/* TC: O(nlogn) Arrays.sort() is merge sort SC: O(logn) Java 13's Arrays.sort() uses a dual-pivot quicksort, which uses log n additional space */
class Solution { public int findDuplicate(int[] nums) { Arrays.sort(nums); // TC: O(nlog(n)) modified mergesort int len = nums.length; for (int i = 1; i < len; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } }
return len; }
/* TC: O(n) SC: O(n) */
import java.util.HashSet;
class Solution { public int findDuplicate(int[] nums) { HashSet<Integer> set = new HashSet<>(); for(int i=0;i<nums.length;i++){ // O(n) if(set.contains(nums[i])) return nums[i]; // contains O(1) else set.add(nums[i]); // add O(1) } return -1; } }
/* TC: O(n) SC: O(1) Floyd Algorithm */ class Solution { public int findDuplicate(int[] nums) { int slow = 0; int fast = 0; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }