Skip to content

2970. Count the Number of Incremovable Subarrays I

  • Time: $O(n\log n)$
  • Space: $O(1)$
 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
class Solution {
 public:
  int incremovableSubarrayCount(vector<int>& nums) {
    const int n = nums.size();
    const int startIndex = getStartIndexOfSuffix(nums);
    // If the complete array is strictly increasing, the total number of ways we
    // can remove elements equals the total number of possible subarrays.
    if (startIndex == 0)
      return n * (n + 1) / 2;

    // The valid removals starting from nums[0] include nums[0..startIndex - 1],
    // nums[0..startIndex], ..., nums[0..n).
    int ans = n - startIndex + 1;

    // Enumerate each prefix subarray that is strictly increasing.
    for (int i = 0; i < startIndex; ++i) {
      if (i > 0 && nums[i] <= nums[i - 1])
        break;
      // Since nums[0..i] is strictly increasing, find the first index j in
      // nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
      // will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
      ans += nums.end() -
             upper_bound(nums.begin() + startIndex, nums.end(), nums[i]) + 1;
    }

    return ans;
  }

 private:
  // Returns the start index i of the suffix subarray such that nums[i..n) is
  // strictly increasing.
  int getStartIndexOfSuffix(const vector<int>& nums) {
    for (int i = nums.size() - 2; i >= 0; --i)
      if (nums[i] >= nums[i + 1])
        return i + 1;
    return 0;
  }
};

 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
40
class Solution {
  public int incremovableSubarrayCount(int[] nums) {
    final int n = nums.length;
    final int startIndex = getStartIndexOfSuffix(nums);
    // If the complete array is strictly increasing, the total number of ways we
    // can remove elements equals the total number of possible subarrays.
    if (startIndex == 0)
      return n * (n + 1) / 2;

    // The valid removals starting from nums[0] include nums[0..startIndex - 1],
    // nums[0..startIndex], ..., nums[0..n).
    int ans = n - startIndex + 1;

    // Enumerate each prefix subarray that is strictly increasing.
    for (int i = 0; i < startIndex; ++i) {
      if (i > 0 && nums[i] <= nums[i - 1])
        break;
      // Since nums[0..i] is strictly increasing, find the first index j in
      // nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
      // will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
      ans += n - firstGreater(nums, startIndex, nums[i]) + 1;
    }

    return ans;
  }

  // Returns the start index i of the suffix subarray such that nums[i..n) is
  // strictly increasing.
  private int getStartIndexOfSuffix(int[] nums) {
    for (int i = nums.length - 2; i >= 0; --i)
      if (nums[i] >= nums[i + 1])
        return i + 1;
    return 0;
  }

