Month:

When solving the popular “Two Sum” problem, different programming languages and techniques offer varying levels of efficiency. Let’s compare Python and Java implementations using both nested loops and optimized data structures.

The Problem Statement

Given an array of integers and a target sum, return the indices of two numbers that add up to the target. For example:

Example Input

array = [2, 7, 11, 15]
target = 9

Expected Output

[0, 1]

This output indicates that the numbers at indices 0 and 1 (2 and 7) add up to 9.

Python Solutions

1. Python with Nested Loops

This straightforward solution uses two nested loops to check every possible pair of numbers.

Code:

def two_sum(array, target):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            if array[i] + array[j] == target:
                return [i, j]
    return []

array = [2, 7, 8, 11]
target = 9
print(two_sum(array, target))  # Output: [0, 1]

Performance:

• Memory Usage: 13.5 MB
• Runtime: 2093 ms

Explanation:

Python checks every pair of numbers in the array, making it accurate but slow. Its time complexity is O(n²) due to the double loop.

2. Python with Dictionary (Optimized)

This optimized solution leverages a dictionary to store numbers and their indices for faster lookups.

Code:

class Solution(object):
    def twoSum(self, nums, target):
        num_to_index = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_to_index:
                return [num_to_index[complement], i]
            num_to_index[num] = i
        return []

nums = [2, 7, 11, 15]
target = 9
solution = Solution()
print(solution.twoSum(nums, target))  # Output: [0, 1]

Performance:

• Memory Usage: 13.1 MB
• Runtime: 0 ms

Explanation:

By storing the numbers in a dictionary, we reduce the time complexity to O(n). The dictionary enables instant lookups for the complement of the current number.

Java Solutions

1. Java with Nested Loops

Similar to Python’s nested loops, this solution iterates through every pair of numbers to find the correct indices.

Code:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {};
    }
}

int[] nums = {2, 7, 11, 15};
int target = 9;
Solution sol = new Solution();
int[] result = sol.twoSum(nums, target);
// Output: [0, 1]

Performance:

• Memory Usage: 45 MB
• Runtime: 78 ms

Explanation:

While Java runs nested loops more efficiently than Python due to its compiled nature, the time complexity remains O(n²).

2. Java with HashMap (Optimized)

This implementation mirrors Python’s dictionary-based approach but uses Java’s HashMap for efficient lookups.

Code:

import java.util.HashMap;

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

int[] nums = {2, 7, 11, 15};
int target = 9;
Solution sol = new Solution();
int[] result = sol.twoSum(nums, target);
// Output: [0, 1]

Performance:

• Memory Usage: 44.9 MB
• Runtime: 2 ms

Explanation:

Using a HashMap significantly reduces the runtime to O(n), as lookups and insertions in a HashMap are extremely fast.

Comparing the Solutions

Solution	Language	Time Complexity	Runtime	Memory Usage
Nested Loops	Python	O(n²)	2093 ms	13.5 MB
Dictionary (Optimized)	Python	O(n)	0 ms	13.1 MB
Nested Loops	Java	O(n²)	78 ms	45 MB
HashMap (Optimized)	Java	O(n)	2 ms	44.9 MB

Key Takeaways:

1. Optimized solutions outperform nested loops: Leveraging data structures like dictionaries (Python) or HashMaps (Java) can drastically reduce runtime.
2. Language differences matter: Python’s nested loops are significantly slower than Java’s, but its dictionary implementation is faster due to Python’s efficient data handling.
3. Memory usage varies: Java generally consumes more memory due to its internal processing overhead.

Conclusion

When solving problems like Two Sum, choosing the right data structure can drastically improve performance. For optimal efficiency, avoid nested loops in favor of dictionaries or HashMaps. While Python is often faster for smaller datasets due to its interpreted nature, Java’s compiled approach ensures consistent performance across larger datasets.