LeetCode 3388 - Count Beautiful Splits in an Array

We are given an integer array nums, and we want to count how many ways we can split it into exactly three non-empty contiguous subarrays: - nums1 - nums2 - nums3 such that: where + means concatenation. A split is considered beautiful if at least one of these conditions holds: 1.

leetcodemediumarraydynamic-programming

LeetCode Problem 3388

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

We are given an integer array nums, and we want to count how many ways we can split it into exactly three non-empty contiguous subarrays:

  • nums1
  • nums2
  • nums3

such that:

nums = nums1 + nums2 + nums3

where + means concatenation.

A split is considered beautiful if at least one of these conditions holds:

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

A prefix means the entire smaller array matches the beginning of the larger array. For example:

  • [1, 2] is a prefix of [1, 2, 5]
  • [1, 2] is not a prefix of [1, 3, 2]

The task is to return the total number of beautiful splits.

The constraints are important:

  • nums.length <= 5000
  • Elements are small integers, but that does not significantly simplify the core problem.

The main challenge comes from the number of possible splits. If the array has length n, there are roughly O(n^2) valid ways to choose the two split points. For each split, we may need to compare subarrays. A naive comparison can take O(n) time, which would lead to O(n^3) complexity, too slow for n = 5000.

Several edge cases are important:

  • Arrays too short to form three non-empty parts.
  • Repeated values, where many prefixes match.
  • Completely distinct arrays, where almost no matches exist.
  • Cases where both prefix conditions hold simultaneously.
  • Very long repeated sequences, where inefficient comparisons become extremely expensive.

The key difficulty is efficiently checking whether two subarrays share a common prefix.

Approaches

Brute Force Approach

The most direct solution is to try every possible split.

We choose:

  • the end of nums1
  • the end of nums2

which automatically determines nums3.

For each split:

  • extract the three subarrays
  • check whether nums1 is a prefix of nums2
  • check whether nums2 is a prefix of nums3

A prefix check can take linear time in the size of the smaller array.

Since there are O(n^2) splits and each comparison may cost O(n), the total complexity becomes O(n^3).

This works for small inputs but is too slow for n = 5000.

Optimal Approach

The critical observation is that we repeatedly compare prefixes of subarrays.

Instead of comparing elements one by one every time, we can precompute the Longest Common Prefix, LCP, between every pair of starting positions.

Define:

lcp[i][j]

as the length of the longest common prefix between:

nums[i:]
and
nums[j:]

Once we know lcp[i][j], we can determine whether one subarray is a prefix of another in constant time.

For example:

  • nums1 = nums[0:i]
  • nums2 = nums[i:j]

Then nums1 is a prefix of nums2 if:

length(nums1) <= lcp[0][i]

Similarly:

  • nums2 = nums[i:j]
  • nums3 = nums[j:n]

Then nums2 is a prefix of nums3 if:

length(nums2) <= lcp[i][j]

The LCP table can be built using dynamic programming in O(n^2) time.

After preprocessing, every split check becomes O(1), giving total complexity O(n^2).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Tries all splits and compares subarrays directly
Optimal O(n^2) O(n^2) Uses LCP preprocessing for constant-time prefix checks

Algorithm Walkthrough

Step 1: Define the LCP Table

Create a 2D table:

lcp[i][j]

where each entry stores the length of the longest common prefix between:

nums[i:]
and
nums[j:]

This lets us quickly determine how many consecutive elements match starting from two positions.

Step 2: Build the LCP Table Bottom-Up

We fill the table from the end toward the beginning.

If:

nums[i] == nums[j]

then:

lcp[i][j] = 1 + lcp[i + 1][j + 1]

Otherwise:

lcp[i][j] = 0

We process indices in reverse order so that lcp[i + 1][j + 1] is already known.

Step 3: Enumerate All Valid Splits

We choose two split points:

  • i, the start of nums2
  • j, the start of nums3

This creates:

nums1 = nums[0:i]
nums2 = nums[i:j]
nums3 = nums[j:n]

All three parts must be non-empty, so:

1 <= i < j < n

Step 4: Check the First Beautiful Condition

Let:

len1 = i
len2 = j - i

nums1 is a prefix of nums2 if:

len1 <= len2
and
lcp[0][i] >= len1

The first condition ensures the shorter array can fit entirely inside the second.

The second condition verifies that all elements match.

Step 5: Check the Second Beautiful Condition

Let:

len2 = j - i
len3 = n - j

nums2 is a prefix of nums3 if:

len2 <= len3
and
lcp[i][j] >= len2

Step 6: Count Beautiful Splits

If either condition is true, increment the answer.

Continue until all split pairs have been processed.

Why it works

The algorithm works because lcp[i][j] precisely captures the maximum number of matching consecutive elements starting from positions i and j.

A subarray A is a prefix of subarray B exactly when:

  • len(A) <= len(B)
  • the first len(A) elements match

The LCP table allows us to verify the second requirement instantly. Since every valid split is examined exactly once, and every beautiful condition is checked correctly, the final count is accurate.

Python Solution

from typing import List

class Solution:
    def beautifulSplits(self, nums: List[int]) -> int:
        n = len(nums)

        # lcp[i][j] = longest common prefix length
        # between nums[i:] and nums[j:]
        lcp = [[0] * (n + 1) for _ in range(n + 1)]

        # Build from bottom-right to top-left
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if nums[i] == nums[j]:
                    lcp[i][j] = 1 + lcp[i + 1][j + 1]

        answer = 0

        # i = start of nums2
        # j = start of nums3
        for i in range(1, n):
            for j in range(i + 1, n):
                len1 = i
                len2 = j - i
                len3 = n - j

                beautiful = False

                # nums1 is prefix of nums2
                if len1 <= len2 and lcp[0][i] >= len1:
                    beautiful = True

                # nums2 is prefix of nums3
                if len2 <= len3 and lcp[i][j] >= len2:
                    beautiful = True

                if beautiful:
                    answer += 1

        return answer

The implementation begins by constructing the LCP table. The table dimensions are (n + 1) x (n + 1) so that accesses to i + 1 and j + 1 remain valid without boundary checks.

The nested reverse loops build the table dynamically. Whenever two elements match, we extend the common prefix by one plus the already computed suffix result.

After preprocessing, the algorithm iterates through every valid pair of split points. For each split, it computes the lengths of the three subarrays and checks both beautiful conditions using constant-time LCP lookups.

The boolean variable beautiful prevents double counting when both conditions hold simultaneously.

Go Solution

