Leetcode Problem 1906. Minimum Absolute Difference Queries

1906. Minimum Absolute Difference Queries

Leetcode Solutions

Prefix Sums and Cumulative Counters

  1. Initialize a 2D array dp with dimensions (len(nums) + 1) x (max(nums) + 1) filled with zeros.
  2. Populate dp such that dp[i][j] represents the count of number j up to index i-1 in nums.
  3. For each query [li, ri], create a list present of numbers that are present in the subarray by comparing dp[ri+1] and dp[li].
  4. Sort the list present and iterate through it to find the minimum absolute difference between consecutive numbers.
  5. If the list present has less than two elements, the result for the query is -1.
  6. Store the result for each query in a list ans and return it.
UML Thumbnail

Brute Force with Sorting

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...