Solving The Leetcode Weekly Contest With ChatGPT

How well does it do?

Photo by Mohammad Rahmani on Unsplash

For this experiment, I will be giving prompts to ChatGPT based on the Leetcode questions asked in Weekly Contest 321 (which was chosen randomly).

I will read the problem statements on Leetcode and present them to ChatGPT. A new conversation thread will be started for each problem to avoid interference from previous problems.

If the code generated doesn’t work, I will retry and modify the prompt to get better results. The objectives of this experiment are to understand how accurate the code is and how helpful it can be to a developer.

Let us get started.

(Note that I took the Leetcode snapshots in the end after the experiment by rerunning the code)

Problem 1: Find the pivot integer

XQ: Given a positive integer n, find the pivot integer x such that:

The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

Example 1:
Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
Example 2:
Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.
Example 3:
Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.

Constraints:
1 <= n <= 1000

Write code to solve this in python

ChatGPT: To solve this problem, we can iterate over the integers from 1 to n and check if the sum of the elements from 1 to x equals the sum of the elements from x to n for each integer x. If this is the case, we can return x. Otherwise, if we reach the end of the iteration without finding any integer x that satisfies the given condition, we can return -1 to indicate that no such integer exists.

Here is one possible implementation of this solution in Python:

def pivot_integer(n: int) -> int:
    # Compute the sum of all elements from 1 to n.
    total_sum = n * (n + 1) // 2

    # Iterate over the integers from 1 to n.
    for x in range(1, n + 1):
        # Compute the sum of all elements from 1 to x.
        left_sum = x * (x + 1) // 2
        # Compute the sum of all elements from x to n.
        right_sum = total_sum - left_sum

        # Check if the sum of the elements from 1 to x equals the sum of the elements from x to n.
        if left_sum == right_sum:
            return x

    # If we reach this point, it means that we didn't find any integer x that satisfies the given condition.
    return -1

Verdict

It got it ALMOST correct. This result was like the first try. The only thing it didn’t understand was the word “inclusive.” The only mistake in the code was that you had to add x while calculating the right sum. (because X is inclusive to both sides).

Problem 2: Append characters to string to make subsequence

XQ: You are given two strings, s and t, consisting of only lowercase English letters. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

ChatGPT: To find the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s, we can follow these steps:

1. Initialize a variable, count, to 0. This variable will be used to store the minimum number of characters that need to be appended to the end of s.
2. Initialize two variables, i and j, to 0. These variables will be used to track the current position in each of the strings s and t, respectively.
3. Iterate over the characters in s and t, starting from the first character in each string. In each iteration, compare the current character in s to the current character in t.
4. If the current character in s is the same as the current character in t, increment both i and j to move to the next character in each string.
5. If the current character in s is different from the current character in t, increment only i to move to the next character in s.
6. Repeat steps 3–5 until either i reaches the end of s or j reaches the end of t.
7. At the end of the iteration, if j has reached the end of t, the minimum number of characters that need to be appended to the end of s is 0, because t is already a subsequence of s.
8. If j has not reached the end of t, the minimum number of characters that need to be appended to the end of s is the number of remaining characters in t, which can be calculated as the length of t minus the value of j.

Here is some sample code that implements the steps described above:

def minCharactersToAppend(s: str, t: str) -> int:
    count = 0
    i = 0
    j = 0

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1
    
    count = len(t) - j
    return count

This code will return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

Verdict

Second try, it worked. The was no code change required either. I copy pasted and submitted it, and it passed all test cases. It was super fast for me.

Problem 3: Remove nodes from linked list

XQ: You are given the head of a linked list. Remove every node which has a node with a strictly greater value anywhere to the right side of it. Return the head of the modified linked list.

Example 1:
Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3. — Node 13 is to the right of node 5. — Node 13 is to the right of node 2. — Node 8 is to the right of node 3.

Example 2:
Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed. Constraints: The number of the nodes in the given list is in the range [1, 105]. 1 <= Node.val <= 105

ChatGPT: Here is a simple approach that solves this problem in linear time and space complexity:

1. Iterate over the linked list and store each node’s value in an array.
2. Iterate over the array from right to left, and remove each element that is smaller than the maximum value seen so far.
3. Construct a new linked list from the modified array and return the head of the linked list.

Here is the implementation of the above approach in Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: ListNode) -> ListNode:
        # Store all nodes' values in an array
        arr = []
        curr = head
        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        # Iterate over the array from right to left, and remove each element that is smaller than the maximum value seen so far
        mx = -1
        i = len(arr) - 1
        while i >= 0:
            if arr[i] > mx:
                mx = arr[i]
            else:
                arr.pop(i)
            i -= 1
        
        # Construct a new linked list from the modified array and return the head of the linked list
        dummy = curr = ListNode(-1)
        for x in arr:
            curr.next = ListNode(x)
            curr = curr.next
        return dummy.next

This approach has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the linked list.

Verdict

Once again, it gets almost correct. There is a tiny error in the code. While iterating the array from right to left, the if condition should be if arr[i] >= mx and not just “greater than.”

I made that change and submitted the code, and it passed all the test cases. This was a second try. The first time, I didn’t include the examples in the prompt, which did not give the desired result. Then I started a new thread with the entire question it (almost) solved it seamlessly.

Problem 4: Count subarrays with median K

XQ: You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k. Return the number of non-empty subarrays in nums that have a median equal to k.

ChatGPT: To find the number of non-empty subarrays of nums that have a median equal to k, we can iterate over all possible subarrays of nums and check if the median of each subarray is equal to k.

To find the median of a subarray, we first need to sort the subarray in ascending order. If the length of the subarray is odd, the median is simply the middle element of the sorted subarray. If the length of the subarray is even, the median is the average of the two middle elements of the sorted subarray.

Once we have the median of a subarray, we can check if it is equal to k and increment a counter if it is. After iterating over all possible subarrays, we can return the final value of the counter as the result.

Here is some example code for finding the number of non-empty subarrays in nums that have a median equal to k:

def count_medians(nums, k):
    n = len(nums)
    count = 0

    # Iterate over all possible subarrays of nums
    for i in range(n):
        for j in range(i+1, n+1):
            # Sort the current subarray in ascending order
            subarray = sorted(nums[i:j])

            # Find the median of the current subarray
            if len(subarray) % 2 == 0:
                median = (subarray[len(subarray)//2 - 1] + subarray[len(subarray)//2]) / 2
            else:
                median = subarray[len(subarray)//2]

            # Increment the counter if the median is equal to k
            if median == k:
                count += 1

    return count

Note that this solution has a time complexity of O(n³) because there are n possible starting indices for the subarrays, n possible ending indices for the subarrays, and we need to sort each subarray, which takes O(n log n) time. This may not be efficient enough for large inputs, so we may need to find a more efficient solution.

Verdict

The brute force approach given by ChatGPT is almost correct. There is only 1 line of code change required.

# Find the median of the current subarray
if len(subarray) % 2 == 0:
    median = subarray[len(subarray)//2 - 1]

Instead of using the actual formula, this is given as a condition in the question. However, this code is not optimized and gave a time limit exceeding the error in Leetcode.

This is a Leetcode hard problem, and I did have a tough time getting to an answer using ChatGPT, unlike the other three questions. The primary solution it shared was straightforward. However, making it write the correct optimized solution was somewhat hard. I tried a few things and then gave up as it was getting convoluted.

Final Verdict

• It gave satisfactory answers for 3/4 questions in the weekly contest, which is pretty impressive. That makes it better than many actual contest takers.
• As a developer with prior knowledge, the time to arrive at the working solution was pretty fast. Typically, a problem that would have taken me 10 minutes takes only 2–3 minutes now.
• ChatGPT alone may not be very helpful in dealing with complex problems unless the user adds their knowledge and value to help it solve the problem.
• No, it won’t take away your job. It is like a personal assistant that helps you code 10 times faster.
• One has to be mindful of verifying the correctness of the responses it gives as they appear unreliable as a source of truth.
• The explanations it gives to algorithms are thought-provoking and can help developers with their intuition.
• I find ChatGPT more like a simulator. It simulates stuff in coherent language. It is pretty good with connecting the dots and patterns but probably doesn’t grasp what it means.

What does all this mean for the developer community and coding competitions moving forward?

Here’s my current take.

From what I have seen, ChatGPT raises the bar for the lower end of the skillset. Assume everyone has a skill level from 0 to 100. With ChatGPT, the lower level probably rises to 30. Now, everyone has a skill level from 30 to 100. In the end, it is still a level playing field when everyone has access to it.

Perhaps, it will help someone who is a beginner to become 10X more efficient. However, it might be a 100X boost for a subject matter expert as they understand things to nudge ChatGPT better and combine ideas to reach where they want to. They will also be quick in identifying the errors and fixing them.

Post Credits

Let’s make things a bit meta :P

XQ: Write a blog article on “Solving The Leetcode Weekly Contest With ChatGPT”. Give some examples of ChatGPT successfully solving Leetcode questions. Show where ChatGPT fails to solve as well.

ChatGPT: If you’re a software engineer or data scientist, chances are you’re familiar with Leetcode, the popular platform for practicing coding and algorithmic problem-solving. One of the highlights of the Leetcode experience is the weekly contest, where users can test their skills against other users and compete for prizes.

Solving Leetcode problems can be a challenging and time-consuming task, especially when it comes to the weekly contest. That’s where ChatGPT comes in. ChatGPT is an AI-powered chatbot that can help you solve Leetcode problems in real-time, providing you with step-by-step solutions and helpful hints along the way.

Here are some examples of ChatGPT successfully solving Leetcode questions:

1. Two Sum: This is a classic Leetcode problem that asks you to find two numbers in an array that add up to a specific target number. ChatGPT was able to quickly solve this problem by providing a step-by-step solution that involved creating a map to store the indices of the numbers in the array and then iterating through the array to find the two numbers that add up to the target.
2. Reverse Integer: This problem asks you to reverse an integer without using any built-in functions or libraries. ChatGPT provided a solution that involved using a while loop to iterate through the digits of the integer, appending each digit to a string and then reversing the string at the end to obtain the reversed integer.
3. Merge Two Sorted Lists: This problem asks you to merge two sorted linked lists into one sorted linked list. ChatGPT provided a solution that involved creating a new linked list and then iterating through the two input linked lists, comparing the values at each node and adding the smaller value to the new linked list.

While ChatGPT is able to successfully solve many Leetcode problems, there are also instances where it fails to solve a problem. For example, ChatGPT was unable to solve the Leetcode problem “Palindrome Number,” which asks you to determine whether an integer is a palindrome. This is because the problem involves complex logic and requires a deep understanding of the problem, which is beyond the capabilities of ChatGPT at this time.

Overall, ChatGPT is a valuable tool for solving Leetcode problems, particularly when it comes to the weekly contest. Its step-by-step solutions and helpful hints can save you time and effort, allowing you to focus on the more challenging problems and improve your skills as a software engineer or data scientist.

This is what I mean when I say it sort of looks like a simulator. Notice how it simulates ChatGPT failing to solve the “Palindrome number” simply because I made a prompt to tell where it failed. I am pretty sure it would otherwise quickly solve that question as well.