You are given an integer array nums.
Splitting of an integer array nums into subarrays is valid if:
1, andnums belongs to exactly one subarray.Return the minimum number of subarrays in a valid subarray splitting of nums. If a valid subarray splitting is not possible, return -1.
Note that:
Example 1:
Input: nums = [2,6,3,4,3] Output: 2 Explanation: We can create a valid split in the following way: [2,6] | [3,4,3]. - The starting element of the 1st subarray is 2 and the ending is 6. Their greatest common divisor is 2, which is greater than 1. - The starting element of the 2nd subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1. It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.
Example 2:
Input: nums = [3,5] Output: 2 Explanation: We can create a valid split in the following way: [3] | [5]. - The starting element of the 1st subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1. - The starting element of the 2nd subarray is 5 and the ending is 5. Their greatest common divisor is 5, which is greater than 1. It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.
Example 3:
Input: nums = [1,2,1] Output: -1 Explanation: It is impossible to create valid split.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 105Problem Overview: Given an integer array nums, split it into the minimum number of contiguous subarrays such that in every subarray the gcd(first, last) > 1. If no such split exists, return -1. The challenge is deciding where each subarray should end while minimizing the total count.
Approach 1: Brute Force Split Enumeration (O(n^3 logA) time, O(1) space)
Try every possible split configuration. For each starting index i, attempt all ending indices j and check if gcd(nums[i], nums[j]) > 1. If valid, recursively evaluate the remainder of the array. Without caching, the same suffix gets recomputed many times, leading to exponential recursion that effectively behaves like O(n^3 logA) due to repeated GCD checks. This approach mainly helps you understand the structure of the problem before applying dynamic programming.
Approach 2: Memoization Search (Top-Down DP) (O(n^2 logA) time, O(n) space)
Use depth‑first search with memoization on the starting index. Define dfs(i) as the minimum number of valid subarrays needed to cover the suffix starting at index i. Iterate j from i to the end of the array and check the gcd(nums[i], nums[j]). Whenever the value is greater than 1, the segment [i, j] is valid, so compute 1 + dfs(j + 1). Store the result in a memo table so each index is solved once. The outer recursion runs at most n times, and each state scans up to n positions with a gcd computation costing O(logA).
This approach combines ideas from dynamic programming and number theory. The DP handles optimal substructure (minimum splits for each suffix), while the mathematical constraint relies on the GCD property. The array is scanned repeatedly, so the logic remains simple and easy to implement during interviews.
Further optimization is possible by tracking shared prime factors and jumping directly to candidate indices. That reduces unnecessary checks but increases implementation complexity. For most interview settings, the memoized DFS is clear, correct, and fast enough.
Recommended for interviews: Start with the brute force explanation to show you understand the split decisions. Then transition to the memoized DFS. Interviewers typically expect the O(n^2 logA) dynamic programming solution because it demonstrates recursion design, caching, and efficient use of array traversal.
We design a function dfs(i) to represent the minimum number of partitions starting from index i. For index i, we can enumerate all partition points j, i.e., i leq j < n, where n is the length of the array. For each partition point j, we need to determine whether the greatest common divisor of nums[i] and nums[j] is greater than 1. If it is greater than 1, we can partition, and the number of partitions is 1 + dfs(j + 1); otherwise, the number of partitions is +infty. Finally, we take the minimum of all partition numbers.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Split Enumeration | O(n^3 logA) | O(1) | Conceptual baseline to understand all possible split points |
| Memoized DFS (Top‑Down Dynamic Programming) | O(n^2 logA) | O(n) | General solution with manageable complexity and clean implementation |
| Prime Factor Jump Optimization | ~O(n logA) | O(n) | When optimizing large inputs by linking indices sharing common factors |
2464. Minimum Subarrays in a Valid Split - Week 5/5 Leetcode October Challenge • Programming Live with Larry • 348 views views
Watch 2 more video solutions →Practice Minimum Subarrays in a Valid Split with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor