## Monday, August 10, 2015

### LeetCode OJ - Contains Duplicate II

Problem:

Please find the problem here.

Solution:

Instead of using a map, just sort the array with their positions and do a scan, that involves $O(n)$ space, if space is an issue, I could optimize it to $O(k)$ space if needed by building a balanced search tree of the running $k$ elements, in addition, that will produce an algorithm that runs in $O(n \log k)$ time, which is faster than $O(n \log n)$.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/contains-duplicate-ii/

#include "LEET_CONTAINS_DUPLICATE_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_CONTAINS_DUPLICATE_II
{
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
vector<pair<int, unsigned int>> nums_with_position;
nums_with_position.resize(nums.size());
for (unsigned int i = 0; i < nums.size(); i++)
{
nums_with_position[i] = pair<int, unsigned >(nums[i], i);
}
sort(nums_with_position.begin(), nums_with_position.end());
for (unsigned int i = 1; i < nums.size(); i++)
{
if (nums_with_position[i - 1].first == nums_with_position[i].first)
{
if (nums_with_position[i].second - nums_with_position[i - 1].second <= k)
{
return true;
}
}
}
return false;
}
};
};

using namespace _LEET_CONTAINS_DUPLICATE_II;

int LEET_CONTAINS_DUPLICATE_II()
{
Solution solution;
int case1[] = { 3, 2, 3 };
cout << !solution.containsNearbyDuplicate(vector<int>(case1, case1 + _countof(case1)), 1) << endl;
cout << solution.containsNearbyDuplicate(vector<int>(case1, case1 + _countof(case1)), 2) << endl;
return 0;
}