Minimum Absolute Difference Queries — LeetCode 1906 Python Solution
MediumArrayHash Table
- Problem
- #1906
- Pattern
- Hash Map
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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:
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1906. Minimum Absolute Difference Queries is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1906. Minimum Absolute Difference Queries?
- LeetCode 1906. Minimum Absolute Difference Queries is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1906. Minimum Absolute Difference Queries?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1906. Minimum Absolute Difference Queries?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1906. Minimum Absolute Difference Queries cover?
- LeetCode 1906. Minimum Absolute Difference Queries is tagged Array and Hash Table on LeetCode.