Algorithms – Part 1: Brute-force and Array

Earlier this year, I launched my inaugural Road to Google series, and it garnered significant attention within the blogging community due to its comprehensive explanations of coding algorithms. The primary objective behind creating this series wasn’t solely on enhancing my coding skills; it also involved sharing my knowledge with a broader audience. Just as one of the most effective methods of solidifying your own understanding is by simplifying rocket science concepts for a five-year-old, I aimed to present complex coding topics in a similarly understandable manner.

This time around, in order to further strengthen my coding skills, I’ve taken a step beyond the existing Road to Google series. I’ve embarked on a new journey called the “Algorithm Series,” where we delve into the practical and real-world applications of algorithmic concepts. This series aims to bridge the gap between theory and practical solutions.

Through this series, here is my environment:

• OS (Client) : Ubuntu 22.04
• OS (Server): Ubuntu Server 22.04
• Java version: openjdk 17.0.8 2023-07-18
• DB: MySQL 8.0

The crux of the matter lies in my utilization of the MySQL database to facilitate a more hands-on comprehension of algorithms. This approach proves invaluable in enhancing our grasp of the concepts by providing a visual framework for better understanding.

Here’s the original post: Road to Google – Part 1: Array and Brute Force

Question:

Given an array of integers, return the indices of the two numbers that add up to a given target.

Original answer:

This was the first answer we came up with to solve the problem.

class array_sample {

    public static void findPair(int[] nums, int targetNum){
        // consider each element except the last
        for(int i = 0; i < nums.length - 1; i++) {
            // start from the i'th element until the last element
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] == targetNum) {
                    System.out.printf("Pair found (%d, %d)", nums[i], nums[j]);
                    return;
                }
            }
        }
        // we reach here if the pair is not found
        System.out.println("Pair not found");
    }

    public static void main(String[] args) {
        int[] nums = {1,3,7,9,2};
        int targetNum = 11;
        findPair(nums, targetNum);
    }
}

Practical framework:

As previously noted, to achieve a more comprehensive visual understanding and enhance practical application, why not leverage the capabilities of the MySQL database? We can effectively transition the brute-force algorithm from theory to real-world solutions using this approach.

And here is the table and dataset we’ve got this time:

CREATE TABLE transactions (
    transaction_id INT PRIMARY KEY,
    amount DECIMAL(10, 2)
);

INSERT INTO transactions (transaction_id, amount) VALUES
(1, 50.00),
(2, 30.00),
(3, 20.00),
(4, 40.00),
(5, 60.00),
(6, 10.00),
(7, 25.00),
(8, 35.00),
(9, 45.00);

For the given challenges, I provide you with two possible solutions for it.

First solution – using SQL:

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.Scanner;

public class JDBCSampleLocalArray1 {

    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 {
            Scanner scanner = new Scanner(System.in);

            System.out.print("Enter target amount: ");
            double targetAmount = Double.parseDouble(scanner.nextLine());

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

            String sqlQuery = "SELECT t1.transaction_id, t2.transaction_id\n" +
                    "FROM transactions t1\n" +
                    "JOIN transactions t2 ON t1.transaction_id < t2.transaction_id\n" +
                    "WHERE t1.amount + t2.amount = ?";

            PreparedStatement preparedStatement = connection.prepareStatement(sqlQuery);
            preparedStatement.setDouble(1, targetAmount);

            ResultSet resultSet = preparedStatement.executeQuery();

            while (resultSet.next()) {
                int transactionId1 = resultSet.getInt(1);
                int transactionId2 = resultSet.getInt(2);
                System.out.println("Transaction IDs: " + transactionId1 + ", " + transactionId2);
            }

            resultSet.close();
            preparedStatement.close();
            connection.close();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}

The result:

user@client:~/work$ java -cp .:mysql-connector-java-8.0.11.jar JDBCSampleLocalArray1
Enter target amount: 80
Sat Aug 26 21:41:00 JST 2023 WARN: Establishing SSL connection without server's identity verification is not recommended. According to MySQL 5.5.45+, 5.6.26+ and 5.7.6+ requirements SSL connection must be established by default if explicit option isn't set. For compliance with existing applications not using SSL the verifyServerCertificate property is set to 'false'. You need either to explicitly disable SSL by setting useSSL=false, or set useSSL=true and provide truststore for server certificate verification.
Transaction IDs: 1, 2
Transaction IDs: 3, 5
Transaction IDs: 8, 9
Sat Aug 26 21:41:01 JST 2023 WARN: Caught while disconnecting...

As you might have discerned, this approach represents an efficient means of achieving practical utility, bypassing the need to solely rely on Java’s algorithmic coding framework. Instead, we’ve implemented an SQL solution, resulting in more concise and visually straightforward code.

Second solution – coding algorithm:

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;

class JDBCSampleLocalArray4 {

    public static void findPair(List<Integer> nums, int targetNum){
        // create a map to store the pairs that we have found
        HashMap<Integer, Integer> pairs = new HashMap<>();

        // consider each element except the last
        for(int i = 0; i < nums.size() - 1; i++) {
            // start from the i'th element until the last element
            for(int j = i + 1; j < nums.size(); j++) {
                // if the sum of the two numbers is equal to the target number, then add the pair to the map
                if(nums.get(i) + nums.get(j) == targetNum) {
                    pairs.put(nums.get(i), nums.get(j));
                }
            }
        }

        // print all of the pairs in the map
        for(Integer key : pairs.keySet()) {
            System.out.printf("Pair found (%d, %d)", key, pairs.get(key));
        }
    }


    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 amount FROM transactions";
            ResultSet resultSet = statement.executeQuery(sqlQuery);

            List<Integer> resultList = new ArrayList<>();

            // Populate the resultList variable outside of the do-while loop
            while (resultSet.next()) {
                int value = resultSet.getInt("amount");
                resultList.add(value);
            }

            int targetNum = 80;
            findPair(resultList, targetNum);

            resultSet.close();
            statement.close();
            connection.close();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}

The result:

Pair found (50, 30)Pair found (35, 45)Pair found (20, 60)

Allow me to break down the logic by dissecting two of the aforementioned key points: the outer and inner for-loops.

The outer loop:

for(int i = 0; i < nums.size() - 1; i++)

What you might be wondering is the reason behind the -1. In the realm of programming, lists start from 0, so using -1 is necessary to prevent overshooting the list’s size. Without subtracting 1, the index would exceed the list’s bounds.

The inner loop:

for(int j = i + 1; j < nums.size(); j++)

The segment “int j = i + 1” signifies that the inner loop, represented by variable j, should always iterate subsequent to the outer loop i. This arrangement ensures that the loops never overlap.