func beautifulSplits(nums []int) int {
	n := len(nums)

	// lcp[i][j] = longest common prefix
	// between nums[i:] and nums[j:]
	lcp := make([][]int, n+1)
	for i := range lcp {
		lcp[i] = make([]int, n+1)
	}

	// Build LCP table
	for i := n - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if nums[i] == nums[j] {
				lcp[i][j] = 1 + lcp[i+1][j+1]
			}
		}
	}

	answer := 0

	// i = start of nums2
	// j = start of nums3
	for i := 1; i < n; i++ {
		for j := i + 1; j < n; j++ {
			len1 := i
			len2 := j - i
			len3 := n - j

			beautiful := false

			// nums1 is prefix of nums2
			if len1 <= len2 && lcp[0][i] >= len1 {
				beautiful = true
			}

			// nums2 is prefix of nums3
			if len2 <= len3 && lcp[i][j] >= len2 {
				beautiful = true
			}

			if beautiful {
				answer++
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A 2D slice is used for the LCP table. Go arrays are zero initialized automatically, so unmatched positions naturally remain 0.

No special handling for integer overflow is required because the maximum answer is bounded by O(n^2) and easily fits inside a standard Go int.

Slices are used throughout instead of copying subarrays, which keeps the implementation efficient.

Worked Examples

Example 1

nums = [1, 1, 2, 1]

Step 1: Enumerate Splits

Possible split points:

i j nums1 nums2 nums3
1 2 [1] [1] [2,1]
1 3 [1] [1,2] [1]
2 3 [1,1] [2] [1]

Step 2: Evaluate Conditions

Split (i=1, j=2)

nums1 = [1]
nums2 = [1]
nums3 = [2,1]

Check:

nums1 prefix nums2?
Yes

Beautiful split count becomes 1.

Split (i=1, j=3)

nums1 = [1]
nums2 = [1,2]
nums3 = [1]

Check:

nums1 prefix nums2?
Yes

Beautiful split count becomes 2.

Split (i=2, j=3)

nums1 = [1,1]
nums2 = [2]
nums3 = [1]

Neither prefix condition holds.

Final answer:

2

Example 2

nums = [1,2,3,4]

Step 1: Enumerate Splits

i j nums1 nums2 nums3
1 2 [1] [2] [3,4]
1 3 [1] [2,3] [4]
2 3 [1,2] [3] [4]

Step 2: Evaluate Conditions

Every prefix comparison fails immediately because all elements differ.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Building the LCP table and checking all splits both require quadratic time
Space O(n^2) The LCP dynamic programming table stores values for every pair of indices

The preprocessing phase fills an n x n table, which costs O(n^2) time.

The split enumeration also examines O(n^2) pairs of split points, but each validation is constant time due to the LCP table.

Therefore, the total complexity remains quadratic.

Test Cases

from typing import List

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, -1, -1):
                if nums[i] == nums[j]:
                    lcp[i][j] = 1 + lcp[i + 1][j + 1]

        answer = 0

        for i in range(1, n):
            for j in range(i + 1, n):
                len1 = i
                len2 = j - i
                len3 = n - j

                beautiful = False

                if len1 <= len2 and lcp[0][i] >= len1:
                    beautiful = True

                if len2 <= len3 and lcp[i][j] >= len2:
                    beautiful = True

                if beautiful:
                    answer += 1

        return answer

sol = Solution()

assert sol.beautifulSplits([1,1,2,1]) == 2  # Provided example
assert sol.beautifulSplits([1,2,3,4]) == 0  # No matching prefixes

assert sol.beautifulSplits([1,1,1]) == 1  # Smallest valid beautiful split
assert sol.beautifulSplits([1,1,1,1]) == 3  # Multiple overlapping matches

assert sol.beautifulSplits([1,2,1,2,1,2]) == 3  # Repeated pattern
assert sol.beautifulSplits([5,5,5,5,5]) == 6  # Heavy repetition

assert sol.beautifulSplits([1,2,3]) == 0  # Minimum size with no match
assert sol.beautifulSplits([0,0,0,0,0,0]) == 9  # Large number of valid splits

assert sol.beautifulSplits([1,2,1]) == 0  # Exactly one possible split, invalid
assert sol.beautifulSplits([1,2,2,2]) == 1  # nums2 prefix nums3 only

Test Summary

Test Why
[1,1,2,1] Validates the provided example
[1,2,3,4] Ensures no false positives
[1,1,1] Smallest non-trivial valid case
[1,1,1,1] Multiple valid prefix relationships
[1,2,1,2,1,2] Repeated structured pattern
[5,5,5,5,5] Stress case with many equal elements
[1,2,3] Minimum valid array length
[0,0,0,0,0,0] Dense matching prefixes
[1,2,1] Single split that should fail
[1,2,2,2] Validates second prefix condition independently

Edge Cases

One important edge case is the smallest possible valid array length, n = 3. In this situation there is exactly one possible split, where every subarray has length 1. A buggy implementation may accidentally allow empty subarrays or miss this only candidate split. The current implementation avoids this by enforcing 1 <= i < j < n.

Another important edge case is arrays with all identical values, such as [1,1,1,1,1]. In these cases, almost every prefix comparison succeeds. A naive solution may become extremely slow because it repeatedly compares long matching subarrays. The LCP preprocessing completely eliminates repeated work, allowing these cases to run efficiently in quadratic time.

A third important edge case occurs when both beautiful conditions are simultaneously true. For example:

nums = [1,1,1,1]

Some splits satisfy both:

  • nums1 is a prefix of nums2
  • nums2 is a prefix of nums3

A careless implementation might count such splits twice. This solution uses a single boolean flag and increments the answer only once per split.

Another subtle edge case involves length mismatches. Even if two subarrays start with identical elements, the smaller one cannot be a prefix if it is longer than the target subarray. For example:

nums1 = [1,1]
nums2 = [1]

Even though the first element matches, nums1 cannot be a prefix of nums2. The implementation explicitly checks length constraints before consulting the LCP table.