#2197

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Replace Non-Coprime Numbers in Array

Replace Non-Coprime Numbers in Array uses stack-based state management to iteratively merge adjacent non-coprime integers efficiently.

array math stack number theory

Problem Statement

Given an array of integers nums, repeatedly replace any two adjacent numbers that are not coprime with their least common multiple. Continue this process until no adjacent pair in the array shares a common factor greater than 1. Return the final array after all possible replacements.

It is guaranteed that regardless of the order in which adjacent non-coprime numbers are merged, the resulting array is unique. Each value in the final array is less than or equal to 108, and the input size satisfies 1 <= nums.length <= 105 with 1 <= nums[i] <= 105.

Examples

Example 1

Input: nums = [6,4,3,2,7,6,2]

Output: [12,7,6]

(6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
(12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
(12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
(6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [12,7,6]. Note that there are other ways to obtain the same resultant array.

Example 2

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

Output: [2,1,1,3]

(3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
(3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
(2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [2,1,1,3]. Note that there are other ways to obtain the same resultant array.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105
The test cases are generated such that the values in the final array are less than or equal to 108.

Solution Approach

Use a Stack to Track Merged Numbers

Initialize an empty stack and iterate through nums. For each number, check the top of the stack; if it is non-coprime with the current number, replace the top with their LCM. Repeat until the top of the stack and current number are coprime, then push the current number. This stack-based state management ensures efficient processing of merges.

Greedy Left-Merging Strategy

Since the order of merging does not affect the final result, always attempt to merge the current number with the leftmost possible candidate on the stack. This greedy approach minimizes unnecessary comparisons and avoids repeated scanning of the array, directly exploiting the stack pattern to maintain the correct sequence of merges.

Optimize Coprime Checks and LCM Calculation

Use the greatest common divisor (GCD) function to check if numbers are non-coprime efficiently. Compute the LCM as current * top / GCD(current, top). This approach reduces arithmetic overhead and ensures the solution runs within practical time limits for large input arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of merges, which is at most proportional to the array length, as each merge reduces the effective number of elements. Space complexity is O(n) due to the stack storing processed numbers.

What Interviewers Usually Probe

Check if you are correctly handling consecutive merges in the stack.
Ask how your approach ensures that the final array is unique regardless of merge order.
Consider edge cases where numbers are prime or repeated in sequence.

Common Pitfalls or Variants

Common pitfalls

Not repeatedly merging with the stack top after a replacement can yield incorrect final arrays.
Using inefficient GCD or LCM calculations may cause timeouts on large arrays.
Failing to maintain the stack order can break the left-to-right merge consistency required by the problem.

Follow-up variants

Replace adjacent numbers with LCM if their sum is not prime, instead of coprime condition.
Merge adjacent non-coprime numbers but return the sum of the final array instead of the array itself.
Apply the same merging process on a circular array where the first and last elements are considered adjacent.

FAQ

What is the key insight for Replace Non-Coprime Numbers in Array?

The key insight is that you can greedily merge adjacent non-coprime numbers using a stack, as the merge order does not affect the final result.

Why use a stack instead of iterating multiple times?

A stack lets you efficiently manage previous merges and ensures that each number is processed only once for all left merges.

How do I check if two numbers are non-coprime efficiently?

Use the greatest common divisor (GCD); if GCD > 1, the numbers are non-coprime and should be merged using their LCM.

Does the final array always stay within bounds?

Yes, the problem guarantees that the final values do not exceed 108, so no special overflow handling is needed.

Can the solution handle repeated numbers or primes?

Yes, repeated numbers and primes are handled naturally by the stack merge logic, only merging non-coprime adjacent pairs.

terminal

Solution

Solution 1: Stack

If there exist three adjacent numbers $x$, $y$, $z$ that can be merged, then the result of first merging $x$ and $y$, then merging $z$, is the same as the result of first merging $y$ and $z$, then merging $x$. Both results are $\textit{LCM}(x, y, z)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stk = []
        for x in nums:
            stk.append(x)
            while len(stk) > 1:
                x, y = stk[-2:]
                g = gcd(x, y)
                if g == 1:
                    break
                stk.pop()
                stk[-1] = x * y // g
        return stk

Continue Practicing

#2818 apply operations to maximize score #2183 count array pairs divisible by k #2280 minimum lines to represent a line chart