{"id":8590,"date":"2021-08-15T16:26:14","date_gmt":"2021-08-15T23:26:14","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8590"},"modified":"2021-08-15T16:27:18","modified_gmt":"2021-08-15T23:27:18","slug":"leetcode-1906-minimum-absolute-difference-queries","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1906-minimum-absolute-difference-queries\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1906. Minimum Absolute Difference Queries"},"content":{"rendered":"\n<p>The&nbsp;<strong>minimum absolute difference<\/strong>&nbsp;of an array&nbsp;<code>a<\/code>&nbsp;is defined as the&nbsp;<strong>minimum value<\/strong>&nbsp;of&nbsp;<code>|a[i] - a[j]|<\/code>, where&nbsp;<code>0 &lt;= i &lt; j &lt; a.length<\/code>&nbsp;and&nbsp;<code>a[i] != a[j]<\/code>. If all elements of&nbsp;<code>a<\/code>&nbsp;are the&nbsp;<strong>same<\/strong>, the minimum absolute difference is&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the minimum absolute difference of the array&nbsp;<code>[5,<u>2<\/u>,<u>3<\/u>,7,2]<\/code>&nbsp;is&nbsp;<code>|2 - 3| = 1<\/code>. Note that it is not&nbsp;<code>0<\/code>&nbsp;because&nbsp;<code>a[i]<\/code>&nbsp;and&nbsp;<code>a[j]<\/code>&nbsp;must be different.<\/li><\/ul>\n\n\n\n<p>You are given an integer array&nbsp;<code>nums<\/code>&nbsp;and the array&nbsp;<code>queries<\/code>&nbsp;where&nbsp;<code>queries[i] = [l<sub>i<\/sub>, r<sub>i<\/sub>]<\/code>. For each query&nbsp;<code>i<\/code>, compute the&nbsp;<strong>minimum absolute difference<\/strong>&nbsp;of the&nbsp;<strong>subarray<\/strong>&nbsp;<code>nums[l<sub>i<\/sub>...r<sub>i<\/sub>]<\/code>&nbsp;containing the elements of&nbsp;<code>nums<\/code>&nbsp;between the&nbsp;<strong>0-based<\/strong>&nbsp;indices&nbsp;<code>l<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>r<sub>i<\/sub><\/code>&nbsp;(<strong>inclusive<\/strong>).<\/p>\n\n\n\n<p>Return&nbsp;<em>an&nbsp;<strong>array<\/strong>&nbsp;<\/em><code>ans<\/code>&nbsp;<em>where<\/em>&nbsp;<code>ans[i]<\/code>&nbsp;<em>is the answer to the<\/em>&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;<em>query<\/em>.<\/p>\n\n\n\n<p>A&nbsp;<strong>subarray<\/strong>&nbsp;is a contiguous sequence of elements in an array.<\/p>\n\n\n\n<p>The value of&nbsp;<code>|x|<\/code>&nbsp;is defined as:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>x<\/code>&nbsp;if&nbsp;<code>x &gt;= 0<\/code>.<\/li><li><code>-x<\/code>&nbsp;if&nbsp;<code>x &lt; 0<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]\n<strong>Output:<\/strong> [2,1,4,1]\n<strong>Explanation:<\/strong> The queries are processed as follows:\n- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.\n- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.\n- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.\n- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]\n<strong>Output:<\/strong> [-1,1,1,3]\n<strong>Explanation: <\/strong>The queries are processed as follows:\n- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the\n  elements are the same.\n- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.\n- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.\n- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= nums.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 100<\/code><\/li><li><code>1 &lt;= queries.length &lt;= 2&nbsp;* 10<sup>4<\/sup><\/code><\/li><li><code>0 &lt;= l<sub>i<\/sub>&nbsp;&lt; r<sub>i<\/sub>&nbsp;&lt; nums.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<p>Since the value range of num is quiet small [1~100], we can store the indices for each value. <br>[2, 1, 2, 2, 3] =&gt; {1: [1], 2: [0, 2, 3]: 3: [4]}.<\/p>\n\n\n\n<p>For each query, we try all possible value b. Check whether b is the query range using binary search, we also keep tracking the previous available value a, ans will be min{b &#8211; a}.<\/p>\n\n\n\n<p>Time complexity: O(n + q * 100 * log(n))<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {    \n    constexpr int kMax = 100;\n    const int n = nums.size();\n    vector<vector<int>> idx(kMax + 1);\n    for (int i = 0; i < n; ++i)\n      idx[nums[i]].push_back(i);\n    vector<int> ans;\n    for (const auto& q: queries) {      \n      int diff = INT_MAX;\n      for (int a = 0, b = 1; b <= kMax; ++b) {\n        auto it = lower_bound(begin(idx[b]), end(idx[b]), q[0]);\n        if (it == end(idx[b]) || *it > q[1]) continue;\n        if (a) diff = min(diff, b - a);\n        a = b;\n      }\n      ans.push_back(diff == INT_MAX ? -1 : diff);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>The&nbsp;minimum absolute difference&nbsp;of an array&nbsp;a&nbsp;is defined as the&nbsp;minimum value&nbsp;of&nbsp;|a[i] &#8211; a[j]|, where&nbsp;0 &lt;= i &lt; j &lt; a.length&nbsp;and&nbsp;a[i] != a[j]. If all elements of&nbsp;a&nbsp;are the&nbsp;same,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177,98],"class_list":["post-8590","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","tag-range-query","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8590","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=8590"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8590\/revisions"}],"predecessor-version":[{"id":8593,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8590\/revisions\/8593"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8590"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8590"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}