LeetCode 3605 - Minimum Stability Factor of Array

We are given an array nums and an integer maxC. A subarray is called stable if the greatest common divisor (HCF/GCD) of all elements in that subarray is at least 2. The stability factor of the entire array is defined as the length of the longest stable subarray.

leetcodehardarraymathbinary-searchgreedysegment-treenumber-theory

LeetCode Problem 3605

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Greedy, Segment Tree, Number Theory

Solution

LeetCode 3605 - Minimum Stability Factor of Array

Problem Understanding

We are given an array nums and an integer maxC.

A subarray is called stable if the greatest common divisor (HCF/GCD) of all elements in that subarray is at least 2.

The stability factor of the entire array is defined as the length of the longest stable subarray.

We are allowed to modify at most maxC elements, and each modified element can be changed to any integer we want.

Our goal is to minimize the stability factor after performing at most maxC modifications.

The key observation is that after changing an element, we can choose a value such as 1 or a suitable prime so that it destroys any stable subarray passing through that position. Therefore, modifications act as "break points" that can invalidate many stable subarrays simultaneously.

The constraints are large:

  • n ≤ 100000
  • nums[i] ≤ 10^9

This immediately rules out any solution that examines all subarrays.

Some important edge cases are:

  • Arrays containing only 1s. No stable subarray exists because every GCD equals 1.
  • Arrays where every element is even. The entire array is stable.
  • maxC = 0, meaning we cannot modify anything.
  • maxC = n, meaning every position may be changed.
  • Stable regions that are completely disjoint, where a single modification cannot destroy both regions.

The challenge is to determine the minimum possible longest stable subarray length after strategically placing at most maxC modifications.

Approaches

Brute Force

A brute force solution would consider every possible set of modifications and compute the resulting longest stable subarray.

Even if we ignore modifications, determining all stable subarrays by checking every interval requires O(n²) intervals. Computing GCDs for each interval leads to at least O(n² log V) complexity.

Once modifications are included, the search space becomes exponential because every element can either be modified or not.

Therefore, brute force is completely infeasible.

Key Insight

Suppose we want to know whether it is possible to make the stability factor at most L.

This means that every stable subarray must have length at most L.

Equivalently:

  • Any subarray of length L + 1 whose GCD is at least 2 must be destroyed.
  • Destroying such a subarray requires modifying at least one position inside it.

Thus the problem becomes:

Given all length L+1 windows with GCD ≥ 2, can we hit every such window using at most maxC modified positions?

This is a classic interval stabbing problem.

The remaining challenge is efficiently identifying all windows of length L+1 whose GCD is at least 2.

Since n is large, we need fast range GCD queries. A segment tree provides:

  • Range GCD query in O(log n)
  • Building in O(n)

For a fixed L:

  1. Find every interval [i, i+L] whose GCD ≥ 2.
  2. These intervals must all be stabbed.
  3. The minimum number of stabbing points for intervals is obtained greedily:
  • Sort by right endpoint (already naturally ordered).
  • Place a modification at the right endpoint of the first uncovered interval.
  • Continue.

If the required number of modifications is at most maxC, then L is feasible.

Since feasibility is monotonic, binary search on L gives the answer.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates modifications and stable subarrays
Optimal O(n log² n) O(n) Binary search + segment tree + greedy interval stabbing

Algorithm Walkthrough

Step 1

Build a segment tree storing GCD values.

This allows us to query the GCD of any interval [l, r] in O(log n) time.

Step 2

Binary search the answer L.

The answer lies between:

  • 0
  • n

For each candidate L, we check whether it is possible to make every stable subarray have length at most L.

Step 3

For the current L, examine every window of length L+1.

The window starting at i is:

[i, i+L]

Using the segment tree, compute its GCD.

If the GCD is at least 2, then this interval must be destroyed.

Step 4

Greedily stab all bad intervals.

Maintain:

  • used = number of modifications chosen
  • lastChosen = most recent modification position

Process intervals in increasing right endpoint order.

For interval [l, r]:

  • If lastChosen already lies inside the interval, it is covered.
  • Otherwise place a modification at r.
  • Increment used.

This greedy strategy produces the minimum number of stabbing points.

Step 5

If used <= maxC, then L is feasible.

