FastPrepCount Strictly Increasing Subsequences of Length 3
Problem · Array

Count Strictly Increasing Subsequences of Length 3

Learn this problem
● MediumIBM logoIBMOA
See IBM hiring insights

Problem statement

Given an integer array arr of length n, return the number of strictly increasing subsequences of length 3, modulo 10^9 + 7.

A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements. A length-3 subsequence is strictly increasing when its indices satisfy i < j < k and its values satisfy arr[i] < arr[j] < arr[k].

Function

countIncreasingSubsequences(n: int, arr: int[]) → int

Examples

Example 1

n = 5arr = [1, 2, 3, 4, 1]return = 4

The strictly increasing subsequences are [1, 2, 3], [1, 2, 4], [1, 3, 4], and [2, 3, 4]. Therefore, the answer is 4.

Example 2

n = 4arr = [3, 1, 4, 5]return = 2

The two strictly increasing subsequences are [3, 4, 5] and [1, 4, 5].

Constraints

  • 1 ≤ n ≤ 5000
  • 0 ≤ arr[i] ≤ 10^9

More IBM problems

drafts saved locally
public int countIncreasingSubsequences(int n, int[] arr) {
  // write your code here
}
n5
arr[1, 2, 3, 4, 1]
expected4
checking account