HomeLeetcode220. Contains Duplicate III - Leetcode Solutions
Leetcode

220. Contains Duplicate III – Leetcode Solutions

Declan Clarke

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.

Examples:

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.

Solution in Python

To solve the problem of finding whether there exists a pair of indices (i, j) in the array nums such that the following conditions are satisfied:

  1. i != j
  2. abs(i - j) <= indexDiff
  3. abs(nums[i] - nums[j]) <= valueDiff

We can employ a strategy using a sliding window and a SortedSet from the sortedcontainers module. The SortedSet allows us to efficiently manage a dynamic set of elements while keeping them sorted, which helps us quickly find the closest values to any element within the current window of size indexDiff.

Steps to Solve the Problem:

  1. Initialize a SortedSet: This will be used to maintain the current window of elements in the array, where the window size is controlled by indexDiff.
  2. Iterate through the array nums:
    • For each element nums[i], find the closest value in the current window that could potentially satisfy the valueDiff condition.
    • Check for potential matches both just smaller and just larger than the current element in the SortedSet.
    • If a valid match is found, return True.
    • Add the current element nums[i] to the SortedSet.
    • Ensure that the SortedSet maintains a maximum size of indexDiff by removing the oldest element (i.e., nums[i - indexDiff]) when necessary.
  3. If no valid pair is found during the iteration, return False.
Python
from sortedcontainers import SortedSet

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        # Create a SortedSet to maintain the current window of elements
        window = SortedSet()

        for i, num in enumerate(nums):
            # Find the smallest element in the set that is >= nums[i] - valueDiff
            pos = window.bisect_left(num - valueDiff)
            
            # Check if such an element exists and is within the valueDiff constraint
            if pos < len(window) and abs(window[pos] - num) <= valueDiff:
                return True

            # Add the current number to the set
            window.add(num)
            
            # Maintain the size of the window to be at most indexDiff
            if i >= indexDiff:
                window.remove(nums[i - indexDiff])
        
        return False

Explanation:

  1. SortedSet:
    • The SortedSet from the sortedcontainers module is used because it allows us to maintain a dynamically sorted set of elements with efficient insertion, deletion, and lookup operations.
  2. Window Management:
    • The window set is used to keep track of the last indexDiff elements (or fewer at the beginning). As we iterate over nums, we add the current element to window and remove the element that is outside the current window size.
  3. Finding Close Values:
    • pos = window.bisect_left(num - valueDiff) finds the smallest element in window that is greater than or equal to num - valueDiff. This is crucial because it gives us a potential candidate for satisfying the valueDiff condition.
    • We then check if the difference between this candidate and num is within valueDiff. If it is, we return True.
  4. Efficiency:
    • The operations of adding, removing, and finding the closest element in the SortedSet are all logarithmic in complexity, making this approach efficient for large input sizes.

Result:

The function returns True if there exists a pair (i, j) that satisfies all the given conditions. Otherwise, it returns False. This approach effectively handles large arrays and the constraints provided.

Solution in Javascript

JavaScript
var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
    if (indexDiff <= 0) return false;
    
    // Map that will serve as our TreeSet-like structure
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        
        // Determine the bucket key for the current number
        let bucket = Math.floor(num / (valueDiff + 1));
        
        // Check if current bucket contains a duplicate within the range
        if (map.has(bucket)) {
            return true;
        }
        
        // Check neighboring buckets for values within the range
        if (map.has(bucket - 1) && Math.abs(num - map.get(bucket - 1)) <= valueDiff) {
            return true;
        }
        if (map.has(bucket + 1) && Math.abs(num - map.get(bucket + 1)) <= valueDiff) {
            return true;
        }
        
        // Insert the number into its bucket
        map.set(bucket, num);
        
        // Maintain the size of the map to be at most indexDiff
        if (map.size > indexDiff) {
            // Remove the element that is out of the window
            let oldBucket = Math.floor(nums[i - indexDiff] / (valueDiff + 1));
            map.delete(oldBucket);
        }
    }
    
    return false;
};

Solution in Java

Java
import java.util.TreeSet;

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (nums == null || nums.length < 2 || indexDiff < 1) {
            return false;
        }

        // TreeSet to maintain a sliding window of the last `indexDiff` elements
        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            long num = (long) nums[i];  // Cast to long to handle large numbers
            
            // Check if there is a number in the set within the range [num - valueDiff, num + valueDiff]
            Long floor = set.floor(num + valueDiff);
            if (floor != null && floor >= num - valueDiff) {
                return true;
            }

            // Add the current number to the set
            set.add(num);

            // Maintain the size of the set to be at most `indexDiff`
            if (i >= indexDiff) {
                set.remove((long) nums[i - indexDiff]);
            }
        }

        // If no such pair was found, return false
        return false;
    }
}

Solution in C#

C#
using System;
using System.Collections.Generic;

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (nums == null || nums.Length < 2 || indexDiff < 1) {
            return false;
        }

        // SortedSet to maintain a sliding window of the last `indexDiff` elements
        SortedSet<long> set = new SortedSet<long>();

        for (int i = 0; i < nums.Length; i++) {
            long num = (long) nums[i];  // Cast to long to avoid overflow issues
            
            // Find the smallest element in the set that is greater than or equal to `num - valueDiff`
            if (set.GetViewBetween(num - valueDiff, num + valueDiff).Count > 0) {
                return true;
            }

            // Add the current number to the set
            set.Add(num);

            // Maintain the size of the set to be at most `indexDiff`
            if (i >= indexDiff) {
                set.Remove((long) nums[i - indexDiff]);
            }
        }

        // If no such pair was found, return false
        return false;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com