Maximum Valid Split Positions II solution and explanation
The problem
You are given an integer array nums.
You may remove at most one element from nums. Let arr be the array of remaining elements in their original order, and let m be its length.
A split position i of arr is valid if:
0 <= i < m - 1, andgcd(arr[0..i]) == gcd(arr[i + 1..m - 1]).
An array of length 1 has no valid split positions.
The score of arr is the number of valid split positions in it.
Return the maximum possible score of arr.
Here, gcd(a) denotes the greatest common divisor of all elements in the array a.
Example 1:
Input: nums = [10,30,15,10]
Output: 2
Explanation:
One optimal solution is to remove nums[2] = 15. Then arr = [10, 30, 10].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 10 | 10 |
| 1 | 10 | 10 |
All split positions are valid. Thus, the answer is 2.
Example 2:
Input: nums = [2,10,14]
Output: 1
Explanation:
One optimal solution is to not remove any element. Then arr = [2, 10, 14].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 2 | 2 |
| 1 | 2 | 14 |
Only the split position at index 0 is valid. Thus, the answer is 1.
Example 3:
Input: nums = [2,4]
Output: 0
Explanation:
The only remaining array that has a split position is arr = [2, 4].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 2 | 4 |
There are no valid split positions. Thus, the answer is 0.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: Given an array of positive integers, you can remove at most one element. After removal, the array splits into two non-empty contiguous parts. A split is valid if the GCD of the left part and the GCD of the right part are both greater than 1. Return the maximum number of valid split positions achievable after removing at most one element.
Approach 1: Brute Force (O(n^2) time, O(1) space)
For each possible removal index, compute the GCD of every prefix and suffix from scratch using a nested loop. This involves repeatedly calling the Euclidean algorithm for each segment, leading to O(n^2) GCD computations. While straightforward, it is impractical for large inputs and only useful for understanding the problem statement. You would iterate over all removal candidates and for each, compute left and right GCDs by scanning the array, which is inefficient.
Approach 2: Prefix and Suffix GCD + Enumerate Candidate Removed Indices (O(n) time, O(n) space)
Precompute prefix GCD arrays where prefix[i] is the GCD of elements from index 0 to i, and suffix GCD arrays where suffix[i] is the GCD of elements from index i to n-1. Then, for each possible removal index (including removing no element), compute the GCD of the left part as prefix[i-1] and the right part as suffix[i+1]. Check if both are greater than 1. This reduces the problem to O(n) time because each GCD query is O(1) after preprocessing. The key insight is that removing an element only affects the GCD of segments that include it; by precomputing prefix and suffix GCDs, you avoid recomputing from scratch. This approach is optimal and works for all cases.
Recommended for interviews: Interviewers expect you to recognize that brute force is too slow and move to the prefix-suffix technique. The brute force shows you understand the problem, but the optimal solution demonstrates your ability to precompute and reuse intermediate results—a core skill in arrays and GCD problems. Always aim for the O(n) solution in a coding interview.
Solution
Following the idea of the previous problem, for an array arr of length m we precompute the prefix GCD array pre and the suffix GCD array suf. A split position i is valid if and only if pre[i] = suf[i + 1], so the score of arr is the number of indices satisfying this condition. However, n can be as large as 10^5 here, so enumerating every removed index and spending O(n) on each of them is too slow.
Observe that every entry of the prefix GCD sequence divides the previous one, so it is at least halved whenever it changes, meaning the whole sequence changes only O(log M) times. If the prefix GCD does not change at index i, i.e. pre[i] = pre[i - 1], which is equivalent to pre[i - 1] dividing nums[i], then removing nums[i] leaves every prefix GCD unchanged. Likewise, if the suffix GCD does not change at index i either, removing it leaves every suffix GCD unchanged as well. In that case the only effect of the removal is to merge the split positions i - 1 and i into a single one, and those two positions are either both valid or both invalid, so the score can only decrease.
Therefore only the indices where the prefix GCD changes or the suffix GCD changes are worth enumerating, and there are at most O(log M) of them. We call mark once forward and once backward to collect the candidate indices, then compute the score with calc after removing each candidate, and take the maximum together with the score of the untouched array.
The time complexity is O(n times log^2 M), and the space complexity is O(n). Here, n is the length of the array nums, and M is the maximum value in the array nums.
class Solution:
def maxValidSplits(self, nums: List[int]) -> int:
n = len(nums)
def calc(arr):
m = len(arr)
pre = [0] * m
suf = [0] * m
pre[0] = arr[0]
for i in range(1, m):
pre[i] = gcd(pre[i - 1], arr[i])
suf[-1] = arr[-1]
for i in range(m - 2, -1, -1):
suf[i] = gcd(suf[i + 1], arr[i])
ans = 0
for i in range(m - 1):
if pre[i] == suf[i + 1]:
ans += 1
return ans
def mark(arr):
pos = [False] * n
pos[0] = True
g = arr[0]
for i in range(1, n):
ng = gcd(g, arr[i])
pos[i] = ng != g
g = ng
return pos
pos1 = mark(nums)
pos2 = mark(nums[::-1])
ans = calc(nums)
for i in range(n):
if pos1[i] or pos2[n - 1 - i]:
arr = nums[:i] + nums[i + 1 :]
ans = max(ans, calc(arr))
return ansclass Solution {
public int maxValidSplits(int[] nums) {
int n = nums.length;
boolean[] pos1 = mark(nums);
int[] rev = nums.clone();
for (int i = 0; i < n / 2; ++i) {
int t = rev[i];
rev[i] = rev[n - 1 - i];
rev[n - 1 - i] = t;
}
boolean[] pos2 = mark(rev);
int ans = calc(nums);
for (int i = 0; i < n; ++i) {
if (pos1[i] || pos2[n - 1 - i]) {
int[] arr = new int[n - 1];
for (int j = 0, k = 0; j < n; ++j) {
if (j != i) {
arr[k++] = nums[j];
}
}
ans = Math.max(ans, calc(arr));
}
}
return ans;
}
private boolean[] mark(int[] nums) {
int n = nums.length;
boolean[] pos = new boolean[n];
pos[0] = true;
int g = nums[0];
for (int i = 1; i < n; ++i) {
int ng = gcd(g, nums[i]);
pos[i] = ng != g;
g = ng;
}
return pos;
}
private int calc(int[] arr) {
int n = arr.length;
int[] pre = new int[n];
int[] suf = new int[n];
pre[0] = arr[0];
for (int i = 1; i < n; ++i) {
pre[i] = gcd(pre[i - 1], arr[i]);
}
suf[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; --i) {
suf[i] = gcd(suf[i + 1], arr[i]);
}
int ans = 0;
for (int i = 0; i + 1 < n; ++i) {
if (pre[i] == suf[i + 1]) {
++ans;
}
}
return ans;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
}class Solution {
public:
int maxValidSplits(vector<int>& nums) {
int n = nums.size();
vector<bool> pos1 = mark(nums);
vector<int> rev = nums;
reverse(rev.begin(), rev.end());
vector<bool> pos2 = mark(rev);
int ans = calc(nums);
for (int i = 0; i < n; ++i) {
if (pos1[i] || pos2[n - 1 - i]) {
vector<int> arr;
arr.reserve(n - 1);
for (int j = 0; j < n; ++j) {
if (i != j) {
arr.push_back(nums[j]);
}
}
ans = max(ans, calc(arr));
}
}
return ans;
}
private:
vector<bool> mark(const vector<int>& nums) {
int n = nums.size();
vector<bool> pos(n);
pos[0] = true;
int g = nums[0];
for (int i = 1; i < n; ++i) {
int ng = gcd(g, nums[i]);
pos[i] = ng != g;
g = ng;
}
return pos;
}
int calc(const vector<int>& arr) {
int n = arr.size();
vector<int> pre(n), suf(n);
pre[0] = arr[0];
for (int i = 1; i < n; ++i) {
pre[i] = gcd(pre[i - 1], arr[i]);
}
suf[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; --i) {
suf[i] = gcd(suf[i + 1], arr[i]);
}
int ans = 0;
for (int i = 0; i + 1 < n; ++i) {
if (pre[i] == suf[i + 1]) {
++ans;
}
}
return ans;
}
};function maxValidSplits(nums: number[]): number {
const n = nums.length;
const pos1 = mark(nums);
const rev = [...nums].reverse();
const pos2 = mark(rev);
let ans = calc(nums);
for (let i = 0; i < n; ++i) {
if (pos1[i] || pos2[n - 1 - i]) {
const arr = nums.slice(0, i).concat(nums.slice(i + 1));
ans = Math.max(ans, calc(arr));
}
}
return ans;
}
function mark(nums: number[]): boolean[] {
const n = nums.length;
const pos = Array(n).fill(false);
pos[0] = true;
let g = nums[0];
for (let i = 1; i < n; ++i) {
const ng = gcd(g, nums[i]);
pos[i] = ng !== g;
g = ng;
}
return pos;
}
function calc(arr: number[]): number {
const n = arr.length;
const pre = Array(n);
const suf = Array(n);
pre[0] = arr[0];
for (let i = 1; i < n; ++i) {
pre[i] = gcd(pre[i - 1], arr[i]);
}
suf[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; --i) {
suf[i] = gcd(suf[i + 1], arr[i]);
}
let ans = 0;
for (let i = 0; i + 1 < n; ++i) {
if (pre[i] === suf[i + 1]) {
++ans;
}
}
return ans;
}
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}func maxValidSplits(nums []int) int {
n := len(nums)
pos1 := mark(nums)
rev := make([]int, n)
for i := 0; i < n; i++ {
rev[i] = nums[n-1-i]
}
pos2 := mark(rev)
ans := calc(nums)
for i := 0; i < n; i++ {
if pos1[i] || pos2[n-1-i] {
arr := make([]int, 0, n-1)
for j := 0; j < n; j++ {
if i != j {
arr = append(arr, nums[j])
}
}
ans = max(ans, calc(arr))
}
}
return ans
}
func mark(nums []int) []bool {
n := len(nums)
pos := make([]bool, n)
pos[0] = true
g := nums[0]
for i := 1; i < n; i++ {
ng := gcd(g, nums[i])
pos[i] = ng != g
g = ng
}
return pos
}
func calc(arr []int) int {
n := len(arr)
pre := make([]int, n)
suf := make([]int, n)
pre[0] = arr[0]
for i := 1; i < n; i++ {
pre[i] = gcd(pre[i-1], arr[i])
}
suf[n-1] = arr[n-1]
for i := n - 2; i >= 0; i-- {
suf[i] = gcd(suf[i+1], arr[i])
}
ans := 0
for i := 0; i+1 < n; i++ {
if pre[i] == suf[i+1] {
ans++
}
}
return ans
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Only for small arrays or understanding the problem |
| Prefix/Suffix GCD + Enumeration | O(n) | O(n) | General case, optimal for large arrays |
Frequently asked questions
Is Maximum Valid Split Positions II easy or hard?
It is rated Hard on FleetCode with a 28% acceptance rate. The difficulty comes from optimizing beyond brute force and handling edge cases correctly.
Maximum Valid Split Positions II Python/Java solution
In Python, you can use a list comprehension with math.gcd to build prefix and suffix arrays. In Java, use int arrays and a helper gcd function. Both implementations run in O(n) time.
How to solve Maximum Valid Split Positions II in O(n)?
Compute prefix GCDs where prefix[i] = gcd(prefix[i-1], arr[i]) and suffix GCDs where suffix[i] = gcd(suffix[i+1], arr[i]). Then for each index i, check if gcd(prefix[i-1], suffix[i+1]) > 1 (with edge cases for boundaries). Count how many such indices exist.
What is the best approach for Maximum Valid Split Positions II?
The best approach is to precompute prefix and suffix GCD arrays and then enumerate each possible removal index. This runs in O(n) time and O(n) space, which is optimal for this problem.
Is Maximum Valid Split Positions II asked at Google/Amazon/Meta?
This problem is tagged as Hard and appears in coding interviews at top tech companies like Google, Amazon, and Meta. It tests your ability to optimize with prefix/suffix computations.
What data structure is used in Maximum Valid Split Positions II?
The optimal solution uses two arrays to store prefix and suffix GCD values. No complex data structures are needed—just basic arrays and the Euclidean algorithm for GCD computation.
What is the time complexity of Maximum Valid Split Positions II?
The optimal solution using prefix and suffix GCD arrays runs in O(n) time, where n is the length of the input array. The brute force approach takes O(n^2) time.