Otherwise it is impossible.

Step 6

Use binary search to find the smallest feasible L.

That value is the minimum possible stability factor.

Why it works

Every stable subarray of length greater than L contains a stable subarray of exactly length L+1, because the GCD of a subarray cannot increase when extending it. Therefore eliminating all stable windows of length L+1 automatically eliminates all longer stable subarrays.

Each such window becomes an interval that must contain at least one modified position. The problem therefore reduces to finding the minimum number of points needed to hit all intervals. The standard greedy interval stabbing algorithm is optimal. Since feasibility is monotonic with respect to L, binary search correctly finds the minimum achievable stability factor.

Python Solution

from typing import List
from math import gcd

class Solution:
    def minStable(self, nums: List[int], maxC: int) -> int:
        n = len(nums)

        size = 1
        while size < n:
            size <<= 1

        seg = [0] * (2 * size)

        for i in range(n):
            seg[size + i] = nums[i]

        for i in range(size - 1, 0, -1):
            seg[i] = gcd(seg[i * 2], seg[i * 2 + 1])

        def range_gcd(left: int, right: int) -> int:
            left += size
            right += size

            res_left = 0
            res_right = 0

            while left <= right:
                if left & 1:
                    res_left = gcd(res_left, seg[left])
                    left += 1

                if not (right & 1):
                    res_right = gcd(seg[right], res_right)
                    right -= 1

                left >>= 1
                right >>= 1

            return gcd(res_left, res_right)

        def feasible(limit: int) -> bool:
            used = 0
            last_chosen = -1

            for start in range(n - limit):
                end = start + limit

                if range_gcd(start, end) < 2:
                    continue

                if last_chosen < start:
                    used += 1
                    last_chosen = end

                    if used > maxC:
                        return False

            return True

        left = 0
        right = n

        while left < right:
            mid = (left + right) // 2

            if feasible(mid):
                right = mid
            else:
                left = mid + 1

        return left

Implementation Explanation

The segment tree stores GCD values for all ranges. Every internal node contains the GCD of its two children.

The range_gcd() function performs a standard iterative segment tree query and returns the GCD of any interval in O(log n) time.

The feasible(limit) function checks whether a stability factor of at most limit can be achieved. It scans every window of length limit + 1. Whenever such a window has GCD at least 2, it becomes a bad interval that must be hit by a modification.

The greedy interval stabbing algorithm is implemented using last_chosen. If the previous chosen position already lies within the current interval, that interval is covered. Otherwise a new modification is placed at the interval's right endpoint.

Finally, binary search finds the smallest feasible limit.

Go Solution

