Sum of GCD of Formed Pairs — LeetCode Daily Python Solution (Two Pointers Eats It Alive)

Introduction

Some LeetCode problems look intimidating because of how they're worded, not because of how hard they actually are. "Sum of GCD of Formed Pairs" is a great example. The name alone — prefix maximums, formed pairs, greatest common divisors — makes it sound like it needs three different algorithms stitched together. It doesn't. Once you see the trick, it collapses into a single pass, one sort, and two pointers walking toward each other from opposite ends of an array.

This matters beyond the problem itself. The "pair the smallest thing with the largest thing" pattern shows up constantly in real interviews at companies like Amazon and Google, and it mirrors real systems too — a job scheduler pairing the heaviest task with the lightest available machine, a load balancer matching requests to capacity, a matchmaking system pairing skill levels. Once you internalize this pattern, a whole family of "meet in the middle" problems becomes recognizable on sight instead of scary.

By the end of this article, you'll understand not just how to solve this specific problem, but why sorting plus two pointers is often the fastest path from "confusing pairing rule" to "boring, predictable loop."

Problem Overview

You're given an array of integers, nums. First, build a new array called the prefix GCD array. For each index i, compute the greatest common divisor of nums[i] and the largest value seen anywhere in nums[0..i] (including nums[i] itself). This gives you a transformed array of the same length.

Next, sort this prefix GCD array. Then repeatedly form pairs by taking the smallest remaining value and the largest remaining value, computing the GCD of each pair, and summing all those GCDs together. If the array has an odd length, the middle element is left unpaired and ignored.

Return the total sum.

The tricky part isn't the GCD — it's realizing that "smallest paired with largest, repeatedly" is exactly what a sorted array with two pointers gives you for free.

Example

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

Step 1 — Build the prefix GCD array:

i	nums[i]	running max so far	gcd(nums[i], running max)
0	3	3	gcd(3, 3) = 3
1	6	6	gcd(6, 6) = 6
2	2	6	gcd(2, 6) = 2
3	8	8	gcd(8, 8) = 8

Prefix GCD array: [3, 6, 2, 8]

Step 2 — Sort it: [2, 3, 6, 8]

Step 3 — Pair smallest with largest:

• Outer pair: gcd(2, 8) = 2
• Inner pair: gcd(3, 6) = 3

Total: 2 + 3 = 5 ✅ matches the expected answer.

Second example: nums = [2, 2]

• Running max stays 2 both times, so the prefix array is [2, 2].
• Sorted: [2, 2].
• One pair: gcd(2, 2) = 2.
• Answer: 2.

This second example is worth sitting with. It shows that duplicate values don't break the logic — the smallest and largest can legitimately be the same number, and the GCD of a number with itself is just that number.

Intuition

The problem gives you two separate ideas bundled together, so the key move is to solve them one at a time instead of trying to hold both in your head at once.

First idea: the prefix GCD step. As you scan left to right, keep a single variable tracking the largest value seen so far. At each index, update that running max first, then take the GCD of the current number with the running max. The order matters — the running max has to include the current element before you compute anything, otherwise you're comparing against a max that's one step behind.

Notice something convenient: whenever a number becomes the new record-holder, you're computing gcd(x, x), which is just x. So the prefix GCD array often looks a lot like the original array, except numbers that come after a bigger number get "pulled down" toward that bigger number's factors.

Second idea: the pairing step. "Pair the smallest remaining with the largest remaining, repeat" is a classic tell. Whenever you see that phrase, sort first. Once sorted, "smallest with largest" is just index 0 with the last index, then index 1 with the second-to-last index, and so on. That's not a coincidence — sorting is exactly what turns an abstract pairing rule into a concrete, predictable index pattern. Two pointers, one starting at the front and one at the back, walk toward each other and meet somewhere in the middle. If the length is odd, they land on the same middle index and simply stop, which naturally skips the unpaired element without any special-casing.

Think of it like a dance instructor lining up a class by height and pairing the shortest student with the tallest, then the second-shortest with the second-tallest, working inward. The sorted order does all the organizational work; you just need two fingers.

Brute Force Solution

Idea: Follow the problem statement literally. Build the prefix GCD array, sort it, then repeatedly pop the first element and the last element from the list, compute their GCD, and add it to the total.

Algorithm:

1. Build the prefix GCD array as described.
2. Sort it.
3. While the list has more than one element, remove the first and last elements, compute their GCD, add to the sum.

Advantages:

• Directly mirrors the problem description — easy to explain out loud in an interview.
• Obviously correct, since it does exactly what's asked.

Disadvantages:

• Popping from the front of a Python list (list.pop(0)) shifts every remaining element over by one position. Do that repeatedly and the simulation quietly becomes quadratic.

Time complexity: O(n²) in the worst case, dominated by repeated front-pops. Space complexity: O(n) for the prefix GCD array and the sorted copy.

Optimal Solution

The optimal approach keeps the same two ideas — prefix GCD, then pair smallest with largest — but implements the pairing step with two pointers instead of list mutation, avoiding the quadratic shifting entirely.

Step-by-step:

1. Build the prefix GCD array. Walk through nums once, maintaining a running max mx. At each index, update mx = max(mx, nums[i]), then compute math.gcd(nums[i], mx) and store it.
2. Sort the prefix GCD array. This arranges values so that "smallest with largest" becomes "first index with last index."
3. Two pointers. Set i = 0 and j = len(array) - 1. While i < j, add gcd(array[i], array[j]) to the total, then move i forward and j backward.
4. Return the total.

The i < j condition (strictly less than, not less-than-or-equal) is doing quiet but important work. When the array length is odd, both pointers eventually land on the same middle index — the loop stops right there, leaving that element unpaired, exactly as the problem requires. There's no need to check for odd length separately.

sorted array: [2, 3, 6, 8]
                i           j
step 1: gcd(2, 8) = 2   →  i=1, j=2
step 2: gcd(3, 6) = 3   →  i=2, j=1  (i < j fails, stop)
total = 5

Python Code

from math import gcd


def sum_of_gcd_of_formed_pairs(nums: list[int]) -> int:
    # Step 1: build prefix GCD array using a running max
    prefix_gcd = []
    mx = 0
    for num in nums:
        mx = max(mx, num)
        prefix_gcd.append(gcd(num, mx))

    # Step 2: sort so smallest-with-largest becomes first-with-last
    prefix_gcd.sort()

    # Step 3: two pointers squeeze inward, summing gcds
    total = 0
    i, j = 0, len(prefix_gcd) - 1
    while i < j:
        total += gcd(prefix_gcd[i], prefix_gcd[j])
        i += 1
        j -= 1

    return total

Code Walkthrough

• from math import gcd: uses Python's built-in GCD implementation instead of writing one by hand — it's faster and already correct.
• mx = 0: starting the running max at 0 is safe because gcd(num, 0) == num for any positive num, so the very first element always produces itself.
• mx = max(mx, num) happens before gcd(num, mx) — this ordering guarantees the running max always includes the current element, which is what "prefix max up to and including index i" means.
• prefix_gcd.sort(): an in-place O(n log n) sort — this single line is what turns the pairing rule into an index pattern.
• i, j = 0, len(prefix_gcd) - 1: pointers start at the two ends of the sorted array.
• while i < j: strict inequality — this is the line that makes odd-length arrays "just work" without extra code.
• i += 1; j -= 1: pointers converge one step at a time until they meet or cross.

Dry Run

Using nums = [3, 6, 2, 8]:

1. Build prefix GCD:
   • num=3: mx=3, gcd(3,3)=3 → [3]
   • num=6: mx=6, gcd(6,6)=6 → [3, 6]
   • num=2: mx=6, gcd(2,6)=2 → [3, 6, 2]
   • num=8: mx=8, gcd(8,8)=8 → [3, 6, 2, 8]
2. Sort: [2, 3, 6, 8]
3. Two pointers:
   • i=0, j=3: gcd(2,8)=2, total=2 → i=1, j=2
   • i=1, j=2: gcd(3,6)=3, total=5 → i=2, j=1 (loop stops)
4. Return 5 — matches the expected result.

Complexity Analysis

