Contains Duplicate II

Problem Statement

Constraints

Solution 1: Hash Map Approach

function containsNearbyDuplicateWithHashMap(nums, k) {
    const indexMap = new Map();

    for (let i = 0; i < nums.length; i++) {
        if (indexMap.has(nums[i])) {
            const prevIndex = indexMap.get(nums[i]);
            if (i - prevIndex <= k) {
                return true;
            }
        }
        indexMap.set(nums[i], i);
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithHashMap(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithHashMap(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithHashMap(nums3,k3);  //output: false 

Solution 2: Sliding Window Approach

function containsNearbyDuplicateWithSlidingWindow(nums, k) {
    const window = new Set();

    for (let i = 0; i < nums.length; i++) {
        if (window.has(nums[i])) {
            return true;
        }
        window.add(nums[i]);
        if (window.size > k) {
            window.delete(nums[i - k]);
        }
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithSlidingWindow(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithSlidingWindow(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithSlidingWindow(nums3,k3);  //output: false 

Solution 3: Optimized Hash Map Approach

function containsNearbyDuplicateOptimizedHashMap(nums, k) {
    const indexMap = {};

    for (let i = 0; i < nums.length; i++) {
        if (indexMap.hasOwnProperty(nums[i])) {
            if (i - indexMap[nums[i]] <= k) {
                return true;
            }
        }
        indexMap[nums[i]] = i;
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateOptimizedHashMap(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateOptimizedHashMap(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateOptimizedHashMap(nums3,k3);  //output: false 

Solution 4: Using JavaScript Set for Window Size

function containsNearbyDuplicateWithSet(nums, k) {
    const seen = new Set();

    for (let i = 0; i < nums.length; i++) {
        if (seen.has(nums[i])) {
            return true;
        }
        seen.add(nums[i]);
        if (seen.size > k) {
            seen.delete(nums[i - k]);
        }
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithSet(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithSet(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithSet(nums3,k3);  //output: false 

Solution 5: Brute Force Approach

function containsNearbyDuplicateBruteForce(nums, k) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length && j <= i + k; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateBruteForce(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateBruteForce(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateBruteForce(nums3,k3);  //output: false 

Solution 6: Using Fixed-Size Window with Array

function containsNearbyDuplicateWithFixedSizeArray(nums, k) {
    const window = Array(k + 1).fill(null);

    for (let i = 0; i < nums.length; i++) {
        const index = nums[i] % (k + 1);
        if (window[index] !== null) {
            return true;
        }
        window[index] = nums[i];
        if (i >= k) {
            window[nums[i - k] % (k + 1)] = null;
        }
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithFixedSizeArray(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithFixedSizeArray(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithFixedSizeArray(nums3,k3);  //output: false 

Solution 7: Using Priority Queue

function containsNearbyDuplicateWithPriorityQueue(nums, k) {
    const pq = new PriorityQueue();

    for (let i = 0; i < nums.length; i++) {
        if (pq.contains(nums[i])) {
            return true;
        }
        pq.add(nums[i]);
        if (i >= k) {
            pq.remove(nums[i - k]);
        }
    }

    return false;
}

class PriorityQueue {
    constructor() {
        this.queue = [];
    }

    add(value) {
        this.queue.push(value);
        this.queue.sort((a, b) => a - b);
    }

    remove(value) {
        this.queue = this.queue.filter(item => item !== value);
    }

    contains(value) {
        return this.queue.includes(value);
    }
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithPriorityQueue(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithPriorityQueue(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithPriorityQueue(nums3,k3);  //output: false 

Solution 8: Using Deque

function containsNearbyDuplicateWithDeque(nums, k) {
    const deque = [];

    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < deque.length; j++) {
            if (nums[deque[j]] === nums[i] && i - deque[j] <= k) {
                return true;
            }
        }
        deque.push(i);
        if (deque.length > k) {
            deque.shift();
        }
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateWithDeque(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateWithDeque(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateWithDeque(nums3,k3);  //output: false 

Solution 9: Recursion

function containsNearbyDuplicateRecursion(nums, k) {
    function checkDuplicates(nums, k, index, map) {
        if (index === nums.length) {
            return false;
        }

        const num = nums[index];
        if (map.has(num) && Math.abs(index - map.get(num)) <= k) {
            return true;
        }

        map.set(num, index);
        return checkDuplicates(nums, k, index + 1, map);
    }

    return checkDuplicates(nums, k, 0, new Map());
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicateRecursion(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicateRecursion(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicateRecursion(nums3,k3);  //output: false 

Solution 10: Efficient Lookup for Nearby Duplicates using Map

function containsNearbyDuplicate(nums, k) {
    const indexMap = new Map(); // num: [index1, index2, ...]

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const indices = indexMap.get(num);

        if (indices) {
            const lastIndex = indices[indices.length - 1];
            // Checking if the distance between indices is within the given limit
            if (Math.abs(lastIndex - i) <= k) {
                return true;
            }
        }

        if (!indexMap.has(num)) {
            indexMap.set(num, []);
        }
        indexMap.get(num).push(i);
    }

    return false;
} 

const nums1 = [1, 2, 3, 1];
const k1 = 3;
containsNearbyDuplicate(nums1,k1);  //output: true 

const nums2 = [1, 0, 1, 1];
const k2 = 1;
containsNearbyDuplicate(nums2,k2);  //output: true 

const nums3 = [1, 2, 3, 1, 2, 3];
const k3 = 2;
containsNearbyDuplicate(nums3,k3);  //output: false 

More Problems Solutions