#3388

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Beautiful Splits in an Array

Learn to count all valid beautiful splits in an array using state transition dynamic programming efficiently and accurately.

array dynamic programming

Problem Statement

You are given an integer array nums. A split divides the array into two non-empty contiguous parts. A split is considered beautiful if the number of unique elements on the left side equals the number on the right side. Your task is to determine how many beautiful splits exist for the given array.

For example, given nums = [1,1,2,1], the valid beautiful splits occur where the left segment has the same count of unique elements as the right segment. Return the total count of such splits. Constraints include 1 <= nums.length <= 5000 and 0 <= nums[i] <= 50.

Examples

Example 1

Input: nums = [1,1,2,1]

Output: 2

The beautiful splits are:

Example 2

Input: nums = [1,2,3,4]

Output: 0

There are 0 beautiful splits.

Constraints

1 <= nums.length <= 5000
0 <= nums[i] <= 50

Solution Approach

Use Prefix and Suffix Frequency Maps

Construct frequency maps for the left and right parts of the array as you iterate through possible split points. This allows quick comparison of unique element counts for each potential split.

Dynamic Programming State Transition

Use a DP approach to maintain the number of unique elements in prefixes and suffixes. Transition the state as you move the split point, updating counts incrementally rather than recomputing from scratch.

Count Beautiful Splits

Iterate through all possible split points, comparing the DP-tracked unique element counts of left and right segments. Increment a result counter each time the counts match, yielding the total number of beautiful splits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the chosen implementation of prefix and suffix tracking. A direct frequency array approach gives O(n) per update with O(n) space, while more naive counting can reach O(n^2). Space complexity depends on storing frequency counts for each split, generally O(n) or O(maxValue).

What Interviewers Usually Probe

Recognizes DP pattern with prefix and suffix frequency states.
Checks understanding of unique element counting and state transitions.
Tests ability to avoid recomputation and handle incremental updates efficiently.

Common Pitfalls or Variants

Common pitfalls

Recomputing unique counts from scratch for each split instead of using incremental updates.
Incorrectly updating frequency maps when elements move between left and right segments.
Off-by-one errors in split point iteration leading to missed or extra counts.

Follow-up variants

Count beautiful splits when the split condition depends on sum equality instead of unique elements.
Find splits where one side contains a fixed set of elements and count valid partitions.
Modify the problem to allow k-way splits with similar uniqueness constraints.

FAQ

What is the main pattern used in Count Beautiful Splits in an Array?

The problem relies on state transition dynamic programming, tracking unique element counts in prefix and suffix segments to determine valid splits.

How do I efficiently count unique elements in left and right partitions?

Maintain frequency maps and update them incrementally as you move the split point instead of recomputing from scratch.

Can the array contain zeros or repeated numbers?

Yes, the array may contain zeros and duplicates; the solution must handle repeated elements correctly in unique counts.

What is the maximum array length allowed for this problem?

The array length can be up to 5000, so solutions need to handle large arrays efficiently with O(n) or near O(n) approaches.

Are there common mistakes when implementing this solution?

Common mistakes include mismanaging frequency maps, forgetting to decrement counts when moving elements, and off-by-one errors at split points.

terminal

Solution

Solution 1: LCP + Enumeration

We can preprocess $\text{LCP}[i][j]$ to represent the length of the longest common prefix of $\textit{nums}[i:]$ and $\textit{nums}[j:]$. Initially, $\text{LCP}[i][j] = 0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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, i - 1, -1):
                if nums[i] == nums[j]:
                    lcp[i][j] = lcp[i + 1][j + 1] + 1
        ans = 0
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                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)
        return ans

Continue Practicing

#3393 count paths with the given xor value #3376 minimum time to break locks i #3409 longest subsequence with decreasing adjacent difference