• Time: O(n log n) — building the prefix GCD array is a single O(n) pass (each gcd call is effectively O(log(max value)), which doesn't change the overall order). Sorting dominates at O(n log n). The two-pointer sweep is O(n). Total: O(n log n).
• Space: O(n) — for the prefix GCD array (Python's sort() is in-place, so no extra copy is needed beyond that array itself).

This is correct because the only step that isn't linear is the sort, and nothing in the problem lets you avoid ordering the values before pairing smallest with largest.

Alternative Solutions

The brute-force simulation described earlier (pop first and last elements repeatedly) is a reasonable thing to mention first in an interview — it's obviously correct and shows you understand the problem before optimizing. But it costs O(n²) in the worst case because list.pop(0) shifts every remaining element.

Approach	Time	Space	When to use
Pop-both-ends simulation	O(n²)	O(n)	Whiteboard warm-up, small inputs
Two pointers (optimal)	O(n log n)	O(n)	Anything with real input size, this is what you should ship

At the upper constraint (around 10⁵ elements), the quadratic version becomes noticeably slow, while the two-pointer version stays fast because it's bounded by the sort.

Edge Cases

• Single element (nums = [5]): i and j start equal, the while i < j loop never executes, and the function returns 0 — no special casing required.
• All duplicates (nums = [2, 2]): shown above — returns 2, confirming that identical smallest/largest values still pair correctly.
• Odd-length array: the middle element is automatically skipped when i and j meet, exactly matching the problem's intent.
• Large values (up to 10⁹): math.gcd runs in time proportional to the logarithm of the input values (via the Euclidean algorithm), so even large numbers are cheap.
• Already sorted or reverse-sorted input: doesn't matter — the array gets sorted internally regardless of its starting order.

Common Mistakes

1. Using i <= j instead of i < j. This pairs the middle element with itself on odd-length arrays, silently producing a wrong (too high) answer. This is a real mistake that has shipped to production before — treat it as a permanent lesson.
2. Updating the running max after computing the GCD instead of before. This makes the running max lag by one index, breaking the "prefix max including the current element" definition.
3. Popping from the front of a Python list in a loop. Works correctly but silently degrades to O(n²) — fine for small inputs, a real problem at scale.
4. Forgetting to sort before pairing. Without sorting, "smallest with largest" has no clean index-based meaning, and the two-pointer trick doesn't apply.
5. Writing a custom GCD function instead of using math.gcd. Not wrong, but slower and an unnecessary place to introduce bugs when a debugged, optimized version already ships with Python.
6. Assuming the prefix GCD array is always sorted before you sort it. It isn't — the running max can create local dips (as seen with 2 after 6 in the walkthrough), so the explicit sort step is not optional.

Interview Questions

• Why does updating the running max before computing the GCD matter?
• Can you solve the pairing step without sorting? (Answer: not efficiently — sorting is what makes the index relationship exist.)
• What's the time complexity if you used a custom GCD function with a loop instead of math.gcd?
• How would you handle this if nums could contain zero or negative numbers?
• Can you convert the two-pointer loop into a one-liner using zip and slicing?

Similar Problems

• Two Sum II – Input Array Is Sorted (LeetCode 167): same two-pointer-on-sorted-array pattern, different target condition.
• Boats to Save People (LeetCode 881): classic "pair smallest with largest under a constraint" using two pointers.
• Container With Most Water (LeetCode 11): two pointers squeezing inward, but optimizing area instead of summing pairs.
• 3Sum (LeetCode 15): builds on sort-then-two-pointers as an inner loop after fixing one element.

All of these share the same root idea: sort first, then let two pointers do the pairing logic instead of nested loops.

Key Takeaways

• When a problem describes a pairing rule involving "smallest with largest," sort first — it converts an abstract rule into a concrete index pattern.
• A running max computed left-to-right, updated before use, is a common building block worth recognizing on sight.
• i < j versus i <= j is not a stylistic choice — it's the line that decides whether odd-length inputs are handled correctly.
• Reach for math.gcd instead of hand-rolling it; the standard library is faster and already correct.
• Brute-force simulations are worth stating out loud in an interview, but know their hidden costs (like O(n²) list shifting) before defending them as your final answer.

Watch the Video

For the full live walkthrough — including the pause-and-predict moment on [2, 2] and a side-by-side trace of both solutions — watch the video here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where one problem gets solved from scratch every day — plain-English intuition first, clean Python second, no shortcuts on the explanation. The goal isn't just to pass a test case; it's to build the kind of pattern recognition that makes the next fifty similar problems easier.

Call To Action

If this walkthrough helped the trick click, subscribe on YouTube so tomorrow's problem shows up automatically, and subscribe to the Substack for the written breakdown alongside every video. Drop a comment with your own trace of an edge case — trying to break the solution is the fastest way to actually understand it. And if you know someone prepping for interviews, send this one their way.

---

    pre.sort()
    total = 0
    i, j = 0, len(pre) - 1
    while i < j:
        total += gcd(pre[i], pre[j])
        i += 1
        j -= 1
    return total