Find Number of Ways to Split Array
Learn this problem
GoogleNEW GRADOAProblem statement
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.
Update 06-26-2026: This problem has been confirmed as a duplicate of Split and Sort Array. I recommend practicing that version because it is more complete. I merged this page's last seen dates into that problem, so I will not keep tracking this duplicate separately going forward. 🥝
Function
findNumberOfWaysToSplitArray(A: int[]) → intExamples
Example 1
A = [1, 3, 2, 4]return = 2There 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
2 <= A.length <= 10^5-10^9 <= A[i] <= 10^9