DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Replace Non-Coprime Numbers in Array - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stack = []
        for num in nums:
            stack.append(num)

            while len(stack) >= 2:
                a, b = stack[-1], stack[-2]
                hcf = math.gcd(a, b)
                if hcf == 1: # co-prime
                    break
                lcm = a * b // hcf
                stack.pop()
                stack.pop()
                stack.append(lcm)
        return stack

Complexity Analysis

Here, n is the input size, and M is the maximum value in the input.

  • Time Complexity: O(n log M)
    • Each of the n numbers enters the stack once, and every merge operation reduces the total count of numbers by one, meaning there are at most n merges.
    • Since each merge requires an O(log M) calculation to find the GCD, so the total time is simply the number of elements multiplied by the cost of merging them.
  • Space Complexity: O(n) – The stack stores at most n elements at any time, since LCMs replace existing elements rather than increasing stack size.