219_Contains_Duplicate_II.swift

/*
 Done 25.09.2025. Revisited: N/A

 Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 Example 1:
 Input: nums = [1,2,3,1], k = 3
 Output: true

 Example 2:
 Input: nums = [1,0,1,1], k = 1
 Output: true

 Example 3:
 Input: nums = [1,2,3,1,2,3], k = 2
 Output: false

 Constraints:
 1 <= nums.length <= 10^5
 -10^9 <= nums[i] <= 10^9
 0 <= k <= 10^5
 
 Meta
 https://www.youtube.com/watch?v=ypn0aZ0nrL4
 */

import Foundation

class P219 {

    // MARK: - Option 1 (my - brute force). Time: O(n^2). Memory: O(?)

    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        for i in 0..<nums.count {
            for j in 1..<nums.count {
                if abs(i - j) <= k && nums[i] == nums[j] && i != j {
                    return true
                }
            }
        }
        return false
    }

    // MARK: - Option 2 (my). Time: O(?). Memory: O(?)

    func containsNearbyDuplicate2(_ nums: [Int], _ k: Int) -> Bool {
        return false
    }

    // MARK: - Option 3 (neetcode). Time: O(n). Memory: O(k)

    func containsNearbyDuplicate3(_ nums: [Int], _ k: Int) -> Bool {
        var window = Set<Int>()
        var lP = 0

        for rP in 0..<nums.count {
            if rP - lP > k {
                window.remove(nums[lP])
                lP += 1
            }
            if window.contains(nums[rP]) {
                return true
            } else {
                window.insert(nums[rP])
            }
        }

        return false
    }

}