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:

Brute Force Approcah Solution....
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:

Hashmap Approach Two Sum
Hashmap Approach Two Sum
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:

Two pointer two sum
Two pointer two sum
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!

About Nilesh Raut

I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.

15 thoughts on “leet code : Two sum Problem solution – Java || CPP || JavaScript || Python”

  1. bro you solved it by class method and python code for this problem is simpler but i cant understand why we use class and all so please refer me article so that i can understand is use.
    Thankyou.

  2. Itís nearly impossible to find well-informed people for this subject, however, you seem like you know what youíre talking about! Thanks

  3. You’re so awesome! I don’t believe I have read a single thing like that before. So great to find someone with some original thoughts on this topic. Really.. thank you for starting this up. This website is something that is needed on the internet, someone with a little originality!

  4. I am truly thankful to the owner of this web site who has shared this fantastic piece of writing at at this place.

  5. Very nice article, well written. Thank you, helps a lot!

    If someone is looking for a video solution, I recommend you guys to go through this YouTube video on Two Sum. They have explained it in a very simple and easy to understand manner. This for sure has to be the best video on YouTube on Two Sum problem.

Leave a Reply