Count Beautiful Splits in an Array solution and explanation
The problem
You are given an array nums.
A split of an array nums is beautiful if:
- The array
numsis split into three subarrays:nums1,nums2, andnums3, such thatnumscan be formed by concatenatingnums1,nums2, andnums3in that order. - The subarray
nums1is a prefix ofnums2ORnums2is a prefix ofnums3.
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:
- A split with
nums1 = [1],nums2 = [1,2],nums3 = [1]. - A split with
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] <= 50
Approach overview
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.
Solution
We can preprocess LCP[i][j] to represent the length of the longest common prefix of nums[i:] and nums[j:]. Initially, LCP[i][j] = 0.
Next, we enumerate i and j in reverse order. For each pair of i and j, if nums[i] = nums[j], then we can get LCP[i][j] = LCP[i + 1][j + 1] + 1.
Finally, we enumerate the ending position i of the first subarray (excluding position i) and the ending position j of the second subarray (excluding position j). The length of the first subarray is i, the length of the second subarray is j - i, and the length of the third subarray is n - j. If i leq j - i and LCP[0][i] geq i, or j - i leq n - j and LCP[i][j] geq j - i, then this split is beautiful, and we increment the answer by one.
After enumerating, the answer is the number of beautiful splits.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.
class Solution:
def beautifulSplits(self, nums: List[int]) -> int:
n = len(nums)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, i - 1, -1):
if nums[i] == nums[j]:
lcp[i][j] = lcp[i + 1][j + 1] + 1
ans = 0
for i in range(1, n - 1):
for j in range(i + 1, n):
a = i <= j - i and lcp[0][i] >= i
b = j - i <= n - j and lcp[i][j] >= j - i
ans += int(a or b)
return ansclass Solution {
public int beautifulSplits(int[] nums) {
int n = nums.length;
int[][] lcp = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (nums[i] == nums[j]) {
lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
}
int ans = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
boolean a = (i <= j - i) && (lcp[0][i] >= i);
boolean b = (j - i <= n - j) && (lcp[i][j] >= j - i);
if (a || b) {
ans++;
}
}
}
return ans;
}
}class Solution {
public:
int beautifulSplits(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (nums[i] == nums[j]) {
lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
}
int ans = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
bool a = (i <= j - i) && (lcp[0][i] >= i);
bool b = (j - i <= n - j) && (lcp[i][j] >= j - i);
if (a || b) {
ans++;
}
}
}
return ans;
}
};function beautifulSplits(nums: number[]): number {
const n = nums.length;
const lcp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
for (let i = n - 1; i >= 0; i--) {
for (let j = n - 1; j > i; j--) {
if (nums[i] === nums[j]) {
lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
}
let ans = 0;
for (let i = 1; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
const a = i <= j - i && lcp[0][i] >= i;
const b = j - i <= n - j && lcp[i][j] >= j - i;
if (a || b) {
ans++;
}
}
}
return ans;
}func beautifulSplits(nums []int) (ans int) {
n := len(nums)
lcp := make([][]int, n+1)
for i := range lcp {
lcp[i] = make([]int, n+1)
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j > i; j-- {
if nums[i] == nums[j] {
lcp[i][j] = lcp[i+1][j+1] + 1
}
}
}
for i := 1; i < n-1; i++ {
for j := i + 1; j < n; j++ {
a := i <= j-i && lcp[0][i] >= i
b := j-i <= n-j && lcp[i][j] >= j-i
if a || b {
ans++
}
}
}
return
}Complexity analysis
| 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 |
Frequently asked questions
Is Count Beautiful Splits in an Array easy or hard?
The problem is rated Medium but has a relatively low acceptance rate because recognizing the need for LCP preprocessing is not immediately obvious. Candidates who attempt direct comparisons usually hit time limits. The key insight is converting repeated prefix checks into constant-time lookups.
Count Beautiful Splits in an Array Python/Java solution
Implement the LCP table using a 2D array and fill it from the end toward the beginning so that lcp[i+1][j+1] is already known. After preprocessing, iterate over split points (i, j) and use constant-time LCP checks to validate prefix conditions. The same logic translates directly to Python, Java, C++, Go, or TypeScript.
How to solve Count Beautiful Splits in an Array in O(n^2)?
First build an LCP matrix where lcp[i][j] represents the length of the longest common prefix between suffixes starting at indices i and j. Then enumerate split indices (i, j) that create segments A, B, and C. Use LCP lookups to check if A is a prefix of B or B is a prefix of C in constant time.
What is the best approach for Count Beautiful Splits in an Array?
The most effective approach precomputes a Longest Common Prefix (LCP) table and then enumerates all valid split points. The LCP table lets you check whether two subarrays share a prefix in O(1) time. After preprocessing in O(n^2), each split check becomes constant time, giving an overall O(n^2) solution.
Is Count Beautiful Splits in an Array asked at Google/Amazon/Meta?
Problems involving prefix comparisons, array splitting, and dynamic programming appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the technique of precomputing prefix relationships and optimizing repeated comparisons is commonly tested.
What data structure is used in Count Beautiful Splits in an Array?
The core structure is a 2D LCP table built using dynamic programming. It stores the longest common prefix length for every pair of suffix starting indices. The algorithm also relies on standard array traversal and enumeration of split indices.
What is the time complexity of Count Beautiful Splits in an Array?
The optimized solution runs in O(n^2) time with O(n^2) space. O(n^2) time is used to build the LCP table for all suffix pairs and another O(n^2) to iterate through all valid split positions. A naive brute force approach would take O(n^3) because every split requires a linear prefix comparison.