Skip to content

2145. Count the Hidden Sequences 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int numberOfArrays(vector<int>& differences, int lower, int upper) {
    // Start from 0, so prefix[0] = 0
    // Changing prefix[0] to any other number doesn't affect the ans
    vector<long> prefix(differences.size() + 1);

    for (int i = 0; i < differences.size(); ++i)
      prefix[i + 1] += prefix[i] + differences[i];

    const long maxi = *max_element(prefix.begin(), prefix.end());
    const long mini = *min_element(prefix.begin(), prefix.end());
    return max(0L, (upper - lower) - (maxi - mini) + 1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int numberOfArrays(int[] differences, int lower, int upper) {
    // Start from 0, so prefix[0] = 0
    // Changing prefix[0] to any other number doesn't affect the ans
    long[] prefix = new long[differences.length + 1];

    for (int i = 0; i < differences.length; ++i)
      prefix[i + 1] += prefix[i] + differences[i];

    final long max = Arrays.stream(prefix).max().getAsLong();
    final long min = Arrays.stream(prefix).min().getAsLong();
    return (int) Math.max(0L, (upper - lower) - (max - min) + 1);
  }
}

1
2
3
4
class Solution:
  def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
    prefix = [0] + list(itertools.accumulate(differences))
    return max(0, (upper - lower) - (max(prefix) - min(prefix)) + 1)