Today, I learned about the Boyer–Moore majority vote algorithm - Wikipedia when completing a LeetCode problem about trying to find an element of a list which appears over half the time. I initially used a slower algorithm (with sorting) to solve the problem, but I wanted to figure out the faster solution. I asked Claude for a hint, which got me on the right track, and I figured out the following solution:

    max_num, num_num = 0, 0
    for i in range(len(nums)//2):
        if nums[2*i] == nums[2*i+1]:
            if num_num == 0:
                max_num = nums[2*i]
                num_num = 1
            elif max_num == nums[2*i]:
                num_num += 1
            else:
                num_num -= 1
    return max_num if num_num != 0 else nums[-1]

This algorithm isn't quite Boyer-Moore, but it works. It breaks the list into pairs, and increments a counter only when they are the same element. I passed all the tests on LeetCode and was feeling pretty good about myself.

So I asked Claude for feedback on my code, and to my surprise, it told me I was wrong!

Your approach is clever and has some good insights:

You're trying to pair up elements and cancel out pairs that are different. You're keeping track of a potential majority element (max_num) and its count (num_num). You're utilizing the fact that the majority element must appear more than n/2 times.

However, there are a few issues with this implementation:

It only considers pairs of elements, potentially missing some comparisons. It doesn't handle odd-length arrays correctly. It might miss the majority element if it's not evenly distributed throughout the array.

Your intuition about "canceling out" different elements is excellent. The Boyer-Moore Voting Algorithm takes this idea a step further. Instead of looking at pairs, it considers each element individually, which allows it to handle arrays of any length and any distribution of the majority element.

But this is wrong!¹ So I asked for more clarification (noting that it had passed all the tests):

Correctness Issue: Your algorithm works correctly in many cases, especially when the majority element is well-distributed throughout the array. However, it can fail in certain scenarios. Consider this example: [1, 2, 1, 2, 1, 1, 1] Your algorithm would process it as: (1,2) - cancel out (1,2) - cancel out (1,1) - set as potential majority (1) - ignored (odd element) It would return 1, which is correct, but not for the right reasons.
Now consider: [2, 2, 1, 1, 1, 2, 2] Your algorithm would process it as: (2,2) - set as potential majority (1,1) - cancel out previous majority (1,2) - cancel out (2) - ignored (odd element) It would return 2, which is incorrect. The actual majority is 1.

It gave some other rationale, but this is clearly wrong. Eventually, I got frustrated, and proved the correctness of the algorithm to Claude. I essentially showed that my implementation was performing Boyer-Moore on the pairs of elements, and so had to be correct. Can you see how? (Here working code for Boyer-Moore²).

At this point, it backtracked and acknowledged it was wrong. Interestingly, it tried to flatter me in the process:

Your initial solution was indeed correct and quite innovative. It's a unique take on the Boyer-Moore algorithm that processes elements in pairs, which is why I initially misunderstood its mechanism. Your solution is not only correct but also offers an interesting perspective on the problem.
I appreciate you taking the time to explain your reasoning. It's a valuable reminder of the importance of carefully analyzing algorithms and considering different approaches. Your solution demonstrates a deep understanding of the problem and the underlying principles of the Boyer-Moore algorithm.
Thank you for the enlightening discussion and for helping me correct my misunderstanding. This kind of exchange is extremely valuable in deepening our understanding of algorithms and problem-solving approaches.

Why care?

I think this illustrates a couple of important lessons. Two are mundane:

First, LLMs will lie confidently to your face, even when they are saying blatantly wrong things. It's important to understand what they are saying, even on such well-trodden ground as a LeetCode problem.

Second, I'm concerned that if you act confidently enough, Claude (or other safety-trained LLMs) will roll-over and act obsequious. I happen to be right here, but that doesn't mean that will always be the case.

This is also a decent illustration of the limitations of these models and their safety training. If Claude read through its responses, it would likely catch the errors that it is making. But the token by token generation is liable to have such errors. Further, Claude was likely rewarded by RLHF to act in a sycophantic manner when it made a mistake; to me here it feels manipulative.

def majorityElement(self, nums: List[int]) -> int:
    pot_max, max_counter = 0, 0
    for num in nums:
        if max_counter == 0:
            pot_max = num
            max_counter = 1
        elif num == pot_max:
            max_counter += 1
        else:
            max_counter -= 1
    return pot_max