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

Example 3

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

Follow up