FastPrepCount Sortable Splits
Problem · Array

Count Sortable Splits

Learn this problem
● EasyGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

You are given an integer array A of length N.

Choose one split position that divides A into two non-empty contiguous parts, called left and right. Sort the elements in each part independently in non-decreasing order, then join the sorted left part followed by the sorted right part.

Return the number of split positions for which the joined array is sorted in non-decreasing order.

Function

solution(A: int[]) → int

Examples

Example 1

A = [1, 3, 2, 4]return = 2

There are three possible split positions:

  • left = [1] and right = [3, 2, 4] produce [1, 2, 3, 4], so this split works.
  • left = [1, 3] and right = [2, 4] produce [1, 3, 2, 4], so this split does not work.
  • left = [1, 3, 2] and right = [4] produce [1, 2, 3, 4], so this split works.

Therefore, the answer is 2.

More Google problems

drafts saved locally
public int solution(int[] A) {
  // write your code here
}
A[1, 3, 2, 4]
expected2
checking account