Problem Brief
Find Number of Ways to Split Array
NEW GRADOA
See Google online assessment and hiring insights
You are given an array A of N integers. You can split the array into two non-empty parts, left and right, sort the elements in each part independently and join them back together.
Your task is to find the number of ways of splitting the array into two parts such that, after sorting the two parts and rejoining them into a single array, the resulting array will be sorted in non-decreasing order. For the array shown above, the answer is 2: the first and third splits result in a sorted array.
1Example 1
Input
A = [1, 3, 2, 4]
Output
2
Explanation
There are two ways to split the array such that the resulting array is sorted:
- Splitting into left = [1] and right = [3, 2, 4], resulting in [1, 2, 3, 4].
- Splitting into left = [1, 3, 2] and right = [4], resulting in [1, 2, 3, 4].
Therefore, the number of ways to split the array is 2.
Constraints
Limits and guarantees your solution can rely on.
🍅🍅