23.11.2023
1630. Arithmetic Subarrays medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/414
Problem TLDR
Query array ranges can form arithmetic sequence
Intuition
Given the problem contraints, the naive solution would work: just sort the subarray and check the diff
.
Approach
We can use PriorityQueue
Complexity
Time complexity:
O(n2log(n))Space complexity:
O(n)
Code
fun checkArithmeticSubarrays(nums: IntArray, l: IntArray, r: IntArray) =
List(l.size) { ind ->
val pq = PriorityQueue<Int>()
for (i in l[ind]..r[ind]) pq.add(nums[i])
val diff = -pq.poll() + pq.peek()
var prev = pq.poll()
while (pq.isNotEmpty()) {
if (pq.peek() - prev != diff) return@List false
prev = pq.poll()
}
true
}