Only one test per element :-)

  • 9

    Standard solution with a little trick. I walk over the array once, remembering where I last saw each number, and use that to answer. But the way I do it, I don't need the "have I already seen this" safety test before accessing where I have last seen it.


    In Python 2, dict.get(key) returns None if the key doesn't exist, and somenumber <= None always returns False. So I don't have to first check whether the number has occurred before and then check whether it has occurred recently.

    class Solution:
        def containsNearbyDuplicate(self, nums, k):
            index = {}
            for i, n in enumerate(nums):
                if i - k <= index.get(n):
                    return True
                index[n] = i
            return False


    Similar in Java, but using getOrDefault with default -k - 1:

    public class Solution {
        public boolean containsNearbyDuplicate(int[] nums, int k) {
            Map<Integer, Integer> index = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (i - k <= index.getOrDefault(nums[i], -k - 1))
                    return true;
                index.put(nums[i], i);
            return false;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.