Welcome to Subscribe On Youtube
1906. Minimum Absolute Difference Queries
Description
The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.
- For example, the minimum absolute difference of the array
[5,2,3,7,2]is|2 - 3| = 1. Note that it is not0becausea[i]anda[j]must be different.
You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive).
Return an array ans where ans[i] is the answer to the ith query.
A subarray is a contiguous sequence of elements in an array.
The value of |x| is defined as:
xifx >= 0.-xifx < 0.
Example 1:
Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]] Output: [2,1,4,1] Explanation: The queries are processed as follows: - queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2. - queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1. - queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4. - queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.
Example 2:
Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]] Output: [-1,1,1,3] Explanation: The queries are processed as follows: - queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the elements are the same. - queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1. - queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1. - queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 1001 <= queries.length <= 2 * 1040 <= li < ri < nums.length
Solutions
-
class Solution { public int[] minDifference(int[] nums, int[][] queries) { int m = nums.length, n = queries.length; int[][] preSum = new int[m + 1][101]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= 100; ++j) { int t = nums[i - 1] == j ? 1 : 0; preSum[i][j] = preSum[i - 1][j] + t; } } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int left = queries[i][0], right = queries[i][1] + 1; int t = Integer.MAX_VALUE; int last = -1; for (int j = 1; j <= 100; ++j) { if (preSum[right][j] > preSum[left][j]) { if (last != -1) { t = Math.min(t, j - last); } last = j; } } if (t == Integer.MAX_VALUE) { t = -1; } ans[i] = t; } return ans; } } -
class Solution { public: vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) { int m = nums.size(), n = queries.size(); int preSum[m + 1][101]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= 100; ++j) { int t = nums[i - 1] == j ? 1 : 0; preSum[i][j] = preSum[i - 1][j] + t; } } vector<int> ans(n); for (int i = 0; i < n; ++i) { int left = queries[i][0], right = queries[i][1] + 1; int t = 101; int last = -1; for (int j = 1; j <= 100; ++j) { if (preSum[right][j] > preSum[left][j]) { if (last != -1) { t = min(t, j - last); } last = j; } } if (t == 101) { t = -1; } ans[i] = t; } return ans; } }; -
class Solution: def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]: m, n = len(nums), len(queries) pre_sum = [[0] * 101 for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, 101): t = 1 if nums[i - 1] == j else 0 pre_sum[i][j] = pre_sum[i - 1][j] + t ans = [] for i in range(n): left, right = queries[i][0], queries[i][1] + 1 t = inf last = -1 for j in range(1, 101): if pre_sum[right][j] - pre_sum[left][j] > 0: if last != -1: t = min(t, j - last) last = j if t == inf: t = -1 ans.append(t) return ans -
func minDifference(nums []int, queries [][]int) []int { m, n := len(nums), len(queries) preSum := make([][101]int, m+1) for i := 1; i <= m; i++ { for j := 1; j <= 100; j++ { t := 0 if nums[i-1] == j { t = 1 } preSum[i][j] = preSum[i-1][j] + t } } ans := make([]int, n) for i := 0; i < n; i++ { left, right := queries[i][0], queries[i][1]+1 t, last := 101, -1 for j := 1; j <= 100; j++ { if preSum[right][j]-preSum[left][j] > 0 { if last != -1 { if t > j-last { t = j - last } } last = j } } if t == 101 { t = -1 } ans[i] = t } return ans } -
function minDifference(nums: number[], queries: number[][]): number[] { let m = nums.length, n = queries.length; let max = 100; // let max = Math.max(...nums); let pre: number[][] = []; pre.push(new Array(max + 1).fill(0)); for (let i = 0; i < m; ++i) { let num = nums[i]; pre.push(pre[i].slice()); pre[i + 1][num] += 1; } let ans = []; for (let [left, right] of queries) { let last = -1; let min = Infinity; for (let j = 1; j < max + 1; ++j) { if (pre[left][j] < pre[right + 1][j]) { if (last != -1) { min = Math.min(min, j - last); } last = j; } } ans.push(min == Infinity ? -1 : min); } return ans; }