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)$

One pass is enough. During traversal, save the last same value, because the index of the last same value is closest to the current index, thus 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;
    }
};