LeetCode Entry

1630. Arithmetic Subarrays

23.11.2023 medium 2023 kotlin

Query array ranges can form arithmetic sequence

1630. Arithmetic Subarrays medium blog post substack image.png

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(n^2log(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
  }