Contains Duplicate II in C++

Suppose we have an array and an integer k, we have to check whether 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.

So, if the input is like [1,2,4,1] and k = 3, then the output will be True

To solve this, we will follow these steps −

• Define an array nn of pairs

• for initialize i := 0, when i − size of nums, update (increase i by 1), do −

  • insert {nums[i], i} at the end of nn

• sort the array nn

• for initialize i := 1, when i < size of nn, update (increase i by 1), do −

  • if first element of nn[i] is same as first element of nn[i - 1] and |second of nn[i] - second of nn[i - 1]|, then −

    • return true

• return false

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    bool containsNearbyDuplicate(vector<int>& nums, int k) {       vector<pair<int, int> > nn;       for (<) {          nn.push_back(make_pair(nums[i], i));       }       sort(nn.begin(), nn.end());       for (int i = 1; i < nn.size(); i++) {          if (nn[i].first == nn[i - 1].first and abs(nn[i].second - nn[i - 1].second) <= k)             return true;          }          return false;       } }; main(){    Solution ob;    vector<int> v = {1,2,4,1};    cout << (ob.containsNearbyDuplicate(v, 3)); }

Input

{1,2,4,1}

Output

1