Count Beautiful Splits in an Array — Problem & Solution
Count Beautiful Splits in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Beautiful Splits in an Array is a medium coding problem on arrays and dynamic programming, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums. A split of nums into three non-empty consecutive parts nums1, nums2 and nums3 (so that nums = nums1 + nums2 + nums3) is beautiful if at least one of the following holds:
nums1is a prefix ofnums2, ornums2is a prefix ofnums3.
Return the number of beautiful splits.
Example 1
Input: nums = [1,1,2,1]
Output: 2
Explanation: [1] | [1,2] | [1] works because [1] is a prefix of [1,2]; [1] | [1] | [2,1] works too.
Example 2
Input: nums = [1,2,3,4]
Output: 0
Example 3
Input: nums = [1,1,1]
Output: 1
Explanation: The only split is [1] | [1] | [1], and [1] is a prefix of [1].
Constraints
1 <= nums.length <= 50000 <= nums[i] <= 50
Hints for Count Beautiful Splits in an Array
Hint 1
A split is fixed by two cut points:
nums2starts atiandnums3starts atj(1 <= i < j < n). That is onlyO(n^2)splits — the comparisons are the expensive part.Hint 2
"
Ais a prefix ofB" for two suffixes of the same array is a longest-common-prefix question: it holds when|A| <= |B|andlcp(start of A, start of B) >= |A|.Hint 3
Precompute
lcp[a][b]for all pairs of start positions withlcp[a][b] = nums[a] == nums[b] ? lcp[a + 1][b + 1] + 1 : 0, filled from the back.
How to solve Count Beautiful Splits in an Array
There are only O(n^2) splits, so each must be checked in O(1). Both conditions compare two subarrays that start at known positions, which is exactly what a longest-common-prefix table over pairs of suffixes answers.
Approach
- Fill
lcp[a][b](fora < b) from the end:lcp[a][b] = lcp[a + 1][b + 1] + 1whennums[a] == nums[b], else 0. - For each
iin1..n-2(start ofnums2) andjini+1..n-1(start ofnums3): - Condition 1:
i <= j - iandlcp[0][i] >= i(nums1has lengthi). - Condition 2:
j - i <= n - jandlcp[i][j] >= j - i(nums2has lengthj - i). - Count the splits where either condition holds.
Why it works
A is a prefix of B exactly when A is not longer than B and their first |A| elements agree, which is lcp >= |A| for the suffixes where they start. The recurrence for lcp is the standard one: two suffixes share a prefix of length L + 1 iff their first elements match and the suffixes after them share L.
Complexity
- Time —
O(n^2) - Space —
O(n^2)
Pitfalls
- Count a split once even when both conditions hold — use
or, not two separate counters. - Check the length condition too:
lcpalone can exceed the length of the shorter part.
Reference solution
Python
from typing import List
def beautifulSplits(nums: List[int]) -> int:
n = len(nums)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for a in range(n - 1, -1, -1):
for b in range(n - 1, a, -1):
if nums[a] == nums[b]:
lcp[a][b] = lcp[a + 1][b + 1] + 1
count = 0
for i in range(1, n - 1):
first = lcp[0][i] >= i
for j in range(i + 1, n):
if (first and i <= j - i) or (j - i <= n - j and lcp[i][j] >= j - i):
count += 1
return countJava
public static int beautifulSplits(int[] nums) {
int n = nums.length;
int[][] lcp = new int[n + 1][n + 1];
for (int a = n - 1; a >= 0; a--) {
for (int b = n - 1; b > a; b--) {
if (nums[a] == nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
}
}
int count = 0;
for (int i = 1; i < n - 1; i++) {
boolean first = lcp[0][i] >= i;
for (int j = i + 1; j < n; j++) {
if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
}
}
return count;
}C++
int beautifulSplits(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
for (int a = n - 1; a >= 0; a--) {
for (int b = n - 1; b > a; b--) {
if (nums[a] == nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
}
}
int count = 0;
for (int i = 1; i < n - 1; i++) {
bool first = lcp[0][i] >= i;
for (int j = i + 1; j < n; j++) {
if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
}
}
return count;
}JavaScript
var beautifulSplits = function(nums) {
var n = nums.length;
var lcp = [];
for (var r = 0; r <= n; r++) lcp.push(new Array(n + 1).fill(0));
for (var a = n - 1; a >= 0; a--) {
for (var b = n - 1; b > a; b--) {
if (nums[a] === nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
}
}
var count = 0;
for (var i = 1; i < n - 1; i++) {
var first = lcp[0][i] >= i;
for (var j = i + 1; j < n; j++) {
if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming