Claude vs ChatGPT: A Coder's Perspective on LLM Performance

-
In the rapidly evolving world of Large Language Models (LLMs), recent releases from OpenAI's ChatGPT have garnered significant attention. However, when it comes to coding tasks, Anthropic's Claude.ai continues to impress me with its speed and quality of output.

Benchmarking with LeetCode

While LeetCode problems aren't the definitive measure of an AI's coding capabilities (they're pre-designed puzzles, after all), they offer an interesting playground for comparison. Let's dive into a recent example:

The Problem

3319. K-th Largest Perfect Subtree Size in Binary Tree
Medium

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

 

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2000].
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

My Solution
I tackled this problem using a combination of Post-Order Depth-First Search (PO-DFS) and a Priority Queue. Here are the performance stats:

Runtime: 197 ms
Memory Usage: 103.6 MB

```
Marcelo's Solution:

public class Solution {
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        PriorityQueue pQueue = new PriorityQueue(false, 2500);
        int height = 0;
        int numberNodes = 0;
        IsPerfectSubtreePostOrder(root, ref height, ref numberNodes, pQueue);

        int retVal = -1;
        while (pQueue.Count > 0 && k > 0)
        {
            double priority = 0;
            retVal = (int)pQueue.Dequeue(out priority);
            k--;
        }

        return k > 0 ? -1 : retVal;
    }

    private bool IsPerfectSubtreePostOrder(TreeNode node,
                                           ref int height,
                                           ref int numberNodes,
                                           PriorityQueue pQueue)
    {
        if (node == null)
        {
            height = 0;
            numberNodes = 0;
            return true;
        }

        int rightHeight = 0;
        int rightNumberNodes = 0;
        bool rightSubtree = IsPerfectSubtreePostOrder(node.right, ref rightHeight, ref rightNumberNodes, pQueue);

        int leftHeight = 0;
        int leftNumberNodes = 0;
        bool leftSubtree = IsPerfectSubtreePostOrder(node.left, ref leftHeight, ref leftNumberNodes, pQueue);

        height = Math.Max(rightHeight, leftHeight) + 1;
        numberNodes = rightNumberNodes + leftNumberNodes + 1;

        bool isPerfectSubtree = false;
        if (rightSubtree && leftSubtree && rightHeight == leftHeight)
        {
            pQueue.Enqueue(numberNodes, numberNodes);
            isPerfectSubtree = true;
        }

        return isPerfectSubtree;
    }
}

public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private double priority;
        public HeapEntry(object item, double priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public double Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private bool ascend;
    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue(bool ascend, int cap = -1)
    {
        capacity = 10000000;
        if (cap > 0) capacity = cap;
        heap = new HeapEntry[capacity];
        this.ascend = ascend;
    }

    public object Dequeue(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }
    public object Peak(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public object Peak(/*out double priority*/)
    {
        //priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public void Enqueue(object item, double priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        if (this.ascend)
        {
            while ((index > 0) && (heap[parent].Priority > he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        else
        {
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (this.ascend)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority > heap[child + 1].Priority))
                {
                    child++;
                }
            }
            else
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}
```

ChatGPT's Approach
ChatGPT 4 with Code Interpreter took a slightly different route:
  • Highly optimized PO-DFS
  • Used a List instead of a Priority Queue
  • Performance:
Runtime: 170 ms
Memory Usage: 72.2 MB

```
ChatGPT Solution:
public class Solution
{
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        List<int> perfectSubtreeSizes = new List<int>();
        CalculatePerfectSubtreeSizes(root, perfectSubtreeSizes);

        if (perfectSubtreeSizes.Count < k)
        {
            return -1;
        }

        perfectSubtreeSizes.Sort((a, b) => b.CompareTo(a));
        return perfectSubtreeSizes[k - 1];
    }

    private int CalculatePerfectSubtreeSizes(TreeNode node, List<int> sizes)
    {
        if (node == null)
        {
            return 0;
        }

        int leftSize = CalculatePerfectSubtreeSizes(node.left, sizes);
        int rightSize = CalculatePerfectSubtreeSizes(node.right, sizes);

        if (leftSize == rightSize && (leftSize == 0 || IsPowerOfTwoMinusOne(leftSize + rightSize + 1)))
        {
            int currentSize = leftSize + rightSize + 1;
            sizes.Add(currentSize);
            return currentSize;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

Claude's Solution
Claude.ai consistently outperforms ChatGPT in this and other examples I've tested. Its approach:
  • Pruned version of PO-DFS
  • K-min Priority Queue
  • Performance: 
Runtime: 164 ms
Memory Usage: 71.1 MB

```
Claude.ai Solution:

public class Solution
{
    private PriorityQueue<int, int> topK;
    private int k;

    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        this.k = k;
        this.topK = new PriorityQueue<int, int>(k, Comparer<int>.Create((a, b) => a - b));
        
        DFS(root);

        return topK.Count == k ? topK.Peek() : -1;
    }

    private int DFS(TreeNode node)
    {
        if (node == null)
            return 0;

        int left = DFS(node.left);
        int right = DFS(node.right);

        if (left == right && IsPowerOfTwoMinusOne(left + right + 1))
        {
            int size = left + right + 1;
            if (topK.Count < k)
            {
                topK.Enqueue(size, size);
            }
            else if (size > topK.Peek())
            {
                topK.Dequeue();
                topK.Enqueue(size, size);
            }
            return size;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

The Future of AI and Coding

It's astounding to think that we're only in the first decade of LLMs since the groundbreaking "Attention is All You Need" paper. The rapid progress we've seen raises exciting questions:

  1. How will these models evolve in the coming decades?
  2. What impact will they have on software development practices?
  3. How can we best leverage AI assistants in our coding workflows?

As we continue to explore these questions, one thing is clear: the synergy between human creativity and AI capabilities is reshaping the landscape of software development.

Cheers,
ACC

Comments

Post a Comment

Popular posts from this blog

The power of pruning in backtracking V

-
Image
Backtracking is a great technique in algorithms, but it needs to be accompanied by aggressive pruning or else it may quickly become intractable. This was an interesting problem, and the small input numbers (10^5 and k<=5) tells me that the authors knew that this could quickly become intractable, even with pruning. The pruning here primarily happens in two occasions: first during the base case (k==0), second when the product becomes larger than n. Comparing my solution with Sonnet 4's and ChatGPT 5's (and I gave them all the hints too), there is a small gain in my solution compared to theirs. It was surprising to see that Anthropic's one didn't make use of pruning as well as mine's or ChatGPT 5's. Code is down below, cheers, ACC. Balanced K-Factor Decomposition - LeetCode Given two integers  n  and  k , split the number  n  into exactly  k  positive integers such that the  product  of these integers is equal to  n . Return  any ...
Read more

Quasi FSM (Finite State Machine) problem + Vibe

-
Image
Not really an FSM problem since the state isn't changing, it is just defined by the current input. Simply following the instructions should do it. Using VSCode IDE you can also engage the help of Cline or Copilot for a combo of coding and vibe coding, see below screenshot. Cheers, ACC. Process String with Special Operations I - LeetCode You are given a string  s  consisting of lowercase English letters and the special characters:  * ,  # , and  % . Build a new string  result  by processing  s  according to the following rules from left to right: If the letter is a  lowercase  English letter append it to  result . A  '*'   removes  the last character from  result , if it exists. A  '#'   duplicates  the current  result  and  appends  it to itself. A  '%'   reverses  the current  result . Return the final string  result  after processing all char...
Read more

The power and simplicity of IComparer V

-
Image
Easy problem but it shows the power of IComparer. There are multiple possible solutions here, hence you let the IComparer do the job by just comparing the absolute values in the (internal) QuickSort implementation. Code is down below, cheers, ACC. Sort Array By Absolute Value - LeetCode You are given an integer array  nums . Rearrange elements of  nums  in  non-decreasing  order of their absolute value. Return  any  rearranged array that satisfies this condition. Note : The absolute value of an integer x is defined as: x  if  x >= 0 -x  if  x < 0   Example 1: Input:   nums = [3,-1,-4,1,5] Output:   [-1,1,3,-4,5] Explanation: The absolute values of elements in  nums  are 3, 1, 4, 1, 5 respectively. Rearranging them in increasing order, we get 1, 1, 3, 4, 5. This corresponds to  [-1, 1, 3, -4, 5] . Another possible rearrangement is  [1, -1, 3, -4, 5]. Example 2: Input:   nums = [-100,100] ...
Read more