Contains Duplicate III

This problem asks us to find a pair of indices (i, j) in the array nums where the absolute differences between the indices and the corresponding values meet certain constraints.

Here’s how you can solve this problem using a sliding window and a sorted set:

  1. Initialize a Sorted Set: We will use a sorted set to maintain a window of size indexDiff.
  2. Iterate through the Array: For each number, we will:
    • Search for Close Values: Look in the sorted set for a value that is close enough to the current number according to valueDiff.
    • Add Current Value: Add the current value to the sorted set.
    • Maintain Window Size: If the size of the sorted set exceeds indexDiff, remove the oldest value to keep the window size fixed.
  3. Return Result: If a suitable pair is found, return true. Otherwise, return false.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from sortedcontainers import SortedList
from typing import List

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        sorted_nums = SortedList()

        for i in range(len(nums)):
            # Check if there's a nearby value that's close enough
            pos = sorted_nums.bisect_left(nums[i] - valueDiff)
            if pos < len(sorted_nums) and abs(sorted_nums[pos] - nums[i]) <= valueDiff:
                return True

            # Add current value to the sorted set
            sorted_nums.add(nums[i])

            # Maintain the window size by removing the oldest value if necessary
            if len(sorted_nums) > indexDiff:
                sorted_nums.remove(nums[i - indexDiff])

        return False

Here, we used SortedList from the sortedcontainers library, which provides logarithmic time complexity for insertion and removal operations. The overall time complexity of this code is O(n log k), where n is the length of the array, and k is the value of indexDiff. The space complexity is O(k).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        # Using a SortedList to store the window elements
        sorted_window = SortedList()

        # Iterate through the nums list
        for i in range(len(nums)):
            # If the window size exceeds indexDiff, remove the leftmost element
            if i > indexDiff:
                sorted_window.remove(nums[i - indexDiff - 1])

            # Find the first number that is greater or equal to nums[i] - valueDiff in the window
            pos1 = sorted_window.bisect_left(nums[i] - valueDiff)

            # If the number found in the window is within valueDiff of nums[i], return True
            if pos1 != len(sorted_window) and abs(sorted_window[pos1] - nums[i]) <= valueDiff:
                return True

            # Add the current number to the window
            sorted_window.add(nums[i])

        return False

Identifying Problem Isomorphism

“Contains Duplicate III” can be mapped to “Sliding Window Median”.

“Contains Duplicate III” involves checking if there exist two indices i and j such that the absolute difference of i and j is at most k and the absolute difference between nums[i] and nums[j] is at most t. This problem typically requires efficient querying of the range of a value in a given window (a range query data structure).

“Sliding Window Median” requires maintaining a dynamic list of numbers and quickly finding the median after every addition or removal. Efficient querying and updating of a range of values is also needed here, similar to the “Contains Duplicate III” problem.

Both problems involve maintaining a sliding window and executing operations that can be optimized using data structures like balanced binary search trees, heaps, or buckets.

“Contains Duplicate III” is simpler than “Sliding Window Median” because it only requires checking for the existence of a pair of elements within a certain range, while the “Sliding Window Median” problem requires maintaining the entire list and calculating the median after each operation.

10 Prerequisite LeetCode Problems

“Contains Duplicate III” is a problem that requires understanding of array manipulation, window sliding technique and the concept of buckets. Here are 10 problems to prepare for it:

  1. Two Sum: Basic problem for understanding array manipulation and target search.

  2. Contains Duplicate: This problem introduces the concept of finding duplicates in an array.

  3. Contains Duplicate II: This problem builds upon the previous one by adding the condition of the distance between the duplicate numbers.

  4. Sliding Window Maximum: This problem is a great introduction to the sliding window concept.

  5. Maximum Subarray: Understanding the concept of subarrays.

  6. Minimum Size Subarray Sum: This problem introduces the sliding window concept with the task to find the subarray that meets a certain condition.

  7. 3Sum: This problem introduces the concept of three-pointer technique which is a step further in array manipulation.

  8. Find All Numbers Disappeared in an Array: A step further in complex array manipulation.

  9. Subarray Product Less Than K: This problem also involves sliding window concept with a multiplication operation twist.

  10. Subarray Sum Equals K: This problem introduces the concept of maintaining a sum while traversing the array.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

