Problem Description

You are given an array nums. Your task is to find the number of ways to split this array into three non-empty subarrays that form a "beautiful" split.

A split of array nums into three subarrays nums1, nums2, and nums3 is considered beautiful if both of the following conditions are met:

1. The three subarrays are consecutive parts of the original array. When concatenated in order (nums1 + nums2 + nums3), they reconstruct the original array nums.

2. At least one of these relationships holds:

   • nums1 is a prefix of nums2 (meaning nums2 starts with all the elements of nums1)
   • nums2 is a prefix of nums3 (meaning nums3 starts with all the elements of nums2)

For example, if nums = [1, 2, 1, 2, 3], one beautiful split could be:

• nums1 = [1, 2]
• nums2 = [1, 2, 3]
• nums3 = [] (empty in this case would be invalid as all subarrays must be non-empty)

Here nums1 is a prefix of nums2 since nums2 starts with [1, 2].

The goal is to count all possible ways to create such beautiful splits of the given array.

Intuition

To solve this problem, we need to efficiently check if one subarray is a prefix of another. The key insight is that checking if array A is a prefix of array B is equivalent to checking if the first len(A) elements of B match exactly with A.

For any split at positions i and j, we get three subarrays:

• nums1 = nums[0:i] with length i
• nums2 = nums[i:j] with length j - i
• nums3 = nums[j:n] with length n - j

For nums1 to be a prefix of nums2, we need:

• Length condition: i <= j - i (nums1 cannot be longer than nums2)
• Content condition: nums[0:i] must match nums[i:i+i] exactly

For nums2 to be a prefix of nums3, we need:

• Length condition: j - i <= n - j (nums2 cannot be longer than nums3)
• Content condition: nums[i:j] must match nums[j:j+(j-i)] exactly

The challenge is efficiently checking these prefix relationships. If we naively compare elements for each possible split, it would be too slow.

This is where the Longest Common Prefix (LCP) technique comes in. By precomputing LCP[i][j] - the length of the longest common prefix starting at positions i and j - we can check prefix relationships in constant time. If LCP[i][j] >= k, then the subarray starting at position i with length k matches the subarray starting at position j with the same length k.

The LCP array can be built using dynamic programming: if nums[i] == nums[j], then LCP[i][j] = LCP[i+1][j+1] + 1. We build this bottom-up by iterating in reverse order.

With the LCP array ready, we can enumerate all possible splits and check the beautiful conditions in constant time using our precomputed values.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements the LCP (Longest Common Prefix) technique combined with enumeration to count beautiful splits efficiently.

Step 1: Build the LCP Table

We create a 2D array lcp where lcp[i][j] represents the length of the longest common prefix between subarrays starting at index i and index j.

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

We iterate in reverse order (from n-1 to 0 for i, and from n-1 to i for j) because:

• If nums[i] == nums[j], then the common prefix starting at positions i and j extends by 1 plus whatever common prefix exists at positions i+1 and j+1
• This creates a bottom-up dynamic programming approach where we build longer prefixes from shorter ones

Step 2: Enumerate All Possible Splits

We enumerate all valid split positions where:

• i represents the end position of the first subarray (exclusive), so nums1 = nums[0:i]
• j represents the end position of the second subarray (exclusive), so nums2 = nums[i:j] and nums3 = nums[j:n]

for i in range(1, n - 1):
    for j in range(i + 1, n):

The ranges ensure that all three subarrays are non-empty: i >= 1, j >= i + 1, and j < n.

Step 3: Check Beautiful Conditions

For each split, we check if it's beautiful by verifying either:

1. Condition A: nums1 is a prefix of nums2

   • Length check: i <= j - i (nums1's length shouldn't exceed nums2's length)
   • Content check: lcp[0][i] >= i (the common prefix between positions 0 and i should be at least i elements long)

2. Condition B: nums2 is a prefix of nums3

   • Length check: j - i <= n - j (nums2's length shouldn't exceed nums3's length)
   • Content check: lcp[i][j] >= j - i (the common prefix between positions i and j should be at least j-i elements long)

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)

If either condition is satisfied, we increment our answer counter.

The time complexity is O(n²) for building the LCP table and O(n²) for enumeration, resulting in overall O(n²) complexity. The space complexity is O(n²) for storing the LCP table.

Example Walkthrough

Let's walk through the solution with nums = [1, 1, 2, 1].

Step 1: Build the LCP Table

We create a 4×4 LCP table where lcp[i][j] stores the longest common prefix length starting at indices i and j.

Building the table from bottom-right to top-left:

• At positions (3,3): Both point to index 3 (value 1), lcp[3][3] = 1
• At positions (2,3): nums[2]=2, nums[3]=1, different values, so lcp[2][3] = 0
• At positions (2,2): Both point to index 2 (value 2), lcp[2][2] = 1
• At positions (1,3): nums[1]=1, nums[3]=1, same! So lcp[1][3] = lcp[2][4] + 1 = 0 + 1 = 1
• At positions (1,2): nums[1]=1, nums[2]=2, different values, so lcp[1][2] = 0
• At positions (1,1): Both point to index 1 (value 1), lcp[1][1] = lcp[2][2] + 1 = 1 + 1 = 2
• At positions (0,3): nums[0]=1, nums[3]=1, same! So lcp[0][3] = lcp[1][4] + 1 = 0 + 1 = 1
• At positions (0,2): nums[0]=1, nums[2]=2, different values, so lcp[0][2] = 0
• At positions (0,1): nums[0]=1, nums[1]=1, same! So lcp[0][1] = lcp[1][2] + 1 = 0 + 1 = 1
• At positions (0,0): Both point to index 0, lcp[0][0] = lcp[1][1] + 1 = 2 + 1 = 3

Final LCP table (relevant portions):

    0  1  2  3
0 [ 3  1  0  1 ]
1 [ -  2  0  1 ]
2 [ -  -  1  0 ]
3 [ -  -  -  1 ]

Step 2: Enumerate All Possible Splits

We check all valid (i, j) pairs where 1 ≤ i < 3 and i+1 ≤ j < 4:

Split 1: i=1, j=2

• nums1 = [1] (length 1)
• nums2 = [1] (length 1)
• nums3 = [2, 1] (length 2)

Check Condition A: Is nums1 a prefix of nums2?

• Length check: 1 ≤ 1 ✓
• Content check: lcp[0][1] = 1 >= 1 ✓
• Condition A is TRUE

Check Condition B: Is nums2 a prefix of nums3?

• Length check: 1 ≤ 2 ✓
• Content check: lcp[1][2] = 0 >= 1 ✗
• Condition B is FALSE

Result: Beautiful (Condition A is true) ✓

Split 2: i=1, j=3

• nums1 = [1] (length 1)
• nums2 = [1, 2] (length 2)
• nums3 = [1] (length 1)

Check Condition A: Is nums1 a prefix of nums2?

• Length check: 1 ≤ 2 ✓
• Content check: lcp[0][1] = 1 >= 1 ✓
• Condition A is TRUE

Check Condition B: Is nums2 a prefix of nums3?

• Length check: 2 ≤ 1 ✗
• Condition B is FALSE (fails length check)

Result: Beautiful (Condition A is true) ✓

Split 3: i=2, j=3

• nums1 = [1, 1] (length 2)
• nums2 = [2] (length 1)
• nums3 = [1] (length 1)

Check Condition A: Is nums1 a prefix of nums2?

• Length check: 2 ≤ 1 ✗
• Condition A is FALSE (fails length check)

Check Condition B: Is nums2 a prefix of nums3?

• Length check: 1 ≤ 1 ✓
• Content check: lcp[2][3] = 0 >= 1 ✗
• Condition B is FALSE

Result: Not beautiful ✗

Final Answer: 2 (Splits at (1,2) and (1,3) are beautiful)

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n^2), where n is the length of the array nums.

