Are you struggling with the “Contains Duplicate III” problem? You’re not alone! This problem is categorized as Hard on coding platforms like LeetCode, but with the right approach, it can be tackled efficiently. In this article, we’ll break down the problem step by step, explore different solutions, and find the most optimal one.

📌 Problem Statement

You are given:

• An integer array nums
• Two integers indexDiff and valueDiff

Your task is to determine if there exists a pair of distinct indices i,ji, j such that:

1. i≠ji \neq j → The indices are distinct.
2. ∣i−j∣≤indexDiff|i – j| \le \text{indexDiff} → The difference between indices is within the limit.
3. ∣nums[i]−nums[j]∣≤valueDiff| \text{nums}[i] – \text{nums}[j] | \le \text{valueDiff} → The absolute value difference is within the limit.

Return:

• True if such a pair exists.
• False otherwise.

✅ Example 1

nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0

Output: true

• Valid Pair: (0, 3) → nums[0] = 1, nums[3] = 1
• ∣0−3∣=3≤3|0 – 3| = 3 \le 3 ✅
• ∣1−1∣=0≤0|1 – 1| = 0 \le 0 ✅

✅ Example 2

nums = [1, 5, 9, 1, 5, 9], indexDiff = 2, valueDiff = 3

Output: false

• No pair satisfies both conditions.

🧑‍💻 Approach 1: Brute Force (Inefficient)

The simplest way to solve the problem is using a nested loop to compare all possible pairs.

Algorithm:

1. Use a loop to select index i.
2. Use another loop to select index j such that j>ij > i.
3. Check both conditions for index difference and value difference.
4. Return true if conditions are met; otherwise, return false.

Code:

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (abs(i - j) <= indexDiff && abs(nums[i] - nums[j]) <= valueDiff) {
                    return true;
                }
            }
        }
        return false;
    }
};

Complexity:

• Time Complexity: O(n2)O(n^2) → Comparing all pairs.
• Space Complexity: O(1)O(1) → No extra data structures used.

🔎 Why is this not optimal?
For large inputs, a time complexity of O(n2)O(n^2) is inefficient.

⚡ Approach 2: Sliding Window with Ordered Set (Efficient Solution)

A better approach uses a sliding window and an ordered set (std::set) to keep track of numbers within the required range.

Key Insight:

• The set stores numbers in sorted order.
• Using lower_bound() helps find the closest value efficiently.

Algorithm:

1. Initialize an empty set called window.
2. Traverse through the array using a loop.
3. For each number:
   • Check if there exists a number in window such that:
     ∣num−x∣≤valueDiff| \text{num} – x | \le \text{valueDiff}
   • Use lower_bound() to find the smallest number ≥ (num – valueDiff).
4. If a valid number is found, return true.
5. Otherwise, insert the number into the set.
6. Remove numbers from the set if they are out of range.

Code:

#include <set>

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        set<long long> window;

        for (int i = 0; i < nums.size(); i++) {
            long long num = (long long)nums[i];

            auto it = window.lower_bound(num - valueDiff);

            if (it != window.end() && *it <= num + valueDiff) {
                return true;
            }

            window.insert(num);

            if (i >= indexDiff) {
                window.erase((long long)nums[i - indexDiff]);
            }
        }
        return false;
    }
};

Explanation:

1. Initialization:
   • window keeps track of numbers within the current sliding window.
2. Check for Valid Pair:
   • lower_bound() finds the smallest number ≥ num - valueDiff.
   • If this number is ≤ num + valueDiff, we return true.
3. Maintain Window Size:
   • Remove numbers from the set that are out of range using erase().

📊 Complexity Analysis:

• Time Complexity: O(nlog⁡k)O(n \log k)
  • O(log⁡k)O(\log k) for insertion, deletion, and searching using std::set.
  • k=indexDiffk = \text{indexDiff}
• Space Complexity: O(k)O(k)
  • Due to the sliding window storing k elements.

🎯 Key Takeaways

• The brute force solution is simple but inefficient for large inputs.
• The sliding window with an ordered set is the most optimal solution for this problem.
• Using std::set::lower_bound() enables quick searches within the value range.

📝 Final Thoughts

Mastering the “Contains Duplicate III” problem is a great way to sharpen your problem-solving skills. Efficient use of data structures like sets can significantly improve your code performance.

If you’d like to practice similar problems, consider exploring topics like:

• Sliding Window Problems
• Binary Search with Ordered Sets
• Two Pointers Technique

Happy coding, and may your algorithms run in logarithmic time! 🚀

💡 Want to Learn More?

• C++ std::set Documentation
• LeetCode Hard Problems for Practice
• Efficient Sliding Window Techniques

Let us know in the comments if you’d like further explanations or other coding challenges! 😊