2197. Replace Non-Coprime Numbers in Array

Time: O(n log max)

Space: O(n)

Approach

Stack-based merge — while top of stack and current share a common factor (LCM them).

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Math

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Stack

Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.

2197.cs

// Approach: Stack-based merge — while top of stack and current share a common factor (LCM them).
// Time: O(n log max) Space: O(n)

public class Solution
{
    public IList<int> ReplaceNonCoprimes(int[] nums)
    {
        // Use a list as a stack to store the result
        List<int> stack = new List<int>();

        // Process each number in the input array
        foreach (int currentNum in nums)
        {
            // Add current number to the stack
            stack.Add(currentNum);

            // Keep merging adjacent non-coprime numbers
            while (stack.Count > 1)
            {
                // Get the last two elements from the stack
                int lastElement = stack[stack.Count - 1];
                int secondLastElement = stack[stack.Count - 2];

                // Calculate GCD of the two elements
                int gcdValue = Gcd(lastElement, secondLastElement);

                // If they are coprime (GCD = 1), no merge needed
                if (gcdValue == 1)
                    break;

                // Remove the last element
                stack.RemoveAt(stack.Count - 1);

                // Replace the second last element with LCM of both elements
                // LCM(a, b) = (a * b) / GCD(a, b)
                // Using long to prevent integer overflow during multiplication
                long lcmValue = (long)lastElement * secondLastElement / gcdValue;
                stack[stack.Count - 1] = (int)lcmValue;
            }
        }

        return stack;
    }

    /**
     * Calculates the Greatest Common Divisor using Euclidean algorithm
     * @param a First positive integer
     * @param b Second positive integer
     * @return GCD of a and b
     */
    private int Gcd(int a, int b)
    {
        // Base case: when b becomes 0, a is the GCD
        if (b == 0)
            return a;

        // Recursive case: GCD(a, b) = GCD(b, a mod b)
        return Gcd(b, a % b);
    }
}

Was this solution helpful?