17 Jan 2024•PHP•Hard

Contains Duplicate III

check if there exist two indices with value difference ≤ valueDiff and index difference ≤ indexDiff using sliding window with sorted array.

View original LeetCode question

maintain a sliding window of size indexDiff using a sorted array. for each new element, binary search to find insertion position, then check adjacent elements for value difference ≤ valueDiff.

when window exceeds indexDiff, remove the oldest element using binary search. the sorted window allows efficient range queries.

key insight

by keeping the window sorted, we can quickly check if any element within valueDiff exists. binary search gives O(log k) insertion and removal where k is window size.

complexity

O(n log k) time where n is array length and k is indexDiff. O(k) space for the sorted window.

Solution files

PHP•contains-duplicate-3/solution.php
class Solution {

function containsNearbyAlmostDuplicate($nums, $indexDiff, $valueDiff) {
    $window = [];

    for ($i = class="syntax-number">0; $i < count($nums); $i++) {
        $pos = $this->binarySearch($window, $nums[$i]);

        if ($pos < count($window) && abs($window[$pos] - $nums[$i]) <= $valueDiff) {
            return true;
        }
        if ($pos > class="syntax-number">0 && abs($window[$pos - class="syntax-number">1] - $nums[$i]) <= $valueDiff) {
            return true;
        }

        array_splice($window, $pos, class="syntax-number">0, $nums[$i]);

        if (count($window) > $indexDiff) {
            $removeIndex = $this->binarySearch($window, $nums[$i - $indexDiff]);
            array_splice($window, $removeIndex, class="syntax-number">1);
        }
    }

    return false;
}

private function binarySearch(&$arr, $num) {
    $left = class="syntax-number">0;
    $right = count($arr) - class="syntax-number">1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, class="syntax-number">2);
        if ($arr[$mid] === $num) {
            return $mid;
        } elseif ($arr[$mid] < $num) {
            $left = $mid + class="syntax-number">1;
        } else {
            $right = $mid - class="syntax-number">1;
        }
    }

    return $left;
}
}