Ctrl K

Split Into Rising Chains

Hard
You get an array values sorted in non-decreasing order and a number min_len. Distribute all of the elements among one or more chains so that: - every element lands in exactly one chain (elements keep their array order inside a chain); - the values inside each chain are strictly increasing; - every chain holds at least min_len elements. Return True if such a split exists and False otherwise.
Example 1
values=[2, 3, 3, 5, 5, 8], min_len=3 → True

There are two 3s, so at least two chains are needed; with 6 values both can reach length 3: [2, 3, 5] and [3, 5, 8].

Example 2
values=[4, 4, 4, 6, 7], min_len=2 → False

The three 4s must go to three different chains, each needing at least 2 values: that is 6 values, but there are only 5.

Example 3
values=[1, 9], min_len=1 → True
Constraints
  • 1 ≤ min_len ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁵
  • values is sorted in non-decreasing order
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsStretches With Exactly k Kinds HardDistinct GCDs of Selections HardBalanced Cuts After One Replacement HardPrefix Popularity Totals HardPull Matching Cards Apart Hard
loading Python…
Input
values=[2, 3, 3, 5, 5, 8], min_len=3
Expected
True

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.