LeetCode #1. Two Sum

Brute Force Solution

-

Time Complexity: O(n²)

This brute force approach checks every possible pair of numbers exactly once, which guarantees finding the solution if it exists, but at the cost of quadratic time complexity.

The outer loop runs n times (where n is the length of the array)
For each iteration of the outer loop, the inner loop runs approximately n times in the worst case
This gives us n × n = n² operations in the worst case.

The worst case occurs when no valid pair exists or the pair is at the end of the array

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space
You're only using a few variables (i, j) and creating a single result array of size 2
The space usage doesn't grow with the input size

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 null;
    }
}

More Efficient (HashMap) Solution

Time Complexity: O(n)

The algorithm makes a single pass through the array (one loop that runs n times)
For each element, it performs two HashMap operations: containsKey() and put()
HashMap operations (lookup and insertion) have O(1) average time complexity
So we have n iterations × O(1) operations per iteration = O(n) total time
This is a significant improvement over the O(n²) brute force approach

Space Complexity: O(n)

In the worst case, we might store nearly all elements in the HashMap before finding a solution
If no solution exists, we'll store all n elements in the HashMap
Each HashMap entry stores a key-value pair (number and its index), but this is still considered O(1) space per element
Therefore, the total extra space used is O(n)
This is the tradeoff we make: we use additional space to achieve better time complexity

Why this is better:

The HashMap solution trades space for time. While the brute force uses O(1) space, it takes O(n²) time. The HashMap approach uses O(n) space but reduces time to O(n). For large inputs, this tradeoff is usually worth it since time complexity improvements from quadratic to linear are much more significant than the linear space overhead.

class Solution {
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> storage = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int delta = target - nums[i];
            if (storage.containsKey(delta)) {
                return new int[] {storage.get(delta), i};
            }
            storage.put(nums[i], i);
        }
        return null;
    }
}