leet code : Two sum Problem solution – Java || CPP || JavaScript || Python

Sure, let’s solve the “Two Sum” problem using different approaches in C++, Python, Java, and JavaScript, and add some humor along the way! We’ll explore the bruteforce, hashmap, two hashmap, and two-pointer methods for each language.

Time Complexity:

• Bruteforce: O(n^2)
• HashMap: O(n)
• Two Pass HashMap: O(n)
• Two Pointer: O(n log n)

C++:

1. Brute Force Approach:

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {}; // No solution found!
}

Notice: This approach has a time complexity of O(n^2), which isn’t very efficient.

2. HashMap Approach:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (numToIndex.find(complement) != numToIndex.end()) {
            return {numToIndex[complement], i};
        }
        numToIndex[nums[i]] = i;
    }
    return {}; // No solution found!
}

Interesting Fact: This approach has a time complexity of O(n), which is much faster than the brute force method.

3. Two Pass HashMap Approach:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numToIndex;
        
        // First pass: Populate the HashMap
        for (int i = 0; i < nums.size(); i++) {
            numToIndex[nums[i]] = i;
        }
        
        // Second pass: Check for the complement
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (numToIndex.find(complement) != numToIndex.end() && numToIndex[complement] != i) {
                return {i, numToIndex[complement]};
            }
        }
        
        return {};
    }
};

Notice: This approach uses two hashmaps, which might be overkill for this problem.

4. Two-Pointer Approach:

vector<int> twoSum(vector<int>& nums, int target) {
    vector<pair<int, int>> numsWithIndex;
    for (int i = 0; i < nums.size(); i++) {
        numsWithIndex.push_back({nums[i], i});
    }
    sort(numsWithIndex.begin(), numsWithIndex.end());
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = numsWithIndex[left].first + numsWithIndex[right].first;
        if (sum == target) {
            return {numsWithIndex[left].second, numsWithIndex[right].second};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {}; // No solution found!
}

Interesting Fact: This approach requires sorting, so it has a time complexity of O(n*log(n)).

Python:

I’ll provide Python code snippets for the same approaches.

1. Brute Force Approach (Python):

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # No solution found!

2. HashMap Approach (Python):

def twoSum(nums, target):
    numToIndex = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in numToIndex:
            return [numToIndex[complement], i]
        numToIndex[num] = i
    return []  # No solution found!

3. Two Pass Hashmap Approach (Python):

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        
        # First pass: Populate the dictionary
        for i, num in enumerate(nums):
            num_to_index[num] = i
        
        # Second pass: Check for the complement
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_to_index and num_to_index[complement] != i:
                return [i, num_to_index[complement]]
        
        return []

4. Two-Pointer Approach (Python):

def twoSum(nums, target):
    numsWithIndex = [(num, i) for i, num in enumerate(nums)]
    numsWithIndex.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        num_sum = numsWithIndex[left][0] + numsWithIndex[right][0]
        if num_sum == target:
            return [numsWithIndex[left][1], numsWithIndex[right][1]]
        elif num_sum < target:
            left += 1
        else:
            right -= 1
    return []  # No solution found!

Java:

1. Brute Force Approach (Java):

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[]{}; // No solution found!
}

2. HashMap Approach (Java):

public int[] twoSum(int[] nums, int target) {
    Map<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[]{}; // No solution found!
}

3. Two Pass Hashmap Approach (Java):

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numToIndex = new HashMap<>();
        
        // First pass: Populate the HashMap
        for (int i = 0; i < nums.length; i++) {
            numToIndex.put(nums[i], i);
        }
        
        // Second pass: Check for the complement
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numToIndex.containsKey(complement) && numToIndex.get(complement) != i) {
                return new int[]{i, numToIndex.get(complement)};
            }
        }
        
        return new int[0];
    }
}

4. Two-Pointer Approach (Java):

public int[] twoSum(int[] nums, int target) {
    int[][] numsWithIndex = new int[nums.length][2];
    for (int i = 0; i < nums.length; i++) {
        numsWithIndex[i][0] = nums[i];
        numsWithIndex[i][1] = i;
    }


    Arrays.sort(numsWithIndex, Comparator.comparingInt(arr -> arr[0]));
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = numsWithIndex[left][0] + numsWithIndex[right][0];
        if (sum == target) {
            return new int[] {numsWithIndex[left][1], numsWithIndex[right][1]};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{}; // No solution found!
}

JavaScript:

1. Brute Force Approach (JavaScript):

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return []; // No solution found!
}

2. HashMap Approach (JavaScript):

function twoSum(nums, target) {
    const numToIndex = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numToIndex.has(complement)) {
            return [numToIndex.get(complement), i];
        }
        numToIndex.set(nums[i], i);
    }
    return []; // No solution found!
}

3. Two Pass HashMap Approach (JavaScript):

var twoSum = function(nums, target) {
    const numToIndex = {};
    
    // First pass: Populate the object
    for (let i = 0; i < nums.length; i++) {
        numToIndex[nums[i]] = i;
    }
    
    // Second pass: Check for the complement
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (complement in numToIndex && numToIndex[complement] !== i) {
            return [i, numToIndex[complement]];
        }
    }
    
    return [];
};

4. Two-Pointer Approach (JavaScript):

function twoSum(nums, target) {
    const numsWithIndex = nums.map((num, index) => [num, index]);
    numsWithIndex.sort((a, b) => a[0] - b[0]);
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const sum = numsWithIndex[left][0] + numsWithIndex[right][0];
        if (sum === target) {
            return [numsWithIndex[left][1], numsWithIndex[right][1]];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return []; // No solution found!
}

And there you have it! Four different programming languages, four approaches to solving the “Two Sum” problem, and hopefully a smile on your face as well! Remember, choosing the right approach depends on the specific requirements and constraints of your problem. Happy coding!