Skip to main content
Talentd

Minimum Subarrays in a Valid Split - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDynamic ProgrammingNumber Theory8 min read
Practice this problem

Problem Statement

You are given an integer array nums.

Splitting of an integer array nums into subarrays is valid if:

  • the greatest common divisor of the first and last elements of each subarray is greater than 1, and
  • each element of nums 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:

  • The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
  • A subarray is a contiguous non-empty part of an array.

 

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 <= 1000
  • 1 <= nums[i] <= 105

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Split EnumerationO(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

Video Solution

2464. Minimum Subarrays in a Valid Split - Week 5/5 Leetcode October Challenge • Programming Live with Larry • 351 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Subarrays in a Valid Split easy or hard?
Minimum Subarrays in a Valid Split is rated Medium difficulty. The recursion and DP structure are straightforward, but recognizing that the condition only depends on gcd of the first and last elements requires some number theory insight.
Minimum Subarrays in a Valid Split Python/Java solution
The memoized DFS approach translates cleanly to Python, Java, C++, and Go. Implement a recursive function dfs(i) that returns the minimum number of segments starting from index i. Store results in a DP array or hash map to ensure each index is computed once.
How to solve Minimum Subarrays in a Valid Split in O(n)?
Near‑linear solutions rely on number theory. By tracking prime factors of each number and connecting indices that share a factor, you can jump directly to valid endpoints instead of scanning the entire suffix. With efficient factorization and bookkeeping, the complexity approaches O(n logA).
What is the best approach for Minimum Subarrays in a Valid Split?
The most practical solution uses memoized depth‑first search (top‑down dynamic programming). For each starting index, try extending the subarray and check if gcd(nums[i], nums[j]) > 1. Cache results for each index to avoid recomputation. This reduces the complexity to O(n^2 logA) time with O(n) space.
Is Minimum Subarrays in a Valid Split asked at Google/Amazon/Meta?
Problems combining dynamic programming with number theory constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving GCD conditions, prime factors, and optimal partitioning are common in high‑level algorithm rounds.
What data structure is used in Minimum Subarrays in a Valid Split?
The core solution uses an array for memoization combined with recursion (DFS). Each state represents the minimum splits needed from a given index. The algorithm also relies on the gcd operation from number theory to validate subarray boundaries.
What is the time complexity of Minimum Subarrays in a Valid Split?
The common dynamic programming approach runs in O(n^2 logA) time. There are n DP states, and each state scans up to n elements while computing gcd values that take O(logA) time. Space complexity is O(n) for the memoization table.

Ready to solve this problem?

Practice Minimum Subarrays in a Valid Split with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Split Into Subarrays With GCD Greater Than One