Count Beautiful Splits in an Array - Solution & Explanation

Problem Overview: Given an integer array, count the number of ways to split it into three non-empty parts A, B, and C. A split is considered beautiful if either A is a prefix of B, or B is a prefix of C. The challenge is checking prefix equality between many subarrays efficiently while iterating over all valid split points.

Approach 1: Brute Force Comparison (O(n^3) time, O(1) space)

Enumerate all possible split pairs (i, j) where the array is divided into A = nums[0..i-1], B = nums[i..j-1], and C = nums[j..n-1]. For every split, directly compare elements to check whether A is a prefix of B or B is a prefix of C. Each comparison may scan up to O(n) elements, and there are O(n^2) split pairs, leading to O(n^3) time. This method is useful for reasoning about correctness but quickly becomes too slow for larger arrays.

Approach 2: LCP Preprocessing + Enumeration (O(n^2) time, O(n^2) space)

Precompute a Longest Common Prefix (LCP) table where lcp[i][j] stores the length of the common prefix between suffixes starting at indices i and j. This can be built using dynamic programming by iterating from the end of the array: if nums[i] == nums[j], then lcp[i][j] = 1 + lcp[i+1][j+1]. Once the table is built, iterate over all split positions i and j. Checking whether A is a prefix of B becomes a constant-time lookup: verify lcp[0][i] >= len(A). Similarly, check whether B is a prefix of C using lcp[i][j] >= len(B). This reduces repeated comparisons and keeps the overall complexity at O(n^2).

This approach combines ideas from Array processing and Dynamic Programming. The LCP table acts like a memoized comparison structure similar to techniques used in string algorithms, but applied directly to integer arrays.

Recommended for interviews: The LCP + enumeration approach is what interviewers typically expect. Starting with the brute force solution shows you understand the split conditions, but recognizing that repeated prefix comparisons dominate the runtime demonstrates algorithmic maturity. Precomputing LCP values to convert comparisons into O(1) checks is the key optimization that reduces the solution from cubic to quadratic time.