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.

Description Hints 1 Solution Video 44:10

3388. Count Beautiful Splits in an Array

Medium19.3% acceptance2 companies

You are given an array nums.

A split of an array nums is beautiful if:

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.
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:

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 <= 5000
0 <= nums[i] <= 50

Asked at 2 companies

Amazon Bloomberg

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use 2D dynamic programming to find the maximum matching prefix.

44:10

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def beautifulSplits(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,2,1]

Input

[1,2,3,4]

Your code is saved on this device.Solution