Count Beautiful Splits in an Array

Medium
1671.

Count Beautiful Splits in an Array

Count Beautiful Splits in an Array is a medium coding problem on arrays and dynamic programming, asked in Google interviews.

You are given an array nums. A split of nums into three non-empty consecutive parts nums1, nums2 and nums3 (so that nums = nums1 + nums2 + nums3) is beautiful if at least one of the following holds:

  • nums1 is a prefix of nums2, or
  • nums2 is a prefix of nums3.

Return the number of beautiful splits.

Example 1

Input
nums = [1,1,2,1]
Output
2
Explanation
[1] | [1,2] | [1] works because [1] is a prefix of [1,2]; [1] | [1] | [2,1] works too.

Example 2

Input
nums = [1,2,3,4]
Output
0

Example 3

Input
nums = [1,1,1]
Output
1
Explanation
The only split is [1] | [1] | [1], and [1] is a prefix of [1].

Constraints

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var beautifulSplits = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Beautiful Splits in an Array — Problem & Solution

Count Beautiful Splits in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Beautiful Splits in an Array is a medium coding problem on arrays and dynamic programming, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums. A split of nums into three non-empty consecutive parts nums1, nums2 and nums3 (so that nums = nums1 + nums2 + nums3) is beautiful if at least one of the following holds:

  • nums1 is a prefix of nums2, or
  • nums2 is a prefix of nums3.

Return the number of beautiful splits.

Example 1

Input: nums = [1,1,2,1]
Output: 2
Explanation: [1] | [1,2] | [1] works because [1] is a prefix of [1,2]; [1] | [1] | [2,1] works too.

Example 2

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

Example 3

Input: nums = [1,1,1]
Output: 1
Explanation: The only split is [1] | [1] | [1], and [1] is a prefix of [1].

Constraints

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

Hints for Count Beautiful Splits in an Array

  1. Hint 1

    A split is fixed by two cut points: nums2 starts at i and nums3 starts at j (1 <= i < j < n). That is only O(n^2) splits — the comparisons are the expensive part.

  2. Hint 2

    "A is a prefix of B" for two suffixes of the same array is a longest-common-prefix question: it holds when |A| <= |B| and lcp(start of A, start of B) >= |A|.

  3. Hint 3

    Precompute lcp[a][b] for all pairs of start positions with lcp[a][b] = nums[a] == nums[b] ? lcp[a + 1][b + 1] + 1 : 0, filled from the back.

How to solve Count Beautiful Splits in an Array

There are only O(n^2) splits, so each must be checked in O(1). Both conditions compare two subarrays that start at known positions, which is exactly what a longest-common-prefix table over pairs of suffixes answers.

Approach

  1. Fill lcp[a][b] (for a < b) from the end: lcp[a][b] = lcp[a + 1][b + 1] + 1 when nums[a] == nums[b], else 0.
  2. For each i in 1..n-2 (start of nums2) and j in i+1..n-1 (start of nums3):
  3. Condition 1: i <= j - i and lcp[0][i] >= i (nums1 has length i).
  4. Condition 2: j - i <= n - j and lcp[i][j] >= j - i (nums2 has length j - i).
  5. Count the splits where either condition holds.

Why it works

A is a prefix of B exactly when A is not longer than B and their first |A| elements agree, which is lcp >= |A| for the suffixes where they start. The recurrence for lcp is the standard one: two suffixes share a prefix of length L + 1 iff their first elements match and the suffixes after them share L.

Complexity

  • Time — O(n^2)
  • Space — O(n^2)

Pitfalls

  • Count a split once even when both conditions hold — use or, not two separate counters.
  • Check the length condition too: lcp alone can exceed the length of the shorter part.

Reference solution

Python

from typing import List

def beautifulSplits(nums: List[int]) -> int:
    n = len(nums)
    lcp = [[0] * (n + 1) for _ in range(n + 1)]
    for a in range(n - 1, -1, -1):
        for b in range(n - 1, a, -1):
            if nums[a] == nums[b]:
                lcp[a][b] = lcp[a + 1][b + 1] + 1
    count = 0
    for i in range(1, n - 1):
        first = lcp[0][i] >= i
        for j in range(i + 1, n):
            if (first and i <= j - i) or (j - i <= n - j and lcp[i][j] >= j - i):
                count += 1
    return count

Java

public static int beautifulSplits(int[] nums) {
    int n = nums.length;
    int[][] lcp = new int[n + 1][n + 1];
    for (int a = n - 1; a >= 0; a--) {
        for (int b = n - 1; b > a; b--) {
            if (nums[a] == nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
        }
    }
    int count = 0;
    for (int i = 1; i < n - 1; i++) {
        boolean first = lcp[0][i] >= i;
        for (int j = i + 1; j < n; j++) {
            if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
        }
    }
    return count;
}

C++

int beautifulSplits(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
    for (int a = n - 1; a >= 0; a--) {
        for (int b = n - 1; b > a; b--) {
            if (nums[a] == nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
        }
    }
    int count = 0;
    for (int i = 1; i < n - 1; i++) {
        bool first = lcp[0][i] >= i;
        for (int j = i + 1; j < n; j++) {
            if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
        }
    }
    return count;
}

JavaScript

var beautifulSplits = function(nums) {
    var n = nums.length;
    var lcp = [];
    for (var r = 0; r <= n; r++) lcp.push(new Array(n + 1).fill(0));
    for (var a = n - 1; a >= 0; a--) {
        for (var b = n - 1; b > a; b--) {
            if (nums[a] === nums[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
        }
    }
    var count = 0;
    for (var i = 1; i < n - 1; i++) {
        var first = lcp[0][i] >= i;
        for (var j = i + 1; j < n; j++) {
            if ((first && i <= j - i) || (j - i <= n - j && lcp[i][j] >= j - i)) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming