Skip to main content
Talentd

Count Beautiful Splits in an Array - Solution & Explanation

MediumArrayDynamic Programming10 min readAsked at: Amazon, Bloomberg
Practice this problem

Problem Statement

You are given an array nums.

A split of an array nums is beautiful if:

  1. The array 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.
  2. The subarray 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:

  1. A split with nums1 = [1], nums2 = [1,2], nums3 = [1].
  2. 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 <= 5000
  • 0 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Prefix ComparisonO(n^3)O(1)Small arrays or when first deriving the problem logic
LCP Preprocessing + Split EnumerationO(n^2)O(n^2)General case and optimal interview solution

Video Solution

3388. Count Beautiful Splits in an Array (Leetcode Medium) • Programming Live with Larry • 1,338 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Count Beautiful Splits in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays