How should I practice Decreasing Subsequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google online assessment problems in FastPrep.

Is Decreasing Subsequences associated with Google?

FastPrep tags this as a Google online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Greedy

Decreasing Subsequences

Learn this problem

● Medium

GoogleINTERNOA

See Google hiring insights

Problem statement

Given an int array nums of length n. Split it into strictly decreasing subsequences. Output the min number of subsequences you can get by splitting.

Function

minSubsequences(nums: int[]) → int

Examples

Example 1

nums = [5, 2, 4, 3, 1, 6]return = 3

You can split this array into: [5, 2, 1], [4, 3], [6]. And there are 3 subsequences you get. Or you can split it into [5, 4, 3], [2, 1], [6]. Also 3 subsequences. But [5, 4, 3, 2, 1], [6] is not legal because [5, 4, 3, 2, 1] is not a subsequence of the original array.

Example 2

nums = [2, 9, 12, 13, 4, 7, 6, 5, 10]return = 4

You can split the array into: [2], [9, 4], [12, 10], [13, 7, 6, 5].

Example 3

nums = [1, 1, 1]return = 3

Because of the strictly descending order you have to split it into 3 subsequences: [1], [1], [1].

Constraints

1 ≤ nums.length ≤ 2 * 10^5
-10^9 ≤ nums[i] ≤ 10^9
Every input element must appear in exactly one output subsequence, and each subsequence preserves input order.