arcbjorn

thoughtbook

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