Skip to content

3468. Find the Number of Copy Arrays 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int countArrays(vector<int>& original, vector<vector<int>>& bounds) {
    int mn = bounds[0][0];
    int mx = bounds[0][1];

    for (int i = 1; i < original.size(); ++i) {
      const int diff = original[i] - original[i - 1];
      mn = max(mn + diff, bounds[i][0]);
      mx = min(mx + diff, bounds[i][1]);
    }

    return max(0, mx - mn + 1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int countArrays(int[] original, int[][] bounds) {
    int mn = bounds[0][0];
    int mx = bounds[0][1];

    for (int i = 1; i < original.length; ++i) {
      final int diff = original[i] - original[i - 1];
      mn = Math.max(mn + diff, bounds[i][0]);
      mx = Math.min(mx + diff, bounds[i][1]);
    }

    return Math.max(0, mx - mn + 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def countArrays(self, original: list[int], bounds: list[list[int]]) -> int:
    mn, mx = bounds[0]

    for i in range(1, len(original)):
      diff = original[i] - original[i - 1]
      mn = max(mn + diff, bounds[i][0])
      mx = min(mx + diff, bounds[i][1])

    return max(0, mx - mn + 1)