Algorithms – Part 2: Container with Most Water

About:

Again, this is something done earlier this year in the post: Road to Google – Part 2: Container with Most Water.

This problem has practical applications in various fields, such as engineering and optimization. For example, it can be used in designing containers, dams, or structures where the goal is to maximize the capacity while using the least amount of resources.

By applying this approach, you can efficiently find the maximum area that a container formed by two lines can hold, which demonstrates a basic strategy for optimization and solving similar types of challenges.

I’ve already provided comprehensive and detailed descriptions in the post, so please go through that. Similarly, in this instance, I’ve utilized this method to incorporate the use of a MySQL database.

Question:

You are given an array of positive integers where each integer represents the height of a vertical line on a chart.

Find two lines that together with the x-axis form a container that would hold the most significant amount of water.

Return the area of water it would hold.

Table:

CREATE TABLE heights_table (
    id INT PRIMARY KEY AUTO_INCREMENT,
    height INT
);

INSERT INTO heights_table (height) VALUES
    (7),
    (1),
    (2),
    (3),
    (9);

Code:

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class ContainerWithMostWaterDB {

    public static int maxArea(int[] a) {
        int area = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                area = Math.max(area, Math.min(a[i], a[j]) * (j - i));
            }
        }
        return area;
    }

    public static void main(String[] args) {
        String jdbcUrl = "jdbc:mysql://192.168.0.xx:3306/your_db_name";
        String username = "user_name";
        String password = "password";

        try {
            Connection connection = DriverManager.getConnection(jdbcUrl, username, password);

            Statement statement = connection.createStatement();
            String sqlQuery = "SELECT height FROM heights_table";
            ResultSet resultSet = statement.executeQuery(sqlQuery);

            // Count the number of rows in the result set
            resultSet.last();
            int rowCount = resultSet.getRow();
            resultSet.beforeFirst();

            int[] heights = new int[rowCount];
            int index = 0;

            while (resultSet.next()) {
                int height = resultSet.getInt("height");
                heights[index++] = height;
            }

            resultSet.close();
            statement.close();
            connection.close();

            int maxWaterArea = maxArea(heights);
            System.out.println("Maximum water area: " + maxWaterArea);

        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}

How does the logic work?

In the given code, the max water area is tracked using the variable named area. The variable area is initialized to 0 before the loop starts, and as the loop iterates through all the possible pairs of heights, it updates the area value whenever a larger water area is encountered. Here’s how it works:

public static int maxArea(int[] a) {
    int area = 0;  // Initialize area to 0

    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            area = Math.max(area, Math.min(a[i], a[j]) * (j - i));  // Update area if a larger area is found
        }
    }
    return area;  // Return the maximum water area
}

In the nested loop, Math.min(a[i], a[j]) * (j - i) calculates the area between the heights at indices i and j (which forms a container). This area is then compared with the current value of area using Math.max(area, ...), and if the calculated area is greater, the value of area is updated with the larger value.

By the time both loops finish iterating through all pairs of heights, the area variable will contain the maximum water area that can be formed using any pair of heights. This maximum water area is returned by the maxArea method and printed in the main method using System.out.println("Maximum water area: " + maxWaterArea);.

Real-world solution (stock exchange history):

Now, let’s consider how we can apply this approach to address our real-world challenges.

Table:

CREATE TABLE stock_prices (
    id INT PRIMARY KEY AUTO_INCREMENT,
    date DATE,
    price DECIMAL(10, 2)
);

INSERT INTO stock_prices (date, price) VALUES
    ('2023-01-01', 100.00),
    ('2023-01-02', 105.00),
    ('2023-01-03', 110.00),
    ('2023-01-04', 115.00),
    ('2023-01-05', 112.00),
    ('2023-01-06', 108.00);

Code:

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class StockProfitMaximization {

    public static void main(String[] args) {
        String jdbcUrl = "jdbc:mysql://192.168.0.xx:3306/your_db_name";
        String username = "user_name";
        String password = "password";

        try {
            Connection connection = DriverManager.getConnection(jdbcUrl, username, password);

            Statement statement = connection.createStatement();
            String sqlQuery = "SELECT price FROM stock_prices";
            ResultSet resultSet = statement.executeQuery(sqlQuery);

            int[] prices = new int[6]; // Assuming 6 rows of data
            int index = 0;

            while (resultSet.next()) {
                int price = resultSet.getInt("price");
                prices[index++] = price;
            }

            resultSet.close();
            statement.close();
            connection.close();

            int maxProfit = maxProfit(prices);
            System.out.println("Max Profit: $" + maxProfit);

        } catch (SQLException e) {
            e.printStackTrace();
        }
    }

    public static int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }

        return maxProfit;
    }
}

This code reads historical stock prices from the database, calculates the maximum profit using the “container with most water” logic, and then prints the result. In this case, the “water storage capacity” between two stock prices represents the potential profit from buying at the lower price and selling at the higher price.

The logic:

public static int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }

        return maxProfit;
    }

1. int maxProfit = 0;: Initialize the maxProfit variable to keep track of the maximum profit.
2. Outer Loop (for (int i = 0; i < prices.length; i++)): This loop iterates through each day’s stock price as a potential buying price.
3. Inner Loop (for (int j = i + 1; j < prices.length; j++)): For each potential buying price, this loop iterates through the subsequent days’ stock prices as potential selling prices.
4. maxProfit = Math.max(maxProfit, prices[j] - prices[i]);:
   • Calculate the potential profit by subtracting the potential buying price (prices[i]) from the potential selling price (prices[j]).
   • Compare this potential profit with the current maximum profit (maxProfit).
   • The Math.max function returns the greater of the two values, ensuring that you update maxProfit to hold the maximum profit obtained among all potential buying and selling combinations.
5. return maxProfit;: After both loops complete, the maxProfit variable contains the maximum profit that could be obtained by buying at a lower price and selling at a higher price.

Here’s a simple example to illustrate the logic:

Let’s say you have the following stock prices over five days: [7, 1, 5, 3, 6, 4].

• For the first potential buying price 7:
  • If you sell on the second day (1), the profit is 1 - 7 = -6.
  • If you sell on the third day (5), the profit is 5 - 7 = -2.
  • If you sell on the fourth day (3), the profit is 3 - 7 = -4.
  • If you sell on the fifth day (6), the profit is 6 - 7 = -1.
  • If you sell on the sixth day (4), the profit is 4 - 7 = -3.
  The maximum profit for this potential buying price is -1 (selling on the fifth day).
• For the second potential buying price 1, the maximum profit is 5 (selling on the third day).
• For the third potential buying price 5, the maximum profit is 3 (selling on the sixth day).
• For the fourth potential buying price 3, the maximum profit is 3 (selling on the sixth day).
• For the fifth potential buying price 6, there are no potential selling prices after it.

The maximum profit among all potential buying and selling combinations is 5, which occurs when buying at 1 and selling at 6.

The function iterates through all possible buying and selling combinations and keeps track of the maximum profit, which is returned as the result.