Interview 150
Contains Duplicate II
- Problem
- LC 219
- File
- interview150_LC219ContainsDuplicateII.java
- Path
- pkg5leetcode/interview150/interview150_LC219ContainsDuplicateII.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC219ContainsDuplicateII.java
- Lesson
- Back to the chapter
- Approach
- Hash map stores last index; check distance <= k.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Contains Duplicate II | LC 2195 * APPROACH: Hash map stores last index; check distance <= k.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class interview150_LC219ContainsDuplicateII {11 static boolean containsNearbyDuplicate(int[] nums, int k) {12 Map<Integer, Integer> idx = new HashMap<>();13 for (int i = 0; i < nums.length; i++) {14 if (idx.containsKey(nums[i]) && i - idx.get(nums[i]) <= k) return true;15 idx.put(nums[i], i);16 }17 return false;18 }19 20 public static void main(String[] args) {21 check(containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3), "case1");22 check(!containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1), "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}