# Solving Leetcode Interviews in Seconds with AI: Contains Duplicate III


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "220" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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  

	# Explanation
	*   **Sliding Window with Sorted Set:** Maintain a sorted set (using a binary search tree implementation like `SortedList` in Python) of the numbers within the current `indexDiff` window. For each new number, efficiently find if there exists a number within the window that satisfies the `valueDiff` condition.
*   **Binary Search for Efficient Lookup:** Use binary search within the sorted set to find the potential candidates that satisfy the `valueDiff` condition.  This avoids a linear scan of the window.
*   **Maintain Window:** Slide the window by adding the new number to the sorted set and removing the number that falls outside the window.

*   **Runtime Complexity:** O(N log K), where N is the length of the input array `nums`, and K is the window size (`indexDiff`).  The `log K` factor comes from the insertion, deletion, and binary search operations on the sorted set. **Storage Complexity:** O(K), due to storing at most `indexDiff` elements in the sorted set.

	
	# Code
	```python
	from sortedcontainers import SortedList

def containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
    """
    Checks if there are two distinct indices i and j in nums such that
    abs(i - j) <= indexDiff and abs(nums[i] - nums[j]) <= valueDiff.

    Args:
        nums: The input list of integers.
        indexDiff: The maximum allowed difference between the indices.
        valueDiff: The maximum allowed difference between the values.

    Returns:
        True if such indices exist, False otherwise.
    """
    if not nums or len(nums) < 2:
        return False

    window = SortedList()
    for i in range(len(nums)):
        # Find the smallest element in the window that is >= nums[i] - valueDiff
        left = nums[i] - valueDiff
        idx = window.bisect_left(left)

        if idx < len(window) and abs(window[idx] - nums[i]) <= valueDiff:
            return True

        window.add(nums[i])

        if i >= indexDiff:
            window.remove(nums[i - indexDiff])

    return False
	```