LeetCode #3605 — HARD

Minimum Stability Factor of Array

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

You are given an integer array nums and an integer maxC.

A subarray is called stable if the highest common factor (HCF) of all its elements is greater than or equal to 2.

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

You may modify at most maxC elements of the array to any integer.

Return the minimum possible stability factor of the array after at most maxC modifications. If no stable subarray remains, return 0.

Note:

The highest common factor (HCF) of an array is the largest integer that evenly divides all the array elements.
A subarray of length 1 is stable if its only element is greater than or equal to 2, since HCF([x]) = x.

Example 1:

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

Output: 1

Explanation:

The stable subarray [5, 10] has HCF = 5, which has a stability factor of 2.
Since maxC = 1, one optimal strategy is to change nums[1] to 7, resulting in nums = [3, 7, 10].
Now, no subarray of length greater than 1 has HCF >= 2. Thus, the minimum possible stability factor is 1.

Example 2:

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

Output: 1

Explanation:

The subarray [2, 6, 8] has HCF = 2, which has a stability factor of 3.
Since maxC = 2, one optimal strategy is to change nums[1] to 3 and nums[2] to 5, resulting in nums = [2, 3, 5].
Now, no subarray of length greater than 1 has HCF >= 2. Thus, the minimum possible stability factor is 1.

Example 3:

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

Output: 2

Explanation:

The stable subarrays are:
- [2, 4] with HCF = 2 and stability factor of 2.
- [9, 6] with HCF = 3 and stability factor of 2.
Since maxC = 1, the stability factor of 2 cannot be reduced due to two separate stable subarrays. Thus, the minimum possible stability factor is 2.

Constraints:

1 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= maxC <= n

Step 01

Brute Force Baseline

Problem summary: You are given an integer array nums and an integer maxC. A subarray is called stable if the highest common factor (HCF) of all its elements is greater than or equal to 2. The stability factor of an array is defined as the length of its longest stable subarray. You may modify at most maxC elements of the array to any integer. Return the minimum possible stability factor of the array after at most maxC modifications. If no stable subarray remains, return 0. Note: The highest common factor (HCF) of an array is the largest integer that evenly divides all the array elements. A subarray of length 1 is stable if its only element is greater than or equal to 2, since HCF([x]) = x.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Math · Binary Search · Greedy · Segment Tree

Example 1

[3,5,10]
1

Example 2

[2,6,8]
2

Example 3

[2,4,9,6]
1

Step 02

Core Insight

What unlocks the optimal approach

Binary‐search the target length <code>k</code>
For each <code>k</code>, use fast range‐GCD queries
Greedily "hit" every window of size <code>k+1</code> with an edit if its <code>GCD > 1</code>

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// package main
// 
// import (
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// func minStable1(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	type interval struct{ gcd, l int } // 子数组 GCD，最小左端点
// 	intervals := []interval{{1, 0}}    // 哨兵
// 	for i, x := range nums {
// 		// 计算以 i 为右端点的子数组 GCD
// 		for j, p := range intervals {
// 			intervals[j].gcd = gcd(p.gcd, x)
// 		}
// 		// nums[i] 单独一个数作为子数组
// 		intervals = append(intervals, interval{x, i})
// 
// 		// 去重（合并 GCD 相同的区间）
// 		idx := 1
// 		for j := 1; j < len(intervals); j++ {
// 			if intervals[j].gcd != intervals[j-1].gcd {
// 				intervals[idx] = intervals[j]
// 				idx++
// 			}
// 		}
// 		intervals = intervals[:idx]
// 
// 		// 由于我们添加了哨兵，intervals[1] 的 GCD >= 2 且最长，取其区间左端点作为子数组的最小左端点
// 		if len(intervals) > 1 {
// 			leftMin[i] = intervals[1].l
// 		} else {
// 			leftMin[i] = n
// 		}
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func minStable(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	var left, bottom, rightGcd int
// 	for i, x := range nums {
// 		rightGcd = gcd(rightGcd, x)
// 		for left <= i && gcd(nums[left], rightGcd) == 1 {
// 			if bottom <= left {
// 				// 重新构建一个栈
// 				// 由于 left 即将移出窗口，只需计算到 left+1
// 				for j := i - 1; j > left; j-- {
// 					nums[j] = gcd(nums[j], nums[j+1])
// 				}
// 				bottom = i
// 				rightGcd = 0
// 			}
// 			left++
// 		}
// 		leftMin[i] = left
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }

// Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
package main

import (
	"sort"
)

// https://space.bilibili.com/206214
func minStable1(nums []int, maxC int) int {
	n := len(nums)
	leftMin := make([]int, n)
	type interval struct{ gcd, l int } // 子数组 GCD，最小左端点
	intervals := []interval{{1, 0}}    // 哨兵
	for i, x := range nums {
		// 计算以 i 为右端点的子数组 GCD
		for j, p := range intervals {
			intervals[j].gcd = gcd(p.gcd, x)
		}
		// nums[i] 单独一个数作为子数组
		intervals = append(intervals, interval{x, i})

		// 去重（合并 GCD 相同的区间）
		idx := 1
		for j := 1; j < len(intervals); j++ {
			if intervals[j].gcd != intervals[j-1].gcd {
				intervals[idx] = intervals[j]
				idx++
			}
		}
		intervals = intervals[:idx]

		// 由于我们添加了哨兵，intervals[1] 的 GCD >= 2 且最长，取其区间左端点作为子数组的最小左端点
		if len(intervals) > 1 {
			leftMin[i] = intervals[1].l
		} else {
			leftMin[i] = n
		}
	}

	ans := sort.Search(n/(maxC+1), func(upper int) bool {
		c := maxC
		i := upper
		for i < n {
			if i-leftMin[i]+1 > upper {
				if c == 0 {
					return false
				}
				c--
				i += upper + 1
			} else {
				i++
			}
		}
		return true
	})
	return ans
}

func minStable(nums []int, maxC int) int {
	n := len(nums)
	leftMin := make([]int, n)
	var left, bottom, rightGcd int
	for i, x := range nums {
		rightGcd = gcd(rightGcd, x)
		for left <= i && gcd(nums[left], rightGcd) == 1 {
			if bottom <= left {
				// 重新构建一个栈
				// 由于 left 即将移出窗口，只需计算到 left+1
				for j := i - 1; j > left; j-- {
					nums[j] = gcd(nums[j], nums[j+1])
				}
				bottom = i
				rightGcd = 0
			}
			left++
		}
		leftMin[i] = left
	}

	ans := sort.Search(n/(maxC+1), func(upper int) bool {
		c := maxC
		i := upper
		for i < n {
			if i-leftMin[i]+1 > upper {
				if c == 0 {
					return false
				}
				c--
				i += upper + 1
			} else {
				i++
			}
		}
		return true
	})
	return ans
}

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

# Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
#
# @lc app=leetcode id=3605 lang=python3
#
# [3605] Minimum Stability Factor of Array
#

# @lc code=start
import math

class Solution:
    def minStable(self, nums: List[int], maxC: int) -> int:
        n = len(nums)
        # Local reference for speed
        gcd = math.gcd
        
        def check(K):
            # We want to ensure no stable subarray of length > K exists.
            # This is equivalent to breaking all stable subarrays of length L = K + 1.
            L = K + 1
            if L > n:
                return True
            
            # Two-stack queue to maintain sliding window GCD
            # stack_in stores (value, accumulated_gcd_from_bottom)
            stack_in = []
            # stack_out stores (value, accumulated_gcd_from_bottom)
            stack_out = []
            
            cost = 0
            current_len = 0
            
            for x in nums:
                # Push x into stack_in
                if not stack_in:
                    stack_in.append((x, x))
                else:
                    stack_in.append((x, gcd(x, stack_in[-1][1])))
                current_len += 1
                
                if current_len == L:
                    # Query the GCD of the current window
                    g = 0
                    if stack_in:
                        g = stack_in[-1][1]
                    if stack_out:
                        if g == 0:
                            g = stack_out[-1][1]
                        else:
                            g = gcd(g, stack_out[-1][1])
                    
                    if g >= 2:
                        # Found a stable subarray of length L
                        cost += 1
                        if cost > maxC:
                            return False
                        # Greedy strategy: modify the last element (current x) to break this window.
                        # This modification effectively invalidates the current window and allows us
                        # to skip overlapping windows starting within this range. 
                        # We reset the queue to simulate this skip.
                        stack_in.clear()
                        stack_out.clear()
                        current_len = 0
                    else:
                        # Window is not stable, slide forward by popping the oldest element
                        if not stack_out:
                            # Move elements from stack_in to stack_out
                            if stack_in:
                                val, _ = stack_in.pop()
                                stack_out.append((val, val))
                                while stack_in:
                                    val, _ = stack_in.pop()
                                    stack_out.append((val, gcd(val, stack_out[-1][1])))
                        if stack_out:
                            stack_out.pop()
                        current_len -= 1
            
            return True

        low, high = 0, n
        ans = n
        
        while low <= high:
            mid = (low + high) // 2
            if check(mid):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        
        return ans
