{"id":6517,"date":"2020-03-21T16:20:50","date_gmt":"2020-03-21T23:20:50","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6517"},"modified":"2020-03-21T22:29:17","modified_gmt":"2020-03-22T05:29:17","slug":"leetcode-1385-find-the-distance-value-between-two-arrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-1385-find-the-distance-value-between-two-arrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1385. Find the Distance Value Between Two Arrays"},"content":{"rendered":"\n

Given two integer arrays arr1<\/code> and arr2<\/code>, and the integer d<\/code>, return the distance value between the two arrays<\/em>.<\/p>\n\n\n\n

The distance value is defined as the number of elements arr1[i]<\/code> such that there is not any element arr2[j]<\/code> where |arr1[i]-arr2[j]| <= d<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2\nOutput:<\/strong> 2\nExplanation:<\/strong> \nFor arr1[0]=4 we have: \n|4-10|=6 > d=2 \n|4-9|=5 > d=2 \n|4-1|=3 > d=2 \n|4-8|=4 > d=2 \nFor arr1[1]=5 we have: \n|5-10|=5 > d=2 \n|5-9|=4 > d=2 \n|5-1|=4 > d=2 \n|5-8|=3 > d=2\nFor arr1[2]=8 we have:\n|8-10|=2 <= d=2<\/strong>\n|8-9|=1 <= d=2<\/strong>\n|8-1|=7 > d=2\n|8-8|=0 <= d=2<\/strong>\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3\nOutput:<\/strong> 2\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr1.length, arr2.length <= 500<\/code><\/li>
  • -10^3 <= arr1[i], arr2[j] <= 10^3<\/code><\/li>
  • 0 <= d <= 100<\/code><\/li><\/ul>\n\n\n\n
    Solution 1:  All pairs<\/strong><\/h2>\n\n\n\n
    Time complexity: O(m*n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findTheDistanceValue(vector& arr1, vector& arr2, int d) {    \n    int ans = 0;\n    for (int x : arr1) {\n      bool flag = true;\n      for (int y : arr2)\n        if (abs(x - y) <= d) {\n          flag = false;\n          break;\n        }\n      ans += flag;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    \n
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\nclass Solution:\n  def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n    return sum(all(abs(x - y) > d for y in arr2) for x in arr1)\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Two Pointers<\/strong><\/h2>\n\n\n\n
    Sort arr1 in ascending order and sort arr2 in descending order.
    Time complexity: O(mlogm + nlogn + m + n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findTheDistanceValue(vector& arr1, vector& arr2, int d) {    \n    sort(begin(arr1), end(arr1));\n    sort(rbegin(arr2), rend(arr2));\n    int ans = 0;\n    for (int a : arr1) {\n      while (arr2.size() && arr2.back() < a - d)\n        arr2.pop_back();\n      ans += arr2.empty() || arr2.back() > a + d;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 3: Binary Search<\/strong><\/h2>\n\n\n\n
    Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter<\/p>\n\n\n\n
    Time complexity: O(mlogm + nlogm)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findTheDistanceValue(vector& arr1, vector& arr2, int d) {    \n    sort(begin(arr2), end(arr2));\n    int ans = 0;\n    for (int a : arr1) {\n      auto it1 = lower_bound(begin(arr2), end(arr2), a - d);\n      auto it2 = upper_bound(begin(arr2), end(arr2), a + d);\n      if (it1 == it2) ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays. The distance value is defined as the number of elements arr1[i] such that there…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[52,106,222,23,175],"class_list":["post-6517","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-binary-search","tag-brute-force","tag-easy","tag-sort","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6517","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6517"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6517\/revisions"}],"predecessor-version":[{"id":6522,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6517\/revisions\/6522"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}