Interview Classic 150 Questions P219 Contains Duplicate II

---

Timeline

Timeline

2025-11-13

init

Hash table

---

Problem:

P219 Contains Duplicate II

https://leetcode.cn/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

$O(n^2)$

#include <cstdlib>
#include <vector>
#include <unordered_map>

using std::unordered_map;
using std::vector;

class Solution {
    public:
	bool containsNearbyDuplicate(vector<int> &nums, int k)
	{
		int i, j, n = nums.size();
		unordered_map<int, vector<int> > num2index;

		for (i = 0; i < n; i++)
			num2index[nums[i]].push_back(i);

		for (auto &[_, index_vec] : num2index) {
			if (index_vec.size() > 1) {
				n = index_vec.size();

				for (i = 0; i < n; i++) {
					for (j = i + 1; j < n; j++) {
						if (std::abs(index_vec[i] - index_vec[j]) <= k) {
							return true;
						}
					}
				}
			}
		}
		return false;
	}
};

$O(n)$

A single pass is enough. During the traversal, save the last occurrence of the same value, because the index of the last same value is closest to the current index, so it is most likely to satisfy $abs(i - j) <= k$.

#include <unordered_map>
#include <vector>

using std::vector;
using std::unordered_map;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> lastIndex;

        for (int i = 0; i < nums.size(); ++i) {
            if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k)
                return true;

            lastIndex[nums[i]] = i;
        }
        return false;
    }
};