Closest Distinct Values in Ranges

Medium

You are given an array values of integers between 1 and 100, and a list of queries ranges, where ranges[i] = [lo, hi]. For each query, look at the slice of the array from index lo to index hi inclusive and find the smallest difference |a - b| over pairs of its elements with **different** values. If every element of the slice is the same (including a slice of a single element), the answer to that query is -1. Return the answers in query order.

Example 1

values=[6, 2, 9, 2, 5], ranges=[[0, 1], [1, 3], [2, 4], [0, 4]] → [4, 7, 3, 1]

[6, 2] → 4; [2, 9, 2] → 7 (the two 2s are equal and do not count); [9, 2, 5] → 3; across the whole array 5 and 6 are closest → 1.

Example 2

values=[3, 3, 3], ranges=[[0, 2], [1, 2]] → [-1, -1]

All numbers are equal, so there is no pair of different values: both answers are -1.

Constraints

2 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 100
1 ≤ len(ranges) ≤ 2 · 10⁴
0 ≤ lo ≤ hi < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table

Similar problems

Sudoku Board Without Clashes Medium Anagram Buckets Medium Zero Out the Crosses Medium Tree From Pre-Order and In-Order Walks Medium Tree From In-Order and Post-Order Walks Medium

Input

values=[6, 2, 9, 2, 5], ranges=[[0, 1], [1, 3], [2, 4], [0, 4]]

Expected

[4, 7, 3, 1]

Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.