How should I practice Most Segments That Sort the Array?

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

Is Most Segments That Sort the Array associated with Rippling?

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

Most Segments That Sort the Array

Rippling● HardFULLTIMEOA

Problem statement

You are given an integer array arr. Split it into one or more contiguous, non-empty segments. Then sort each segment on its own in nondecreasing order and put the segments back together in their original order.

Return the largest number of segments you can use so that the joined result is the whole array sorted in nondecreasing order.

The array may contain repeated values.

Function

maxSortedSegments(arr: int[]) → int

Examples

Example 1

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

Use the segments [3,1,2], [5,4,4], and [6]. Sorted, they become [1,2,3], [4,4,5], and [6], which join to [1,2,3,4,4,5,6].

A fourth segment does not work. Any cut inside [3,1,2] leaves 3 on the left of a smaller value, and any cut inside [5,4,4] leaves 5 on the left of a 4.

Example 2

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

Every cut leaves a larger value on the left of a smaller one, so the only choice is one segment holding the whole array.

Example 3

arr = [1,1,0,1,2,2]return = 4

Use the segments [1,1,0], [1], [2], and [2]. The first one sorts to [0,1,1], and the joined result is [0,1,1,1,2,2].

The cut before the third 1 is allowed because equal values may sit on either side of a cut.

Constraints

1 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9