Count Beautiful Splits in an Array

Count Beautiful Splits in an Array

What is this problem about?

The Count Beautiful Splits in an Array coding problem asks you to find the number of ways to split an array into three non-empty contiguous parts: nums1, nums2, nums3. A split is "beautiful" if at least one of these conditions is met:

1. nums1 is a prefix of nums2.
2. nums2 is a prefix of nums3.

Why is this asked in interviews?

Amazon and Bloomberg use this Array interview pattern to test your efficiency with prefix and string matching logic. It’s a "Medium" problem because an O(N^3) solution (trying all splits and checking prefixes) is too slow. It evaluates if you can optimize the prefix check to O(1) or O(log N) using a Longest Common Prefix (LCP) array or Z-algorithm.

Algorithmic pattern used

The problem is best solved using Precomputation (Z-algorithm or LCP).

1. Precompute an LCP matrix or use the Z-algorithm to find the length of the longest common prefix between any two suffixes of the array.
2. Iterate through all possible split points i and j (where nums1 = [0..i-1], nums2 = [i..j-1], nums3 = [j..n-1]).
3. Use the precomputed LCP to check if LCP(0, i) >= i (meaning nums1 is a prefix of nums2) or if LCP(i, j) >= j - i (meaning nums2 is a prefix of nums3).

Example explanation

nums = [1, 2, 1, 2, 1, 2, 1]

1. Split into [1, 2], [1, 2, 1, 2], [1].
2. nums1 is [1, 2]. nums2 starts with [1, 2, ...].
3. Condition 1 is met (nums1 is a prefix of nums2). This is a beautiful split.

Common mistakes candidates make

• Brute Force Prefixes: Using array.slice().equals() in every loop, which turns an O(N^2) search into O(N^3).
• Index Management: Tricky off-by-one errors when defining the boundaries of nums1, nums2, and nums3.
• Memory Limit: Creating a full O(N^2) LCP matrix might exceed memory for N=5000. In such cases, the Z-algorithm is more memory-efficient.

Interview preparation tip

Master the Z-algorithm. It allows you to find all occurrences of a pattern (or in this case, a prefix) in linear time, which is a common requirement for "Medium" and "Hard" array/string problems.