Watch 2 video solutions for Count Beautiful Splits in an Array, a medium level problem involving Array, Dynamic Programming. This walkthrough by Programming Live with Larry has 1,272 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums.
A split of an array nums is beautiful if:
nums is split into three subarrays: nums1, nums2, and nums3, such that nums can be formed by concatenating nums1, nums2, and nums3 in that order.nums1 is a prefix of nums2 OR nums2 is a prefix of nums3.Return the number of ways you can make this split.
Example 1:
Input: nums = [1,1,2,1]
Output: 2
Explanation:
The beautiful splits are:
nums1 = [1], nums2 = [1,2], nums3 = [1].nums1 = [1], nums2 = [1], nums3 = [2,1].Example 2:
Input: nums = [1,2,3,4]
Output: 0
Explanation:
There are 0 beautiful splits.
Constraints:
1 <= nums.length <= 50000 <= nums[i] <= 50Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Comparison | O(n^3) | O(1) | Small arrays or when first deriving the problem logic |
| LCP Preprocessing + Split Enumeration | O(n^2) | O(n^2) | General case and optimal interview solution |