<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <code>true</code> <em>if there are two <strong>distinct indices</strong> </em><code>i</code><em> and </em><code>j</code><em> in the array such that </em><code>nums[i] == nums[j]</code><em> and </em><code>abs(i - j) &lt;= k</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,1], k = 3
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,1,1], k = 1
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,1,2,3], k = 2
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

struct LLNode {
    int val;
    LLNode * next;
    LLNode * prev;
    LLNode(int v):val(v),next(nullptr),prev(nullptr){};
};

struct LRU {
    LRU(int m):max(m){}; 
    map<int,LLNode*> tracker;
    LLNode* list = nullptr;
     LLNode* tail = nullptr;
    int count = 0;
    int max;

    bool add(int v);
    bool exist(int v) {return tracker.find(v) != tracker.end();}
    
};


bool LRU::add(int v) {
    
    if (nullptr == list) { 
        // Add First element
        list = new LLNode(v);
        tail = list;
        tracker[v] = list;
        //cout << "add " << v << endl;
    } else if (exist(v)) {
        // exists, so return true, contains duplicate
        //cout << "dup " << v << endl;
        return true;    
    } else {
        // Does not exist!        
        LLNode * tmp = new LLNode(v);
        tmp->next = list;
        list->prev = tmp;
        list = tmp;        
        tracker[v] = list;        
        //cout << "add " << v << endl;
        //cout << tracker[v]->val << endl;
    } 

    if (count >= max) {
        //cout << "C: " << count << " M: " << max << endl;
        tracker.erase(tail->val);
        LLNode * tmp = tail->prev;
        delete tail;
        tail = tmp;
        cout << "drop " << v << endl;
    } else {
        count++;
    }

    return false;

}

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (k ==0) return false;
        
        LRU lru(k);
        //cout << lru.max << endl;
        for (auto &n : nums){
            //cout << "LOOP: " << n << endl;
            if (lru.add(n)) return true;
        }

        return false;   
    }

     
};
93801