Find the Distance Value Between Two Arrays (LeetCode 1385)

by linkjobai

HTML

<p>Count the elements x in arr1 for which no element y in arr2 satisfies <code>|x - y| <= d</code>.</p>
<h2>From O(n*m) to O((n+m) log m)</h2>
<p>The nested loop is fine for the given limits, but sorting arr2 lets you find, for each x, whether any value sits in the window <code>[x-d, x+d]</code> with one binary search.</p>
<pre><code class="language-python">from bisect import bisect_left

def find_the_distance_value(arr1, arr2, d):
    arr2.sort()
    count = 0
    for x in arr1:
        i = bisect_left(arr2, x - d)
        if i == len(arr2) or arr2[i] > x + d:
            count += 1
    return count</code></pre>
<h2>Explaining the window</h2>
<p>bisect_left gives the first value at least x-d. If it is past the end or larger than x+d, nothing lies within distance d. Saying this in one sentence keeps the interviewer with you.</p>
<p>More interview walkthroughs and practice tools at <a href="https://www.linkjob.ai/">www.linkjob.ai</a>.</p>
<p><em>Disclosure: I work on Linkjob AI.</em></p>