Contains Duplicate III
Problem
Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
Hint #1
Time complexity O(n log k) - This will give an indication that sorting is involved for k elements.
Hint #2
Use already existing state to evaluate next state - Like, a set of k sorted numbers are only needed to be tracked. When we are processing the next number in array, then we can utilize the existing sorted state and it is not necessary to sort next overlapping set of k numbers again.
Let’s start
As usual , our main goal is to solve the problem and at the same time achieve the best time complexity with minimal space complexity. If you are a beginner to problem solving or trying data structure problems, I suggest you start with a brute force approach and then try to optimize your solution to the best time/space complexity.
Analysis
Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.
- Before jumping into a solution or pseudocode, read the problem statement a couple of times and make sure to understand it well.
- Based on the problem statement, we understand that we need to find two distinct indices i and j such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.
- This time, the problem is a moderate one and not as easy as the Day 1 problem. So I’m going to use the hints provided. I have shared the two hints provided with the problem.
- Based on the first hint, it is understood that we need to sort the elements first and then using the sorted list, we need to find if there are two distinct indices i.e satisfying the provided condition.
- With sorting and iterating through all the array elements, we can achieve the solution by O(n log k) complexity.
- With second hint, we understood that we need to maintain the sorted elements with its state in a data structure in such a way that we don’t have to sort next overlapping elements again.
- From points #4 to #6, we can definitely choose TreeSet (data structure in Java) which will be a best candidate for this problem solution.
- And with all these points, we also got a hint, that this problem falls under "Sliding Window Pattern".
A sliding window is a sublist or subarray that runs over an underlying data structure. The data structure is iterable and ordered, such as an array or a string. At a high level, you can think of it as a subset of the two pointers method.
TreeSet in Java
A TreeSet is a sorted collection that extends the AbstractSet class and implements the NavigableSet interface.
- It stores unique elements
- It doesn’t preserve the insertion order of the elements
- It sorts the elements in ascending order
- It’s not thread-safe
In our solution, we are going to mainly use the below two important methods of Tree Set.
- ceiling() => This method returns the least element in this set greater than or equal to the given element, or null if there is no such element.
- floor() => This method returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
So with all these hints and analysis, let’s start writing our algorithm or pseudocode.
Algorithm | Pseudocode
- Create a TreeSet to store the visited or tracked elements in the array.
- Iterate each element in the array and get the below two values
- low => highest element in the set lesser than the current element nums[i]
- hight => smallest element in the set greater than the current element nums[i]
- if ((low != null && (long) nums[i] - low <= t) || (high != null && (long) high - nums[i] <= t)) return true
This means, we found the two indices that meet the required conditions. - if the conditions are not satisfied, insert the current element nums[i] in the tracking treeSet.
- if we reach (i>=k) element, we can remove the first element, since the two indices which we need to identify has to be within <=k indices.
Let’s start writing the solution.
Loop through the elements in the array. If we find the two indices that matches the required condition by comparing the low & high values in the treeSet. That’s it. That is our answer.
** Given Array contains Duplicate !**
Solution (in Java)
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> visitedSet = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Integer low = visitedSet.floor(nums[i]);
Integer high = visitedSet.ceiling(nums[i]);
if ((low != null && (long) nums[i] - low <= t) || (high != null && (long) high - nums[i] <= t)) {
return true;
}
visitedSet.add(nums[i]);
if (i >= k) {
visitedSet.remove(nums[i - k]);
}
}
return false;
}
}
Complexity
Time Complexity => O(n log k)
Space Complexity => O(k)
Conclusion
This problem is a very good example of Sliding Window Pattern. Do check out more examples in this category for further learning. Since our solution’s complexity is O(n log k) , this is not the best optimized solution. Based on my research and analysis, I found that we could achieve O(n) complexity for this problem using bucket sort. But it’s a little complex solution based on my understanding. So I am leaving it to readers of this article to try out the O(n) bucket sort solution as an exercise. Provide your experience on solving this problem in O(n) complexity in the comment section of this article, if interested. Let’s learn from each other.
References
The LeetCode Problem in this article:
LeetCode September 2021 Challenge
https://leetcode.com/explore/challenge/card/september-leetcoding-challenge/
Thanks for reading this post!
I hope this article is informative and helpful in some way. If it is, please like and share! Follow me on Twitter | LinkedIn for related content.
Happy learning!
Comments
Post a Comment