package LeetCode_219

/**
 * 219. Contains Duplicate II
 * https://leetcode.com/problems/contains-duplicate-ii/
 * Given an array of integers and an integer k,
 * find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most 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
 * */
class Solution {
    /*
    * solution: HashMap, key is num, value is the index of num in array, Time:O(n), Space:O(n)
    * */
    fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
        val map = HashMap<Int, Int>()
        for (i in nums.indices) {
            val num = nums[i]
            //if num in map and check diff of current index and num's index
            if (map.contains(num) && i - map.get(num)!! <= k) {
                return true
            }
            map.put(num, i)
        }
        return false
    }
}