MediumNo. 1906
Minimum Absolute Difference Queries — LeetCode 1906 Python Solution
- Pattern
- Hash Map
- Topics
- Array, Hash Table
- 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
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 1200 | Minimum Absolute Difference | Easy |
| 1912 | Design Movie Rental System | Hard |
| 0001 | Two Sum | Easy |
| 0036 | Valid Sudoku | Medium |
| 0037 | Sudoku Solver | Hard |
| 0041 | First Missing Positive | Hard |
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.