Count Beautiful Splits in an Array
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward method is to check every possible way to split the array into three non-empty subarrays. A split is defined by two indices, i and j, which mark the start of the second and third subarrays, respectively. We can iterate through all valid pairs of (i, j) and, for each pair, explicitly check if the split is beautiful by comparing the elements of the subarrays.
Algorithm
- Initialize a counter
countto 0. - Iterate through all possible first split points
ifrom1ton-2(wherenis the length of the array). - Inside this loop, iterate through all possible second split points
jfromi+1ton-1. - These loops define three subarrays:
nums1 = nums[0...i-1],nums2 = nums[i...j-1], andnums3 = nums[j...n-1]. - For each
(i, j)pair, check the two conditions for a beautiful split:nums1is a prefix ofnums2: This is possible only iflength(nums1) <= length(nums2). If so, perform a linear scan to comparenums[k]withnums[i+k]forkfrom0toi-1.nums2is a prefix ofnums3: This is possible only iflength(nums2) <= length(nums3). If so, perform another linear scan to comparenums[i+k]withnums[j+k]forkfrom0toj-i-1.
- If either of the two conditions is met, increment the
count. - After all loops complete, return
count.
Walkthrough
We use two nested loops to generate all possible split points. The outer loop for i runs from 1 to n-2, and the inner loop for j runs from i+1 to n-1. For each pair (i, j), we get three subarrays: nums1 = nums[0...i-1], nums2 = nums[i...j-1], and nums3 = nums[j...n-1]. We then check the two conditions for a beautiful split. Condition 1: nums1 is a prefix of nums2. We compare nums[k] with nums[i+k] for k from 0 to i-1. This check is only possible if length(nums1) <= length(nums2). Condition 2: nums2 is a prefix of nums3. We compare nums[i+k] with nums[j+k] for k from 0 to j-i-1. This check is only possible if length(nums2) <= length(nums3). If either of these conditions holds, we increment a counter. The final value of the counter is the answer.
class Solution { public int countBeautifulSplits(int[] nums) { int n = nums.length; int count = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { // nums1: [0, i-1], nums2: [i, j-1], nums3: [j, n-1] int len1 = i; int len2 = j - i; int len3 = n - j; boolean cond1 = false; if (len1 <= len2) { boolean isPrefix = true; for (int k = 0; k < len1; k++) { if (nums[k] != nums[i + k]) { isPrefix = false; break; } } if (isPrefix) { cond1 = true; } } boolean cond2 = false; if (len2 <= len3) { boolean isPrefix = true; for (int k = 0; k < len2; k++) { if (nums[i + k] != nums[j + k]) { isPrefix = false; break; } } if (isPrefix) { cond2 = true; } } if (cond1 || cond2) { count++; } } } return count; }}Complexity
Time
O(N^3) - The two nested loops for `i` and `j` run in `O(N^2)`. Inside these loops, the prefix checks involve another loop that can run up to `O(N)` times in the worst case.
Space
O(1) - We only use a few variables to keep track of indices and the count, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Requires no complex data structures or algorithms.
Cons
Highly inefficient due to the nested loops and repeated linear scans for prefix checking.
Will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
The brute-force approach is slow due to the repeated work of comparing subarrays for prefix relationships. We can optimize this by pre-computing the lengths of the longest common prefixes (LCP) for all pairs of suffixes in the array. This allows us to check the prefix conditions in constant time.
Algorithm
- Define a 2D array
lcpof size(n+1) x (n+1), wherelcp[i][j]will store the length of the longest common prefix of suffixesnums[i...]andnums[j...]. - Populate the
lcptable using dynamic programming. Iterateiandjfromn-1down to0. - The recurrence relation is:
if (nums[i] == nums[j]) lcp[i][j] = 1 + lcp[i+1][j+1];otherwiselcp[i][j] = 0. - After
lcpis computed, initializecount = 0. - Iterate through all split points
(i, j)withifrom1ton-2andjfromi+1ton-1. - For each split, check the conditions in
O(1)time:nums1is a prefix ofnums2:len1 <= len2 && lcp[0][i] >= len1.nums2is a prefix ofnums3:len2 <= len3 && lcp[i][j] >= len2.
- If either condition is true, increment
count. - Return
count.
Walkthrough
We define lcp[i][j] as the length of the longest common prefix between the suffix starting at index i (nums[i...]) and the suffix starting at index j (nums[j...]). This lcp table can be filled using dynamic programming. The recurrence relation is: lcp[i][j] = 1 + lcp[i+1][j+1] if nums[i] == nums[j], and 0 otherwise. We fill the table by iterating i and j from n-1 down to 0. After this O(N^2) pre-computation, we can answer any LCP query in O(1). We then iterate through all split points (i, j) as in the brute-force approach. For each split, the conditions can be checked in O(1): nums1 is a prefix of nums2 if lcp[0][i] >= length(nums1), and nums2 is a prefix of nums3 if lcp[i][j] >= length(nums2). This reduces the total time complexity to O(N^2).
class Solution { public int countBeautifulSplits(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 >= 0; j--) { if (nums[i] == nums[j]) { lcp[i][j] = 1 + lcp[i + 1][j + 1]; } } } int count = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { int len1 = i; int len2 = j - i; int len3 = n - j; boolean cond1 = false; if (len1 <= len2 && lcp[0][i] >= len1) { cond1 = true; } boolean cond2 = false; if (len2 <= len3 && lcp[i][j] >= len2) { cond2 = true; } if (cond1 || cond2) { count++; } } } return count; }}Complexity
Time
O(N^2) - The algorithm is dominated by two phases, both taking `O(N^2)`: building the LCP table and iterating through all possible splits.
Space
O(N^2) - The LCP table requires quadratic space.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Passes within time limits for the given constraints.
Cons
The
O(N^2)space complexity can be problematic for largeN, potentially exceeding memory limits.
We can achieve the same O(N^2) time complexity as the DP approach but with a much better O(N) space complexity by using polynomial rolling hash. Hashing allows us to compare any two subarrays for equality in O(1) time on average after an initial O(N) pre-computation.
Algorithm
- Implement a helper class or structure for rolling hash calculations. This involves choosing a base
Pand a modulusM. - Pre-compute two arrays in
O(N): one for the powers of the baseP(powers[k] = P^k % M) and another for the prefix hashes of the input array (prefixHash[k]= hash ofnums[0...k-1]). - Create a function
getHash(start, end)that uses the pre-computed arrays to return the hash of any subarraynums[start...end]inO(1)time. - Initialize
count = 0. - Iterate through all split points
(i, j)withifrom1ton-2andjfromi+1ton-1. - For each split, check the conditions by comparing hashes:
nums1is a prefix ofnums2:len1 <= len2 && getHash(0, len1-1) == getHash(i, i+len1-1).nums2is a prefix ofnums3:len2 <= len3 && getHash(i, j-1) == getHash(j, j+len2-1).
- If either condition is true, increment
count. - Return
count.
Walkthrough
First, we pre-compute the hash values for all prefixes of the nums array. We also pre-compute the powers of a chosen base p. This allows us to calculate the hash of any subarray nums[i...j] in O(1). To increase reliability and avoid collisions, it's a good practice to use two different prime moduli and bases (double hashing), though a single hash is often sufficient for competitive programming problems. With the hashing utility ready, we iterate through all possible split points (i, j). For each split, we check the two conditions by comparing the hashes of the relevant subarrays. Each check is O(1), so the total time complexity remains O(N^2). The space is dominated by the pre-computed hash and power arrays, which is O(N).
class Solution { public int countBeautifulSplits(int[] nums) { int n = nums.length; HashUtil hashUtil = new HashUtil(nums); int count = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { int len1 = i; int len2 = j - i; int len3 = n - j; boolean cond1 = false; if (len1 <= len2) { if (hashUtil.getHash(0, len1 - 1) == hashUtil.getHash(i, i + len1 - 1)) { cond1 = true; } } boolean cond2 = false; if (len2 <= len3) { if (hashUtil.getHash(i, j - 1) == hashUtil.getHash(j, j + len2 - 1)) { cond2 = true; } } if (cond1 || cond2) { count++; } } } return count; }} class HashUtil { private long[] prefixHash; private long[] powers; private long M = 1_000_000_007; private int P = 53; // nums[i] <= 50, so a prime > 51 is good. public HashUtil(int[] arr) { int n = arr.length; prefixHash = new long[n + 1]; powers = new long[n + 1]; powers[0] = 1; for (int i = 0; i < n; i++) { powers[i + 1] = (powers[i] * P) % M; // Add 1 to nums[i] to avoid hash of [0] being 0. prefixHash[i + 1] = (prefixHash[i] * P + (arr[i] + 1)) % M; } } public long getHash(int start, int end) { long len = end - start + 1; long hash = (prefixHash[end + 1] - (prefixHash[start] * powers[(int)len]) % M + M) % M; return hash; }}Complexity
Time
O(N^2) - `O(N)` for pre-computation of hashes and powers, followed by `O(N^2)` for iterating through all splits, with each check taking `O(1)` time.
Space
O(N) - We need two arrays of size `N` to store the prefix hashes and the powers of the base.
Trade-offs
Pros
Optimal space complexity among
O(N^2)time solutions.Efficient in both time and space, making it a robust solution for the given constraints.
Conceptually simpler to implement than other advanced string algorithms like Z-algorithm or Suffix Trees.
Cons
Relies on hashing, which carries a small theoretical probability of collision (two different subarrays having the same hash). This risk can be minimized by using two different hash functions (double hashing).
Solutions
Solution
class 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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.