220. Contains Duplicate III

Contains Duplicate III

Problem Description 

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

• i != j,
• abs(i - j) <= indexDiff.
• abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

 

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

 

Constraints:

• 2 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 1 <= indexDiff <= nums.length
• 0 <= valueDiff <= 109

Idea:

1. Run a loop for every element nums[i] of the given array.
2. Inside this loop again run a for loop and traverse all the elements from j=i+1 to j=i+k and compare its value to the nums[i].
   • If nums[j]==nums[i] then return true. As we have found an element.
3. Finally when no duplicate element is found then return false before exiting the function.

A) Brute Force Approach

Let`s code it!

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
   for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(Math.abs(nums[i]-nums[j])<=t && (Math.abs(i-j)<=k)){
                return true;
            }
        }
   }
    return false;
};

Complexity 

Time Complexity
We are scanning the string from left to right only once, hence the time complexity will be O(n^2).

Space Complexity
We are not using any extra space, therefore, the space complexity should also be O(1).

Idea: (C++)

• Create a Hash Set for storing k previous elements.
• Traverse for every element nums[i] of the given array in a loop.
  • Check if hash set already contains nums[i] or not. If nums[i] is present in the set ( i.e. duplicate element is present at a distance less than equal to k ), then return true. Else add nums[i] to the set.
  • If the size of the set becomes greater than k then remove the last visited element (nums[i-k]) from the set.
• Finally when no duplicate element is found then return false before exiting the function.

Let`s code it!

#include <bits/stdc++.h>
using namespace std;
bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);
        if(set.size()>k)
            set.erase(nums[i-k]);
    }
    return false;
}
int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
   return 0; 
}

Complexity 

Time Complexity

O(n) : As we visit each element only once and assume that adding an element and removing an element takes constant time in the hash set time complexity is reduced to just O(n).

Space Complexity 

O(min(k,n)) : We are storing k elements at max in the hash set. If k>n then only n element will be stored in the set at max.

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry

Conclusion

That’s all folks! In this post, we solved LeetCode problem #220. Contains Duplicate III using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve Leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!