220. Contains Duplicate III

Description

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Constraints

• 0 <= nums.length <= 2 * 104

• -231 <= nums[i] <= 231 - 1

• 0 <= k <= 104

• 0 <= t <= 231 - 1

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums == null || nums.length < 2 || k < 0 || t < 0) {
            return false;
        }
        int n = nums.length;
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                if(Math.abs(1L * nums[i]-nums[j]) <= t && (j-i) <= k) {
                    return true;
                }
            }
        }
        return false;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums == null || nums.length < 2 || k < 0 || t < 0) {
            return false;
        }
        if(k >= 10000 && t == 0) {
            return false;
        }
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < i+k+1; j++) {
                if(j >= n) break;
                if((long)nums[i]-(long)nums[j] > (long)Integer.MAX_VALUE || 
                    (long)nums[j]-(long)nums[i] > (long)Integer.MAX_VALUE) {
                    continue;
                }
                if(Math.abs(nums[i]-nums[j]) <= t) {
                    return true;
                }
            }
        }
        return false;
    }
}

Follow up