Interview 150
Find the Duplicate Number
- Problem
- LC 287
- File
- interview150_LC287FindTheDuplicateNumber.java
- Path
- pkg5leetcode/interview150/interview150_LC287FindTheDuplicateNumber.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC287FindTheDuplicateNumber.java
- Approach
- Floyd cycle on index-as-next pointer graph.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Find the Duplicate Number | LC 2875 * APPROACH: Floyd cycle on index-as-next pointer graph.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC287FindTheDuplicateNumber {9 static int findDuplicate(int[] nums) {10 int slow = nums[0], fast = nums[0];11 do {12 slow = nums[slow];13 fast = nums[nums[fast]];14 } while (slow != fast);15 slow = nums[0];16 while (slow != fast) {17 slow = nums[slow];18 fast = nums[fast];19 }20 return slow;21 }22 23 public static void main(String[] args) {24 check(findDuplicate(new int[]{1, 3, 4, 2, 2}) == 2, "case1");25 check(findDuplicate(new int[]{3, 1, 3, 4, 2}) == 3, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}