Rearrange Into Even Steps

Medium

Call a sequence of at least two numbers evenly spaced if the difference between every two neighbours is the same, as in 2, 5, 8, 11 or 4, 4, 4. You are given an integer array values and two arrays of equal length, starts and ends, describing queries. Query i covers the piece values[starts[i]], …, values[ends[i]], both ends included. Return a list of booleans whose i-th element is True if the numbers in the piece of query i can be reordered into an evenly spaced sequence, and False otherwise.

Example 1

values=[10, 1, 7, 4, 2], starts=[0, 1, 3], ends=[3, 2, 4] → [True, True, True]

[10, 1, 7, 4] rearranges to 1, 4, 7, 10 with step 3. [1, 7] works, as any two numbers do. [4, 2] becomes 2, 4.

Example 2

values=[3, 3, 5, 9, 1], starts=[0, 1, 0], ends=[1, 3, 4] → [True, False, False]

[3, 3] has step 0. [3, 5, 9] gives steps 2 and 4, so no. [3, 3, 5, 9, 1] repeats a value while its spread is non-zero, so it cannot be evenly spaced.

Constraints

2 ≤ len(values) ≤ 500
1 ≤ len(starts) == len(ends) ≤ 500
0 ≤ starts[i] < ends[i] < len(values)
-10⁵ ≤ values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Sorting

Similar problems

Anagram Buckets Medium More Than a Third of the Votes Medium Most Common Values Medium A Subsequence of One Word Only Medium Pairs With a Fixed Gap Medium

Input

values=[10, 1, 7, 4, 2], starts=[0, 1, 3], ends=[3, 2, 4]

Expected

[True, True, True]

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