Python O(n) window sliding algorithm

  • 0

    I'm just saying that we can do this, doesn't mean this solution is optimal. Just use a dictionary check and update indices should be much simpler.

    class Solution(object):
        def containsNearbyDuplicate(self, nums, k):
            :type nums: List[int]
            :type k: int
            :rtype: bool
            if not nums or len(nums) == 0:
                return False
            table = {}
            left = 0
            right = 0
            while right < len(nums):
                if nums[right] in table:
                    return True
                table[nums[right]] = 1
                right += 1
                if right - left == k + 1: # window size == k + 1
                    del table[nums[left]]
                    left += 1
            return False

  • 0

    My implementation:

    def contains_nearby_duplicate(xs, k):
        w, n = set(), len(xs)
        for i in xrange(min(k+1,n)):
            if xs[i] in w:
                return True
        for j in xrange(n-k-1):
            new = xs[j+k+1]
            if new in w:
                return True
        return False

Log in to reply

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