Skip to content

1630. Arithmetic Subarrays 👍

  • Time: $O(mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l,
                                        vector<int>& r) {
    vector<bool> ans;

    for (int i = 0; i < l.size(); ++i)
      ans.push_back(isArithmetic(nums, l[i], r[i]));

    return ans;
  }

 private:
  bool isArithmetic(vector<int>& nums, int l, int r) {
    if (r - l < 2)
      return true;

    unordered_set<int> numsSet;
    int mn = INT_MAX;
    int mx = INT_MIN;

    for (int i = l; i <= r; ++i) {
      mn = min(mn, nums[i]);
      mx = max(mx, nums[i]);
      numsSet.insert(nums[i]);
    }

    if ((mx - mn) % (r - l) != 0)
      return false;

    const int interval = (mx - mn) / (r - l);

    for (int k = 1; k <= r - l; ++k)
      if (!numsSet.contains(mn + k * interval))
        return false;

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
    List<Boolean> ans = new ArrayList<>();

    for (int i = 0; i < l.length; ++i)
      ans.add(isArithmetic(nums, l[i], r[i]));

    return ans;
  }

  private boolean isArithmetic(int[] nums, int l, int r) {
    if (r - l < 2)
      return true;

    int mn = Integer.MAX_VALUE;
    int mx = Integer.MIN_VALUE;
    Set<Integer> numsSet = new HashSet<>();

    for (int i = l; i <= r; ++i) {
      mn = Math.min(mn, nums[i]);
      mx = Math.max(mx, nums[i]);
      numsSet.add(nums[i]);
    }

    if ((mx - mn) % (r - l) != 0)
      return false;

    final int interval = (mx - mn) / (r - l);

    for (int k = 1; k <= r - l; ++k)
      if (!numsSet.contains(mn + k * interval))
        return false;

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def checkArithmeticSubarrays(
      self,
      nums: list[int],
      l: list[int],
      r: list[int],
  ) -> list[bool]:
    return [self._isArithmetic(nums, a, b) for a, b in zip(l, r)]

  def _isArithmetic(self, nums: list[int], l: int, r: int) -> bool:
    if r - l < 2:
      return True

    numsSet = set()
    mn = math.inf
    mx = -math.inf

    for i in range(l, r+1):
      mn = min(mn, nums[i])
      mx = max(mx, nums[i])
      numsSet.add(nums[i])

    if (mx - mn) % (r - l) != 0:
      return False

    interval = (mx - mn) // (r - l)
    return all(mn + k * interval in numsSet
               for k in range(1, r - l + 1))