algoadvance

Leetcode 219. Contains Duplicate II

Problem Statement

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 the absolute difference between i and j is at most k.

Clarifying Questions

  1. What is the range of the values in the array nums and the integer k?
    • The elements in nums can be any integer within the allowed range of integer values in C++.
    • It is also assumed k will be a non-negative integer less than or equal to the length of the array.
  2. What should be returned if the array nums is empty or contains only one element?
    • If the array is empty or contains only one element, it is not possible to find two distinct indices. Therefore, the function should return false in such cases.

Strategy

  1. Utilize a hash map (unordered_map in C++) to keep track of the last seen index of each number.
  2. Iterate through the array while updating the hash map.
    • If a number has been seen before and the difference between the current index and the last seen index is less than or equal to k, return true.
    • Otherwise, update the hash map with the current index of the number.
  3. If no such pair is found by the end of the iteration, return false.

Code

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> index_map; // to store the latest index of each number
        
        for (int i = 0; i < nums.size(); i++) {
            if (index_map.find(nums[i]) != index_map.end()) {
                if (i - index_map[nums[i]] <= k) {
                    return true;
                }
            }
            index_map[nums[i]] = i; // update the index of the current number
        }
        
        return false;
    }
};

Time Complexity

The time complexity of this solution is O(n) where n is the number of elements in the array nums. This is because we are making a single pass through the array and performing constant-time operations (hash map insertions and lookups) for each element.

The space complexity is also O(n) in the worst-case scenario when all elements in nums are unique, resulting in the hash map storing n key-value pairs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI