Two Pointers for a Linear Solution VI (and the power of LLM to debug code)

This is problem 11 on LeetCode, and the solution is a 2-pointer one, always moving the pointer pointing to the lower wall. The reason can be explained mathematically. Suppose that the current area is:

Min(L,R) * N

You want to maximize the first term (Min(L,R)) since the second one (N) will always decrease as you move the pointers. Therefore, move the one pointing to minimum height in order to guarantee that the next Min(L,R) will be greater than the previous one.

The code is down below, but more interesting is to play with Copilot to debug the code. Purposedly, I introduced a bug where I forgot the brackets in the calculation of N. With the proper prompt engineering, you can ask the Copilot to pinpoint the issue and the fix. Both OpenAI ChatGPT and Bing Chat solved the problem flawlessly, see below. And the correct code is below too. Cheers, ACC.

Container With Most Water - LeetCode

11. Container With Most Water

Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

public int MaxArea(int[] height)
{
    int left = 0;
    int right = height.Length - 1;

    int area = 0;

    while (left < right)
    {
        area = Math.Max(area, Math.Min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) left++;
        else if (height[left] > height[right]) right--;
        else { left++; right--; };
    }

    return area;
}

PROMPT ENGINEERING:

"I'm trying to solve this problem https://leetcode.com/problems/container-with-most-water/ using C# and the two-pointers approach. My code unfortunately is giving the wrong answer. My code is down below. For the input [1,8,6,2,5,4,8,3,7], the right answer should be 49, but my code is giving as the response 55. Can you evaluate my code and pinpoint the issue in the code, and suggest a fix for it please? public int MaxArea(int[] height) { int left = 0; int right = height.Length - 1; int area = 0; while (left < right) { area = Math.Max(area, Math.Min(height[left], height[right]) * right - left); if (height[left] < height[right]) left++; else if (height[left] > height[right]) right--; else { left++; right--; }; } return area; }"

BING CHAT:

I see what’s causing the issue in your C# code. The problem lies in the calculation of the area within the while loop. You’re missing parentheses around the multiplication operation which is causing an incorrect order of operations. The subtraction should happen after the multiplication, not before.

Here’s the corrected line with the proper order of operations:

area = Math.Max(area, Math.Min(height[left], height[right]) * (right - left));

With this fix, your code should now correctly calculate the maximum area for the given input. Here’s the revised version of your MaxArea method:

public int MaxArea(int[] height)
{
    int left = 0;
    int right = height.Length - 1;

    int area = 0;

    while (left < right)
    {
        area = Math.Max(area, Math.Min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) left++;
        else if (height[left] > height[right]) right--;
        else { left++; right--; };
    }

    return area;
}

Now, when you run this corrected code with the input [1,8,6,2,5,4,8,3,7], it should give you the correct answer of 49. Happy coding! 😊