Skip to main content
Talentd

Maximum Valid Split Positions I - Solution & Explanation

MediumArrayMathEnumerationNumber Theory9 min read
Practice this problem

Problem Statement

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, and
  • gcd(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 <= 1000
  • 1 <= nums[i] <= 109​​​​​​​

Approach Overview

Problem Overview: Given an array of positive integers, you can remove exactly one element to split the array into a non-empty prefix and suffix. A split is valid if the GCD (greatest common divisor) of the prefix and the GCD of the suffix are coprime (i.e., their GCD is 1). Return the maximum number of valid split positions across all possible removals.

Approach 1: Brute Force with GCD Recalculation (O(n^2 log A) Time, O(1) Space)

For each possible removal index, compute the GCD of the prefix and suffix from scratch using a loop. This means for every removal you iterate through the entire array, leading to O(n^2) GCD computations. While simple to implement, it fails for large inputs because each GCD call takes O(log A) time, making the total O(n^2 log A). Use this only for small arrays or to verify correctness of an optimal solution.

Approach 2: Prefix and Suffix GCD Precomputation (O(n log A) Time, O(n) Space)

Precompute two arrays: prefixGCD[i] = GCD of elements from index 0 to i, and suffixGCD[i] = GCD of elements from index i to n-1. After removing index k, the prefix GCD is prefixGCD[k-1] (if k > 0) and the suffix GCD is suffixGCD[k+1] (if k < n-1). Then check if gcd(prefixGCD[k-1], suffixGCD[k+1]) == 1. This reduces each query to O(log A) for the final GCD check, giving total O(n log A). This is the optimal approach because it avoids redundant GCD computations and is easy to implement in any language.

Recommended for interviews: Interviewers expect the prefix/suffix precomputation approach because it demonstrates understanding of how to avoid repeated work. The brute force shows you can reason about the problem, but the optimal solution shows you can optimize using auxiliary arrays. Always start with brute force to clarify the problem, then transition to the optimal solution.

This problem is a classic example of array manipulation combined with mathematics (GCD). You can also relate it to prefix-sum techniques, though here we use prefix GCD instead of sum.

Solution

Since the array length satisfies n leq 1000, we can enumerate the index of the removed element (including the case where nothing is removed) to obtain the array arr, compute the score of arr, and take the maximum over all cases.

For an array arr of length m, we precompute the prefix GCD array pre and the suffix GCD array suf, where pre[i] = \gcd(arr[0..i]) and suf[i] = \gcd(arr[i..m - 1]). 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.

The time complexity is O(n^2 times log 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2 log A)O(1)Small arrays or verifying correctness
Prefix & Suffix GCD PrecomputationO(n log A)O(n)General case, optimal for large inputs

Video Solutions (2)

LeetCode Biweekly Contest 190 🔥 | 3 Problems Solved | Q1–Q3 | 4034, 4035, 4036

EdgeCaseOffByOne14:49321 views
Video 1 of 2

Frequently Asked Questions

Is Maximum Valid Split Positions I easy or hard?
It's rated Medium on FleetCode. The brute force is straightforward, but optimizing to O(n log A) requires recognizing that prefix/suffix precomputation avoids redundant work. It's a good test of algorithmic thinking.
Maximum Valid Split Positions I Python/Java solution
In Python, use math.gcd for GCD. Precompute prefix and suffix lists, then iterate over removal indices. In Java, use BigInteger.gcd or implement Euclidean algorithm. Both solutions run in O(n log A) time.
How to solve Maximum Valid Split Positions I in O(n)?
You cannot achieve pure O(n) because computing GCD of two numbers takes O(log A) time. However, you can reduce the overall complexity to O(n log A) by precomputing prefix and suffix GCDs, which is considered linear in practice for typical constraints.
What is the best approach for Maximum Valid Split Positions I?
The best approach uses prefix and suffix GCD precomputation. Compute prefixGCD and suffixGCD arrays in O(n) time, then for each removal check if gcd(prefixGCD[k-1], suffixGCD[k+1]) == 1. This runs in O(n log A) time and O(n) space.
Is Maximum Valid Split Positions I asked at Google/Amazon/Meta?
While not confirmed, this problem type (array splitting with GCD constraints) is common in interviews at top tech companies like Google and Amazon. It tests your ability to optimize repeated calculations using precomputation.
What data structure is used in Maximum Valid Split Positions I?
The solution primarily uses arrays to store prefix and suffix GCD values. No complex data structures like hash maps or trees are needed—just simple integer arrays.
What is the time complexity of Maximum Valid Split Positions I?
The optimal solution runs in O(n log A) time, where n is the array length and A is the maximum element value (due to GCD computation). The space complexity is O(n) for storing prefix and suffix GCD arrays.

Ready to solve this problem?

Practice Maximum Valid Split Positions I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Valid Split Positions II