  private int firstGreater(int[] A, int startIndex, int target) {
    final int i = Arrays.binarySearch(A, startIndex, A.length, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}

 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
class Solution:
  def incremovableSubarrayCount(self, nums: list[int]) -> int:
    n = len(nums)
    startIndex = self._getStartIndexOfSuffix(nums)
    # If the complete array is strictly increasing, the total number of ways we
    # can remove elements equals the total number of possible subarrays.
    if startIndex == 0:
      return n * (n + 1) // 2

    # The valid removals starting from nums[0] include nums[0..startIndex - 1],
    # nums[0..startIndex], ..., nums[0..n).
    ans = n - startIndex + 1

    # Enumerate each prefix subarray that is strictly increasing.
    for i in range(startIndex):
      if i > 0 and nums[i] <= nums[i - 1]:
        break
      # Since nums[0..i] is strictly increasing, find the first index j in
      # nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
      # will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
      ans += n - bisect.bisect_right(nums, nums[i], startIndex) + 1

    return ans

  def _getStartIndexOfSuffix(self, nums: list[int]) -> int:
    for i in range(len(nums) - 2, -1, -1):
      if nums[i] >= nums[i + 1]:
        return i + 1
    return 0

Approach 2: Two Pointers

  • Time: $O(n)$
  • 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:
  int incremovableSubarrayCount(vector<int>& nums) {
    const int n = nums.size();
    const int startIndex = getStartIndexOfSuffix(nums);
    // If the complete array is strictly increasing, the total number of ways we
    // can remove elements equals the total number of possible subarrays.
    if (startIndex == 0)
      return n * (n + 1) / 2;

    // The valid removals starting from nums[0] include nums[0..startIndex - 1],
    // nums[0..startIndex], ..., nums[0..n).
    int ans = n - startIndex + 1;

    // Enumerate each prefix subarray that is strictly increasing.
    for (int i = 0, j = startIndex; i < startIndex; ++i) {
      if (i > 0 && nums[i] <= nums[i - 1])
        break;
      // Since nums[0..i] is strictly increasing, move j to the place such that
      // nums[j] > nums[i]. The valid removals will then be nums[i + 1..j - 1],
      // nums[i + 1..j], ..., nums[i + 1..n).
      while (j < n && nums[i] >= nums[j])
        ++j;
      ans += n - j + 1;
    }

    return ans;
  }

 private:
  // Returns the start index i of the suffix subarray such that nums[i..n) is
  // strictly increasing.
  int getStartIndexOfSuffix(const vector<int>& nums) {
    for (int i = nums.size() - 2; i >= 0; --i)
      if (nums[i] >= nums[i + 1])
        return i + 1;
    return 0;
  }
};

 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
40
41
42
class Solution {
  public int incremovableSubarrayCount(int[] nums) {
    final int n = nums.length;
    final int startIndex = getStartIndexOfSuffix(nums);
    // If the complete array is strictly increasing, the total number of ways we
    // can remove elements equals the total number of possible subarrays.
    if (startIndex == 0)
      return n * (n + 1) / 2;

    // The valid removals starting from nums[0] include nums[0..startIndex - 1],
    // nums[0..startIndex], ..., nums[0..n).
    int ans = n - startIndex + 1;

    // Enumerate each prefix subarray that is strictly increasing.
    for (int i = 0, j = startIndex; i < startIndex; ++i) {
      if (i > 0 && nums[i] <= nums[i - 1])
        break;
      // Since nums[0..i] is strictly increasing, move j to the place such that
      // nums[j] > nums[i]. The valid removals will then be nums[i + 1..j - 1],
      // nums[i + 1..j], ..., nums[i + 1..n).
      while (j < n && nums[i] >= nums[j])
        ++j;
      ans += n - j + 1;
    }

    return ans;
  }

  // Returns the start index i of the suffix subarray such that nums[i..n) is
  // strictly increasing.
  private int getStartIndexOfSuffix(int[] nums) {
    for (int i = nums.length - 2; i >= 0; --i)
      if (nums[i] >= nums[i + 1])
        return i + 1;
    return 0;
  }

  private int firstGreater(int[] A, int startIndex, int target) {
    final int i = Arrays.binarySearch(A, startIndex, A.length, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}

 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
class Solution:
  def incremovableSubarrayCount(self, nums: list[int]) -> int:
    n = len(nums)
    startIndex = self._getStartIndexOfSuffix(nums)
    # If the complete array is strictly increasing, the total number of ways we
    # can remove elements equals the total number of possible subarrays.
    if startIndex == 0:
      return n * (n + 1) // 2

    # The valid removals starting from nums[0] include nums[0..startIndex - 1],
    # nums[0..startIndex], ..., nums[0..n).
    ans = n - startIndex + 1

    # Enumerate each prefix subarray that is strictly increasing.
    j = startIndex
    for i in range(startIndex):
      if i > 0 and nums[i] <= nums[i - 1]:
        break
      # Since nums[0..i] is strictly increasing, move j to the place such that
      # nums[j] > nums[i]. The valid removals will then be nums[i + 1..j - 1],
      # nums[i + 1..j], ..., nums[i + 1..n).
      while j < n and nums[i] >= nums[j]:
        j += 1
      ans += n - j + 1

    return ans

  def _getStartIndexOfSuffix(self, nums: list[int]) -> int:
    for i in range(len(nums) - 2, -1, -1):
      if nums[i] >= nums[i + 1]:
        return i + 1
    return 0