Leetcode Two Sum Problem in three different languages

 The problem from Leetcode.com: 

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9 

Output: [0,1] 

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

First, let's attack this using Python, and then we'll do the same with Java and compare the differences in the solutions.

PYTHON

Problem-solving:

We can solve this problem by using a hash table in Python. First, we will iterate over the array nums and check if the difference between the target and the current element of nums exists in the hash table. If it does, we return the indices of the current element and the difference. Otherwise, we add the current element of nums and its index to the hash table.

Steps:

1. Initialize an empty hash table.
2. Loop through the array nums.
3. For each element, calculate the difference between the target and the element.
4. Check if the difference is already in the hash table. If it is, return the indices of the current element and the difference.
5. Otherwise, add the current element and its index to the hash table.
6. If no solution is found, return an empty list.

Python Code:

Let's write the Python code for the above algorithm:

class Solution(object):
    def twoSum(self, nums, target):
        hash_table = {}
        for i in range(len(nums)):
            difference = target - nums[i]
            if difference in hash_table:
                return [hash_table[difference], i]
            hash_table[nums[i]] = i
        return []

What is happening:

In this code, we first create an empty hash table called hash_table. Then, we loop through the array nums using a for loop. For each element of nums, we calculate the difference between the target and the current element and store it in the variable difference.

Next, we check if the difference exists in the hash table using the in keyword. If it does, we return a list containing the indices of the current element and the difference, which are stored in the hash table. Otherwise, we add the current element and its index to the hash table using the line hash_table[nums[i]] = i.

Finally, if no solution is found, we return an empty list.

JAVA

Problem-Solving:

Let's solve the same problem but in Java. We can solve this problem by using a hash table in Java. First, we will iterate over the array nums and check if the difference between the target and the current element of nums exists in the hash table. If it does, we return the indices of the current element and the difference. Otherwise, we add the current element of nums and its index to the hash table. If this sounds familiar, you're right!

Rather than repeat the steps, it's the same as for Python.

Java Code:

Let's write the Java code for the above algorithm:

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap hashTable = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (hashTable.containsKey(difference)) {
                return new int[] { hashTable.get(difference), i };
            }
            hashTable.put(nums[i], i);
        }
        return new int[] {};
    }
}

What is happening:

In this code, we first import the HashMap class from the java.util package. Then, we create an empty hash table called hashTable using the HashMap class.

Next, we loop through the array nums using a for loop. For each element of nums, we calculate the difference between the target and the current element and store it in the variable difference.

Next, we check if the difference exists in the hash table using the containsKey() method of the HashMap class. If it does, we return a new int array containing the indices of the current element and the difference, which are stored in the hash table using the get() method. Otherwise, we add the current element and its index to the hash table using the put() method.

Finally, if no solution is found, we return an empty int array.

Comparisons:

Both Python and Java solutions use a hash table to solve the problem. The hash table is used to store the elements of the input array along with their indices. This allows us to efficiently lookup elements in the array and check if their complement (the difference between the target and the element) is already in the hash table.

However, there are some differences in the syntax and implementation of hash tables in Python and Java. In Python, we can create a dictionary using curly braces {}. In Java, we use the HashMap class from the java.util package to create a hash table. Here is an example of how we can create an empty hash table in Python and Java:

Python:

hash_table = {}

Java:

HashMap hashTable = new HashMap<>();

In Python, we can check if a key is in a dictionary using the in keyword. In Java, we use the containsKey() method of the HashMap class. Here is an example of how we can check if a key exists in a hash table in Python and Java:

Python: 

if difference in hash_table:
    # do something

Java:

if (hashTable.containsKey(difference)) {
    // do something
}

In Python, we can add a key-value pair to a dictionary using square brackets []. In Java, we use the put() method of the HashMap class. Here is an example of how we can add a key-value pair to a hash table in Python and Java:

Python: 

hash_table[nums[i]] = i

Java:

hashTable.put(nums[i], i);

Finally, both Python and Java solutions return an array containing the indices of the elements that add up to the target. In Python, we can return a list using square brackets []. In Java, we return an int array using the new keyword. Here is an example of how we can return an array in Python and Java:

Python: 

return [hash_table[difference], i]

Java:

return new int[] { hashTable.get(difference), i };

While the basic approach to solving the Two Sum problem using a hash table is the same in Python and Java, there are some differences in the syntax and implementation of hash tables in the two languages. As always, the most important part to spend time on, is solving the problem. What language you use after that will vary, and the syntax will obviously vary, but often not by as much as you'd think. 

PHP

Now let's look at a different language, PHP. Again, the approach will use hashtables (well, actually arrays), and the algorithm will be the same as for Python and Java. 

function twoSum($nums, $target) {
    $hashTable = array();
    for ($i = 0; $i < count($nums); $i++) {
        $difference = $target - $nums[$i];
        if (isset($hashTable[$difference])) {
            return array($hashTable[$difference], $i);
        }
        $hashTable[$nums[$i]] = $i;
    }
    return array();
}

What is happening:

In this code, we first create an empty hash table called $hashTable using an array in PHP. Then, we loop through the array nums using a for loop. For each element of nums, we calculate the difference between the target and the current element and store it in the variable $difference.

Next, we check if the difference exists in the hash table using the isset() function. If it does, we return an array containing the indices of the current element and the difference, which are stored in the hash table using the square brackets []. Otherwise, we add the current element and its index to the hash table using the square brackets [].

Finally, if no solution is found, we return an empty array using the array() function.

Differences with PHP, Python and Java:

While the basic approach to solving the Two Sum problem using a hash table is the same in Python, Java, and PHP, there are some differences in the syntax and implementation of hash tables in the three languages.

In PHP, we create an empty hash table using an array. We can then use the square brackets [] to add key-value pairs to the hash

The Two Sum problem is a very simple problem, but it illustrates how similar the approach is, how you decide to tackle the problem, and the basic layout for how to write your code. The main difference is how each language is written and handles things like adding an item to a hash table or how to display the results. The hard part is getting good at reading through a problem and recognizing what steps need to happen in the code to achieve your outcome. The easy part is writing the code.

References

Two Sum - LeetCode. https://leetcode.com/problems/two-sum/