package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func minStable(nums []int, maxC int) int {
	n := len(nums)

	size := 1
	for size < n {
		size <<= 1
	}

	seg := make([]int, 2*size)

	for i := 0; i < n; i++ {
		seg[size+i] = nums[i]
	}

	for i := size - 1; i > 0; i-- {
		seg[i] = gcd(seg[i<<1], seg[i<<1|1])
	}

	rangeGCD := func(left, right int) int {
		left += size
		right += size

		resLeft := 0
		resRight := 0

		for left <= right {
			if left&1 == 1 {
				resLeft = gcd(resLeft, seg[left])
				left++
			}

			if right&1 == 0 {
				resRight = gcd(seg[right], resRight)
				right--
			}

			left >>= 1
			right >>= 1
		}

		return gcd(resLeft, resRight)
	}

	feasible := func(limit int) bool {
		used := 0
		lastChosen := -1

		for start := 0; start < n-limit; start++ {
			end := start + limit

			if rangeGCD(start, end) < 2 {
				continue
			}

			if lastChosen < start {
				used++
				lastChosen = end

				if used > maxC {
					return false
				}
			}
		}

		return true
	}

	left, right := 0, n

	for left < right {
		mid := (left + right) / 2

		if feasible(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

Go Specific Notes

The Go implementation follows the same algorithm as the Python version.

The segment tree is implemented using slices. All arithmetic safely fits inside Go's int type because values are at most 10^9, and GCD computations never exceed the original values. No special overflow handling is required.

Worked Examples

Example 1

Input:

nums = [3,5,10]
maxC = 1

Binary search eventually checks L = 1.

Windows of length 2:

Window GCD
[3,5] 1
[5,10] 5

Bad interval:

Interval
[1,2]

Greedy stabbing:

Interval Action Chosen
[1,2] choose 2 {2}

Only one modification is needed.

Therefore L = 1 is feasible.

Answer:

1

Example 2

Input:

nums = [2,6,8]
maxC = 2

Check L = 1.

Windows of length 2:

Window GCD
[2,6] 2
[6,8] 2

Bad intervals:

Interval
[0,1]
[1,2]

Greedy:

Interval Action Chosen
[0,1] choose 1 {1}
[1,2] already covered {1}

Only one modification is required.

Answer:

1

Example 3

Input:

nums = [2,4,9,6]
maxC = 1

Check L = 1.

Windows of length 2:

Window GCD
[2,4] 2
[4,9] 1
[9,6] 3

Bad intervals:

Interval
[0,1]
[2,3]

Greedy:

Interval Action
[0,1] choose 1
[2,3] choose 3

Two modifications are required.

Since maxC = 1, L = 1 is impossible.

Therefore the answer becomes:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n log² n) Binary search over answer, each feasibility check performs O(n) GCD queries
Space O(n) Segment tree storage

The binary search performs O(log n) iterations. During each iteration we scan all windows and execute a segment tree GCD query in O(log n) time. Therefore the total complexity is O(n log² n). The segment tree requires O(n) memory.

Test Cases

sol = Solution()

assert sol.minStable([3, 5, 10], 1) == 1      # example 1
assert sol.minStable([2, 6, 8], 2) == 1       # example 2
assert sol.minStable([2, 4, 9, 6], 1) == 2    # example 3

assert sol.minStable([1], 0) == 0             # single unstable element
assert sol.minStable([2], 0) == 1             # single stable element

assert sol.minStable([1, 1, 1], 0) == 0       # no stable subarray exists

assert sol.minStable([2, 2, 2], 0) == 3       # entire array stable
assert sol.minStable([2, 2, 2], 1) == 1       # one modification breaks all

assert sol.minStable([2, 3, 5, 7], 0) == 1    # only singleton stable subarrays

assert sol.minStable([6, 12, 18, 24], 2) == 1 # heavily stable array

assert sol.minStable([2, 4, 3, 9], 0) == 2    # isolated stable regions

assert sol.minStable([1, 2, 1, 2, 1], 5) == 0 # modify all stable singletons

assert sol.minStable([1000000000], 1) == 0    # modify single element away

Test Summary

Test Why
[3,5,10],1 Official example
[2,6,8],2 Official example
[2,4,9,6],1 Official example
[1],0 No stable subarray
[2],0 Single stable element
[1,1,1],0 Entirely unstable array
[2,2,2],0 Maximum stable segment
[2,2,2],1 One modification destroys long segment
[2,3,5,7],0 Only singleton stable subarrays
[6,12,18,24],2 Large common divisor everywhere
[2,4,3,9],0 Multiple disconnected regions
[1,2,1,2,1],5 Enough modifications to eliminate all stability
[10^9],1 Large value boundary

Edge Cases

Arrays Containing Only Ones

Every subarray has GCD equal to 1, so no stable subarray exists. The correct answer is 0. A common bug is assuming every single element forms a stable subarray. The implementation correctly requires GCD at least 2.

Single Element Arrays

For nums = [x], the answer is 1 when x ≥ 2 and 0 when x = 1. The binary search and feasibility check naturally handle this because windows of length one are considered when L = 0.

Completely Stable Arrays

Consider [2,2,2,2,2]. Every subarray is stable. A naive strategy may underestimate how many intervals one modification can destroy. The greedy interval stabbing procedure correctly exploits overlap and always uses the minimum number of modifications.

Multiple Disconnected Stable Regions

For an array such as [2,4,9,6], the stable regions [2,4] and [9,6] are separated. One modification cannot destroy both regions. The interval stabbing formulation captures this exactly because the intervals do not overlap, forcing multiple modification points.

Large Values Near the Constraint Limit

Values can be as large as 10^9. Since the algorithm only performs GCD computations, it never depends on the magnitude of the numbers beyond logarithmic arithmetic inside the GCD operation. Thus large values are handled safely and efficiently.