Solution 1 - Last-seen map
Track each value’s latest index and test whether the previous occurrence is within k.
Track each value’s latest index and test whether the previous occurrence is within k.
""" 0219.1 - Contains Duplicate II - Solution 1 - Last-seen map """
#####################################################################################
# Imports
#####################################################################################
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def containsNearbyDuplicate(self, nums, k: int) -> bool:
"""Contains Duplicate II Function"""
seen = {}
for i, x in enumerate(nums):
if x in seen and i - seen[x] <= k:
return True
seen[x] = i
return False
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
assert Solution().containsNearbyDuplicate([1, 2, 3, 1], 3)
assert not Solution().containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2)
print("tests passed")
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()/** 0219.1 - Contains Duplicate II - Solution 1 - Last-seen map */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
containsNearbyDuplicate(nums, k) {
const last = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (last.has(x) && i - last.get(x) <= k) return true;
last.set(x, i);
}
return false;
}
}
console.log(new Solution().containsNearbyDuplicate([1, 2, 3, 1], 3)); // true/** 0219.1 - Contains Duplicate II - Solution 1 - Last-seen map */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
containsNearbyDuplicate(nums: number[], k: number): boolean {
const last: Map<number, number> = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const prev = last.get(x);
if (prev !== undefined && i - prev <= k) return true;
last.set(x, i);
}
return false;
}
}
console.log(new Solution().containsNearbyDuplicate([1, 2, 3, 1], 3)); // true// 0219.1 - Contains Duplicate II - Solution 1 - Last-seen map
use std::collections::HashMap;
struct Solution;
impl Solution {
pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
let mut last: HashMap<i32, usize> = HashMap::new();
for (i, x) in nums.into_iter().enumerate() {
if let Some(&j) = last.get(&x) {
if i - j <= k as usize {
return true;
}
}
last.insert(x, i);
}
false
}
}
fn main() {
println!("{}", Solution::contains_nearby_duplicate(vec![1, 2, 3, 1], 3));
}