Can you help me with finding the isomorphism for this problem?

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0: return False # edge case 
        
        seen = {}
        for i, x in enumerate(nums): 
            bkt = x//(t+1)
            if bkt in seen and i - seen[bkt][0] <= k: return True 
            if bkt-1 in seen and i - seen[bkt-1][0] <= k and abs(x - seen[bkt-1][1]) <= t: return True 
            if bkt+1 in seen and i - seen[bkt+1][0] <= k and abs(x - seen[bkt+1][1]) <= t: return True 
            seen[bkt] = (i, x) 
        return False

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

Language Agnostic Coding Drills

Here are the smallest units of learning and steps to combine them into the final solution.

  1. Understanding Basic Data Types and Variables: Understand how to use integers and lists in a programming language. Learn how to iterate through a list.

  2. Conditional Statements: Learn how to write and understand if statements to control the flow of a program.

  3. Arithmetic Operations: Learn about basic arithmetic operations like addition, subtraction, and division. Understand integer division and modulus.

  4. Enumerate Function: Understand how to use the enumerate function to get both the index and value of items in a list.

  5. Dictionary Usage: Learn about dictionaries (or similar data structures in other languages), how to add items to a dictionary, and how to check if a key exists in a dictionary.

  6. Abs Function: Understand the abs function which returns the absolute value of a number.

  7. Understanding Loops: Understand how to use loops to iterate over the list of numbers.

Step-by-step problem-solving approach:

  1. Understand the problem statement and input parameters.
  2. Handle edge case where t is less than 0. Return False in this case as it’s not possible to have a difference less than 0.
  3. Initialize an empty dictionary seen.
  4. Iterate over the list of numbers using enumerate to get both index i and value x.
  5. Compute bkt, which is the bucket id of the current number x using integer division by (t+1).
  6. Check if bkt is in seen dictionary and if the difference in indices is less than or equal to k. If true, return True.
  7. Similarly, check if bkt-1 or bkt+1 exist in seen dictionary and their conditions hold. If true, return True.
  8. If none of the above conditions are met, add bkt to seen dictionary with its value being the tuple (i, x).
  9. If we iterate through all numbers and find no almost duplicate, return False.

Targeted Drills in Python

Here are the coding drills in Python:

  1. Understanding Basic Data Types and Variables:

    1
2
3
4
5
6
7

    # Create an integer variable
a = 5
# Create a list
nums = [1, 2, 3, 4, 5]
# Iterate through a list
for num in nums:
    print(num)

  2. Conditional Statements:

    1
2
3
4
5
6

    # Using if-else statement
a = 10
if a > 5:
    print("Greater than 5")
else:
    print("Less than or equal to 5")

  3. Arithmetic Operations:

    1
2
3
4
5
6
7

    # Basic arithmetic operations
a = 10
b = 5
sum = a + b
difference = a - b
quotient = a // b
modulus = a % b

  4. Enumerate Function:

    1
2
3
4

    # Using enumerate function
nums = [10, 20, 30, 40, 50]
for i, num in enumerate(nums):
    print(f"Index: {i}, Value: {num}")

  5. Dictionary Usage:

    1
2
3
4
5
6
7

    # Using a dictionary
dictionary = {}
# Adding items to a dictionary
dictionary['key1'] = 'value1'
# Checking if a key exists in a dictionary
if 'key1' in dictionary:
    print("key1 exists in dictionary")

  6. Abs Function:

    1
2
3

    # Using abs function
a = -10
print(abs(a))  # Outputs: 10

  7. Understanding Loops:

    1
2
3

    # Using a for loop
for i in range(5):
    print(i)

After mastering these concepts and drills, you can combine these skills to solve the given problem. Here you would utilize a for-loop with enumerate to iterate over the nums list, use dictionary operations to store and retrieve data, use arithmetic operations to calculate bkt, and use if-conditions to check the necessary conditions before returning a result.