Container With Most Water - C Solution

1. Introduction

This post discusses an interesting problem commonly known as "Container With Most Water". It involves finding two lines that, together with the x-axis, form a container that can hold the maximum amount of water. This problem is a great example of how to apply the two-pointer technique in array processing to solve optimization problems efficiently.

Problem

Given an integer array height of length n, where n vertical lines are drawn such that the endpoints of the ith line are at coordinates (i, 0) and (i, height[i]), the task is to find two lines that form a container with the x-axis, such that the container holds the maximum amount of water.

2. Solution Steps

1. Initialize two pointers, one at the start and one at the end of the array.

2. Calculate the area formed by the lines at these two pointers.

3. Move the pointer pointing to the shorter line towards the other pointer.

4. Update the maximum area if a larger area is found.

5. Repeat steps 2-4 until the pointers meet.

6. Return the maximum area found.

3. Code Program

#include <stdio.h>

// Function to calculate the maximum water that can be contained
int maxArea(int* height, int heightSize) {
    int maxWater = 0, left = 0, right = heightSize - 1;

    while (left < right) {
        int width = right - left;
        int minHeight = height[left] < height[right] ? height[left] : height[right];
        int water = width * minHeight;

        if (water > maxWater) {
            maxWater = water; // Update max water
        }

        // Move the pointer of the shorter line
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

// Main function to test the maxArea function
int main() {
    int heights1[] = {1,8,6,2,5,4,8,3,7};
    printf("Maximum Water (Example): %d\n", maxArea(heights1, 9));

    return 0;
}

Output:

Maximum Water (Example): 49

Explanation:

1. Initialize left and right pointers.

2. Calculate the area (width * height) formed between the lines at left and right.

3. Update maxWater if a larger area is found.

4. Move the pointer of the shorter line towards the other to explore potentially larger areas.

5. Repeat until left and right meet.

6. The main function tests the maxArea function with an example and prints the maximum amount of water that can be contained.