arcbjorn

thoughtbook

RSS Feed

Sunday, February 26, 2023

Contains duplicate III

Leetcode 220 problem.

Typescript

  • Time complexity: O(n)O(n) - n is a length of an array of integers
  • Auxiliary space: O(n)O(n) - constant amount of space
function containsNearbyAlmostDuplicate(
  nums: number[],
  indexDiff: number,
  valueDiff: number,
): boolean {
  let left = 0, right = 1;

  while (right <= nums.length) {
    const currentIndexDiff = Math.abs(left - right);
    const currentValueDiff = Math.abs(nums[left] - nums[right]);

    if (currentIndexDiff <= indexDiff && currentValueDiff <= valueDiff) {
      return true;
    }

    if (right >= nums.length) {
      left++;
      right = left + 1;
    } else {
      right++;

      if (currentIndexDiff > indexDiff) {
        left++;
        right = left + 1;
      }
    }
  }
  return false;
}
Creative Commons Licence