We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Beautiful Splits in an Array

Number: 3686

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, count the number of ways to split it into three non‐empty consecutive subarrays (nums1, nums2, nums3) such that at least one of the following is true:

  1. nums1 (the first subarray) is a prefix of nums2 (i.e. the entirety of nums1 matches the first |nums1| elements of nums2).
  2. nums2 (the second subarray) is a prefix of nums3 (i.e. the entirety of nums2 matches the first |nums2| elements of nums3).

A split is defined by choosing two indices i and j (with 1 <= i < j <= n−1) that partition nums into: • nums1 = nums[0...i−1] • nums2 = nums[i...j−1] • nums3 = nums[j...n−1]

Return the number of beautiful splits.

Key Insights

  • A “beautiful” split requires at least one of two prefix conditions: either the first subarray is a prefix of the second, or the second subarray is a prefix of the third.
  • For the condition “nums1 is prefix of nums2”, the length of nums1 is i and so nums2 must have at least i elements; also the first i elements of nums2 must equal nums1.
  • For the condition “nums2 is prefix of nums3”, the length of nums2 is (j−i) and therefore nums3 must have at least (j−i) elements; its first (j−i) elements must equal nums2.
  • A naive approach checking every valid split would lead to O(n^3) time. Precomputing information (for example, using rolling hashes or dynamic programming arrays to compare segments in O(1)) helps reduce the cost of each comparison.
  • The split is “beautiful” if either condition holds. Be careful to subtract splits that satisfy both conditions in order to avoid over‐counting when summing individual counts.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case when using precomputed hash arrays or dynamic programming to compare segments in O(1).
Space Complexity: O(n) for storing the hash arrays (or any additional DP arrays).

Solution

We can count the number of beautiful splits by breaking the problem into two parts:

  1. Count splits that satisfy the condition “nums1 is a prefix of nums2.” For a fixed i (the length of nums1), first check whether the first i elements of nums2 (i.e. nums[i ... 2i − 1]) equal nums[0 ... i − 1]. If they do, then any j with j ≥ 2i (and j < n because nums3 must be non‐empty) gives a valid split with respect to this condition. The number of valid j’s for that i is (n − 2*i).
  2. Count splits that satisfy “nums2 is a prefix of nums3.” For a fixed split index j (start of nums3), note that the length of nums2 is (j − i). In order for nums2 to be a prefix of nums3, we require that for the chosen i (subject to 1 <= i < j), the segment nums[i ... j−1] is equal to the first (j−i) elements of nums3 (i.e. nums[j ... j+(j−i)−1]). Since j must allow enough room for nums3, index j ranges from 2 to n−1 and for each j we only consider i that also guarantee nums3 is long enough (i.e. i >= j − (n − j)).
  3. Some splits may satisfy both conditions; subtract these double‐counted splits from the sum of counts obtained in steps (1) and (2).

To compare segments quickly, we use a rolling hash (or any efficient substring equality check) so that we can determine if two segments of the array (of equal length) are identical in O(1) time once precomputation is done.

The algorithm in summary: • Precompute a hash (and any associated power arrays) for array nums. • For each possible valid i (for condition A), check if nums[0...i−1] equals nums[i...2i−1]. If yes, add (n − 2i) to the count. • For condition B, for each valid j (from 2 to n−1), for each valid i in the allowed range (i from max(1, j−(n−j)) to j−1), check if nums[i...j−1] equals nums[j... j+(j−i)−1] and increment the count accordingly. • Next, do a similar nested iteration to count splits that satisfy both conditions and subtract the overlap. • Return the final count.

With careful use of precomputed hashes (or an efficient DP-based prefix comparison), each segment comparison is done in O(1) which leads to an overall time of O(n^2).

Code Solutions

# Python solution using rolling hash for O(1) substring comparisons.
# This solution includes line-by-line comments.

def countBeautifulSplits(nums):
    n = len(nums)
    # Base case: if there are not enough elements to split into 3 parts, return 0.
    if n < 3:
        return 0

    # Precompute prefix hash and power array for a chosen base and mod.
    base = 131
    mod = 10**9 + 7
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + nums[i]) % mod
        power[i+1] = (power[i] * base) % mod

    # Function to get hash of subarray nums[l:r] (r is exclusive).
    def get_hash(l, r):
        return (prefix_hash[r] - prefix_hash[l] * power[r-l]) % mod

    countA = 0  # Count for splits satisfying condition A.
    countB = 0  # Count for splits satisfying condition B.
    countBoth = 0  # Count for splits satisfying both conditions.

    # Condition A: nums1 is prefix of nums2.
    # For subarray nums1 = nums[0..i-1], we need to check that
    # nums[i..2*i-1] equals nums[0..i-1]. Then any j in [2*i, n) yields valid split.
    for i in range(1, n):  # i is length of nums1.
        # Ensure that nums2 has at least i elements and there is a non-empty nums3
        if 2 * i > n - 1:
            break
        if get_hash(0, i) == get_hash(i, 2*i):
            countA += (n - 2*i)

    # Condition B: nums2 is prefix of nums3.
    # For every split point j (start of nums3), consider possible i's for nums1.
    for j in range(2, n):
        # For a fixed j, let len(nums2) = (j - i) which must be <= len(nums3)=n-j.
        # So we require j - i <= n - j, i >= j - (n - j)
        min_i = max(1, j - (n - j))
        for i in range(min_i, j):
            len_seg = j - i
            # Check if nums[i...j-1] equals first len_seg elements of nums3.
            if j + len_seg > n:
                continue  # Not enough elements for nums3.
            if get_hash(i, j) == get_hash(j, j + len_seg):
                countB += 1

    # Count splits that satisfy both conditions.
    # These splits require that both conditions hold.
    for i in range(1, n):
        if 2 * i > n - 1:
            break
        # First ensure condition A holds for this i.
        if get_hash(0, i) != get_hash(i, 2*i):
            continue
        # Now count j in [2*i, n) for which condition B holds as well.
        for j in range(2*i, n):
            len_seg = j - i
            if j + len_seg > n:
                continue
            if get_hash(i, j) == get_hash(j, j + len_seg):
                countBoth += 1

    # Total beautiful splits:
    # A split is beautiful if conditionA OR conditionB holds.
    total = countA + countB - countBoth
    return total

# Example usage:
print(countBeautifulSplits([1,1,2,1]))  # Expected output: 2
← Back to All Questions