Partition Array into Disjoint Intervals

Partition Array into Disjoint Intervals

What is this problem about?

The Partition Array into Disjoint Intervals problem asks you to find the smallest left partition index such that every element in the left part is ≤ every element in the right part. Return the length of the left partition. This coding problem uses prefix max and suffix min to determine the valid partition point. The array interview pattern is the core.

Why is this asked in interviews?

Microsoft asks this to test precomputed prefix/suffix array reasoning. The condition — all left elements ≤ all right elements — translates to: max of left partition ≤ min of right partition. Precompute prefix max from left and suffix min from right, then find the leftmost valid split.

Algorithmic pattern used

Prefix max + suffix min arrays. Compute prefixMax[i] = max of arr[0..i]. Compute suffixMin[i] = min of arr[i..n-1]. For each position i from 0 to n-2: if prefixMax[i] <= suffixMin[i+1], return i+1 (length of left part).

Example explanation

arr=[5,0,3,8,6]. prefixMax=[5,5,5,8,8]. suffixMin=[0,0,3,6,6].

• i=0: prefixMax[0]=5 ≤ suffixMin[1]=0? No.
• i=1: prefixMax[1]=5 ≤ suffixMin[2]=3? No.
• i=2: prefixMax[2]=5 ≤ suffixMin[3]=6? Yes! Return 3.

Common mistakes candidates make

• Linear scan without precomputation (O(n²)).
• Not computing suffix min correctly (from right to left).
• Off-by-one: partition length = index+1 (left part inclusive).
• Using prefix max OR suffix min alone (need both).

Interview preparation tip

"Valid partition where all left ≤ all right" always uses prefix max and suffix min arrays. This O(n) preprocessing + O(n) scan pattern appears in multiple array partition problems. Practice building both prefix and suffix aggregate arrays — they're building blocks for dozens of array boundary problems. After solving this, extend to "find the minimum partition into sorted subarrays."