LeetCode 2197 - Replace Non-Coprime Numbers in Array

The problem asks us to repeatedly replace adjacent non-coprime numbers in an array with their Least Common Multiple (LCM) until no more adjacent non-coprime pairs exist. Two numbers are non-coprime if their greatest common divisor (GCD) is greater than 1.

leetcodehardarraymathstacknumber-theory

LeetCode Problem 2197

Difficulty: 🔴 Hard
Topics: Array, Math, Stack, Number Theory

Solution

Problem Understanding

The problem asks us to repeatedly replace adjacent non-coprime numbers in an array with their Least Common Multiple (LCM) until no more adjacent non-coprime pairs exist. Two numbers are non-coprime if their greatest common divisor (GCD) is greater than 1. The final array should be returned after all possible replacements.

In other words, given an array of integers, we must iteratively combine numbers that share any common factor larger than 1. Once two numbers are combined into their LCM, it may create new non-coprime pairs with the adjacent numbers, so the process continues until no further combinations are possible. The array length can go up to 100,000, and each integer can be as large as 100,000, but the final array values are guaranteed to be less than or equal to 108.

Key edge cases include arrays where all numbers are coprime, arrays of length 1, arrays with repeated numbers, or arrays where repeated replacements can occur, requiring a careful iterative approach.

Approaches

A brute-force approach would be to iterate through the array from left to right, compute the GCD for each adjacent pair, and replace non-coprime pairs with their LCM. After each replacement, the iteration would restart from the previous index to check for newly formed non-coprime pairs. While this works for small arrays, it can be extremely inefficient for large arrays because repeatedly recomputing GCDs for the same pairs can result in O(n^2) time complexity.

The optimal solution leverages a stack to maintain a running list of numbers. For each new number, we repeatedly compare it with the top of the stack. If they are non-coprime, we replace the top element with the LCM of the two and continue this check until the new top of the stack is coprime with the current number. If coprime, we push the number onto the stack. This approach avoids restarting iterations and guarantees linear time complexity on average because each element is processed once with occasional repeated LCM calculations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate repeatedly over the array, recomputing GCDs for adjacent elements after each replacement.
Optimal (Stack) O(n log max(num)) O(n) Use a stack to combine adjacent non-coprime numbers efficiently. LCM/GCD calculations dominate logarithmic factor.

Algorithm Walkthrough

  1. Initialize an empty stack to hold numbers that have been processed so far.
  2. Iterate over each number in the input array.
  3. While the stack is not empty and the top of the stack and the current number are non-coprime (GCD > 1), replace the top of the stack with the LCM of the top element and the current number. Update the current number with this LCM because the combined value may form new non-coprime pairs with the previous stack element.
  4. Once the top of the stack is coprime with the current number or the stack is empty, push the current number onto the stack.
  5. After processing all numbers, the stack contains the final array with all adjacent non-coprime numbers combined.

Why it works: The stack ensures that each new number is always compared with its left neighbor, preserving adjacency checks. Repeated LCM replacements propagate through the stack until all non-coprime pairs are resolved. Since the problem guarantees that the final values are less than 108, repeated LCM calculations will not overflow.

Python Solution

from math import gcd
from typing import List

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stack = []
        
        for num in nums:
            while stack:
                top = stack[-1]
                g = gcd(top, num)
                if g == 1:
                    break
                # Replace top with LCM(top, num)
                num = top * num // g
                stack.pop()
            stack.append(num)
        
        return stack

The code initializes an empty stack and iterates over each number. It computes the GCD with the top element of the stack, and if they are non-coprime, it replaces the top element with their LCM. This continues until the top element is coprime with the current number or the stack is empty, ensuring that all non-coprime pairs are resolved efficiently.

Go Solution

package main

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

func replaceNonCoprimes(nums []int) []int {
    stack := []int{}
    
    for _, num := range nums {
        for len(stack) > 0 {
            top := stack[len(stack)-1]
            g := gcd(top, num)
            if g == 1 {
                break
            }
            num = top * num / g
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, num)
    }
    
    return stack
}

In Go, slices are used to implement the stack. The gcd function uses the Euclidean algorithm. Unlike Python, Go requires explicit slice manipulation to pop elements, but the logic remains identical.

Worked Examples

Example 1: nums = [6,4,3,2,7,6,2]

Step Stack Action
Start [] Initial empty stack
6 [6] Push 6
4 [12] 6 and 4 GCD=2, replace with LCM=12
3 [12] 12 and 3 GCD=3, replace with LCM=12
2 [12] 12 and 2 GCD=2, replace with LCM=12
7 [12,7] 12 and 7 GCD=1, push 7
6 [12,7,6] 7 and 6 GCD=1, push 6
2 [12,7,6] 6 and 2 GCD=2, replace with LCM=6

Final stack: [12,7,6]

Example 2: nums = [2,2,1,1,3,3,3]

Step Stack Action
Start [] Initial empty stack
2 [2] Push 2
2 [2] 2 and 2 GCD=2, replace with LCM=2
1 [2,1] 2 and 1 GCD=1, push 1
1 [2,1,1] 1 and 1 GCD=1, push 1
3 [2,1,1,3] 1 and 3 GCD=1, push 3
3 [2,1,1,3] 3 and 3 GCD=3, replace with LCM=3
3 [2,1,1,3] 3 and 3 GCD=3, replace with LCM=3

Final stack: [2,1,1,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n log M) Each element is pushed and popped at most once. GCD computation takes O(log M) where M is the maximum number value (≤105).
Space O(n) Stack stores at most all elements of the array.

The time complexity accounts for the Euclidean GCD algorithm, which is logarithmic in the size of the numbers, making the solution efficient even for large arrays.

Test Cases

# Provided examples
assert Solution().replaceNonCoprimes([6,4,3,2,7,6,2]) == [12,7,6]  # Example 1
assert Solution().replaceNonCoprimes([2,2,1,1,3,3,3]) == [2,1,1,3]  # Example 2

# Edge cases
assert Solution().replaceNonCoprimes([1]) == [1]  # Single element
assert Solution().replaceNonCoprimes([2,3,5,7]) == [2,3,5,7]  # All coprime
assert Solution().replaceNonCoprimes([4,6,8]) == [24]  # All numbers combine
assert Solution().replaceNonCoprimes([2,4,8,16]) == [16]  # Powers of 2
assert Solution().replaceNonCoprimes([3,9,27,81]) == [81]  # Powers of 3
assert Solution().replaceNonCoprimes([5,10,15,20,25]) == [300]  # Mixed multiples
Test Why
[6,4,3,2,7,6,2] Standard case with multiple replacements
[2,2,1,1,3,3,3] Repeated elements and ones
[1] Minimum length input
`[2,3,5,