Skip to content

2145. Count the Hidden Sequences 👍

Approach 1: 1D Prefix Sum

  • 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) {
    // Starts from 0, so prefix[0] = 0.
    // Changing prefix[0] to any other number doesn't affect the answer.
    vector<long> prefix(differences.size() + 1);

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

    const long mx = ranges::max(prefix);
    const long mn = ranges::min(prefix);
    return max(0L, (upper - lower) - (mx - mn) + 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) {
    // Starts from 0, so prefix[0] = 0.
    // Changing prefix[0] to any other number doesn't affect the answer.
    long[] prefix = new long[differences.length + 1];

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

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

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

Approach 2: Constant Prefix Sum

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int numberOfArrays(vector<int>& differences, int lower, int upper) {
    long prefix = 0;
    long mn = 0;  // Starts from 0.
    long mx = 0;  // Starts from 0.

    for (const int d : differences) {
      prefix += d;
      mn = min(mn, prefix);
      mx = max(mx, prefix);
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int numberOfArrays(int[] differences, int lower, int upper) {
    long prefix = 0;
    long mn = 0; // Starts from 0.
    long mx = 0; // Starts from 0.

    for (final int d : differences) {
      prefix += d;
      mn = Math.min(mn, prefix);
      mx = Math.max(mx, prefix);
    }

    return (int) Math.max(0L, (upper - lower) - (mx - mn) + 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def numberOfArrays(
      self,
      differences: list[int],
      lower: int,
      upper: int,
  ) -> int:
    prefix = 0
    mn = 0  # Starts from 0.
    mx = 0  # Starts from 0.

    for d in differences:
      prefix += d
      mn = min(mn, prefix)
      mx = max(mx, prefix)

    return max(0, (upper - lower) - (mx - mn) + 1)