The analysis breaks down as follows:

• The first nested loop (building the LCP table) iterates from i = n-1 down to 0, and for each i, the inner loop iterates from j = n-1 down to i. This creates approximately n^2/2 iterations, which is O(n^2).
• The second nested loop iterates with i from 1 to n-2, and for each i, j iterates from i+1 to n-1. This also results in approximately n^2/2 iterations, which is O(n^2).
• Inside both nested loops, all operations (array access, comparisons, arithmetic) are O(1).
• Therefore, the overall time complexity is O(n^2) + O(n^2) = O(n^2).

The space complexity is O(n^2), where n is the length of the array nums.

The analysis is:

• The LCP (Longest Common Prefix) table is a 2D array of size (n+1) × (n+1), which requires O(n^2) space.
• Other variables (i, j, a, b, ans) use constant space O(1).
• Therefore, the overall space complexity is O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Split Boundaries

A critical pitfall is misunderstanding how the split positions work. Many developers incorrectly assume that i and j represent inclusive endpoints or make errors in calculating subarray lengths.

Incorrect Implementation:

# Wrong: Using inclusive ranges or incorrect length calculations
for i in range(1, n):  # This could include i = n-1, leaving no room for third part
    for j in range(i, n):  # This could make j = i, creating empty second part
        first_part_length = i + 1  # Wrong calculation
        second_part_length = j - i + 1  # Wrong calculation

Correct Implementation:

for i in range(1, n - 1):  # Ensures third part exists
    for j in range(i + 1, n):  # Ensures second part is non-empty
        first_part_length = i  # nums[0:i] has length i
        second_part_length = j - i  # nums[i:j] has length j-i
        third_part_length = n - j  # nums[j:n] has length n-j

2. Incorrect LCP Table Construction Order

Building the LCP table in the wrong order leads to using uninitialized values, resulting in incorrect prefix length calculations.

Incorrect Implementation:

# Wrong: Forward iteration doesn't allow using future values
for i in range(n):
    for j in range(i, n):
        if nums[i] == nums[j]:
            lcp[i][j] = lcp[i + 1][j + 1] + 1  # Uses uncomputed values!

Correct Implementation:

# Correct: Backward iteration ensures dependent values are already computed
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  # Values already computed

3. Confusing Prefix Check Logic

The prefix relationship requires both length and content checks. A common mistake is only checking one condition or mixing up which indices to use in the LCP table.

Incorrect Implementation:

# Wrong: Only checking LCP without length constraint
first_is_prefix = lcp[0][i] >= i  # Missing length check

# Wrong: Using wrong indices for second prefix check
second_is_prefix = lcp[0][j] >= j - i  # Should start from i, not 0

Correct Implementation:

# Must check both length constraint and actual prefix match
first_is_prefix = (i <= j - i) and (lcp[0][i] >= i)
second_is_prefix = (j - i <= n - j) and (lcp[i][j] >= j - i)

4. Edge Case: Small Arrays

Failing to handle arrays with fewer than 3 elements, though the problem constraints typically guarantee n >= 3.

Safe Implementation with Guard:

def beautifulSplits(self, nums: List[int]) -> int:
    n = len(nums)
    if n < 3:
        return 0  # Cannot split into 3 non-empty parts
    # ... rest of the solution

5. Memory Optimization Oversight

While not incorrect, using a full n x n LCP table when we only need the upper triangle can waste memory in large inputs.

Memory-Optimized Approach:

# Only compute and store necessary LCP values
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
    for j in range(max(i, n - 1), i - 1, -1):  # Only compute j >= i
        if nums[i] == nums[j]:
            lcp[i][j] = lcp[i + 1][j + 1] + 1