# @lc code=end

// Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// package main
// 
// import (
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// func minStable1(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	type interval struct{ gcd, l int } // 子数组 GCD，最小左端点
// 	intervals := []interval{{1, 0}}    // 哨兵
// 	for i, x := range nums {
// 		// 计算以 i 为右端点的子数组 GCD
// 		for j, p := range intervals {
// 			intervals[j].gcd = gcd(p.gcd, x)
// 		}
// 		// nums[i] 单独一个数作为子数组
// 		intervals = append(intervals, interval{x, i})
// 
// 		// 去重（合并 GCD 相同的区间）
// 		idx := 1
// 		for j := 1; j < len(intervals); j++ {
// 			if intervals[j].gcd != intervals[j-1].gcd {
// 				intervals[idx] = intervals[j]
// 				idx++
// 			}
// 		}
// 		intervals = intervals[:idx]
// 
// 		// 由于我们添加了哨兵，intervals[1] 的 GCD >= 2 且最长，取其区间左端点作为子数组的最小左端点
// 		if len(intervals) > 1 {
// 			leftMin[i] = intervals[1].l
// 		} else {
// 			leftMin[i] = n
// 		}
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func minStable(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	var left, bottom, rightGcd int
// 	for i, x := range nums {
// 		rightGcd = gcd(rightGcd, x)
// 		for left <= i && gcd(nums[left], rightGcd) == 1 {
// 			if bottom <= left {
// 				// 重新构建一个栈
// 				// 由于 left 即将移出窗口，只需计算到 left+1
// 				for j := i - 1; j > left; j-- {
// 					nums[j] = gcd(nums[j], nums[j+1])
// 				}
// 				bottom = i
// 				rightGcd = 0
// 			}
// 			left++
// 		}
// 		leftMin[i] = left
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }

// Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3605: Minimum Stability Factor of Array
// package main
// 
// import (
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// func minStable1(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	type interval struct{ gcd, l int } // 子数组 GCD，最小左端点
// 	intervals := []interval{{1, 0}}    // 哨兵
// 	for i, x := range nums {
// 		// 计算以 i 为右端点的子数组 GCD
// 		for j, p := range intervals {
// 			intervals[j].gcd = gcd(p.gcd, x)
// 		}
// 		// nums[i] 单独一个数作为子数组
// 		intervals = append(intervals, interval{x, i})
// 
// 		// 去重（合并 GCD 相同的区间）
// 		idx := 1
// 		for j := 1; j < len(intervals); j++ {
// 			if intervals[j].gcd != intervals[j-1].gcd {
// 				intervals[idx] = intervals[j]
// 				idx++
// 			}
// 		}
// 		intervals = intervals[:idx]
// 
// 		// 由于我们添加了哨兵，intervals[1] 的 GCD >= 2 且最长，取其区间左端点作为子数组的最小左端点
// 		if len(intervals) > 1 {
// 			leftMin[i] = intervals[1].l
// 		} else {
// 			leftMin[i] = n
// 		}
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func minStable(nums []int, maxC int) int {
// 	n := len(nums)
// 	leftMin := make([]int, n)
// 	var left, bottom, rightGcd int
// 	for i, x := range nums {
// 		rightGcd = gcd(rightGcd, x)
// 		for left <= i && gcd(nums[left], rightGcd) == 1 {
// 			if bottom <= left {
// 				// 重新构建一个栈
// 				// 由于 left 即将移出窗口，只需计算到 left+1
// 				for j := i - 1; j > left; j-- {
// 					nums[j] = gcd(nums[j], nums[j+1])
// 				}
// 				bottom = i
// 				rightGcd = 0
// 			}
// 			left++
// 		}
// 		leftMin[i] = left
// 	}
// 
// 	ans := sort.Search(n/(maxC+1), func(upper int) bool {
// 		c := maxC
// 		i := upper
// 		for i < n {
// 			if i-leftMin[i]+1 > upper {
// 				if c == 0 {
// 					return false
// 				}
// 				c--
// 				i += upper + 1
// 			} else {
// 				i++
// 			}
// 		}
// 		return true
// 	})
// 	return ans
// }
// 
// func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.