LeetCode problem 1#: Two Sum solution

LeetCode, the renowned coding platform, offers a plethora of challenges to help developers enhance their problem-solving skills. One of the introductory challenges on LeetCode is Problem #1 – “Two Sum”. In this article, we’ll dissect this problem, understand its requirements, and explore potential solutions.

Problem Description

The “Two Sum” problem is a classic coding challenge that revolves around finding a pair of numbers in an array that add up to a specific target value.

Input:

• An array of integers, nums.
• A target integer, target.

Output:

• The indices of the two numbers such that they add up to the target.

It’s important to note that there is exactly one solution, and the same element cannot be used twice.

Example

Consider the following example:

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

Explanation:

• The numbers at indices 0 and 1 in the array nums are 2 and 7, respectively.
• 2 + 7 = 9, which matches the target value.

Solution 1

The first possible solution for this problem, is based on a “brute-force” algorithm to generate all possible pair of numbers in the input array. We can use two levels for loop, but we need to check that we don’t generate two same values; we can achieve this with an if statement of i!=j.

This solution has a time complexity of O^2(n), where n is the number of elements in the array. It is a good solution, but it is not the efficient one.

Code implementation (in Java)

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

Code implementation (in Python)

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

# Example Usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # Output: [0, 1]

Solution 2

To solve this problem, we can employ a straightforward approach that involves iterating through the array and checking if the difference between the target value and the current element exists in a hashmap.

Here’s a step-by-step breakdown:

1. Initialize an empty hashmap to store elements and their corresponding indices.
2. Iterate through the array nums.
3. For each element num, calculate the difference diff = target - num.
4. Check if diff exists in the hashmap.

• If it does, return the indices of num and diff.
• If not, add num and its index to the hashmap.

This approach has a time complexity of O(n), where n is the number of elements in the array. Since we iterate through the array only once, the algorithm is efficient.

Code implementation (in Java)

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

Code Implementation (in Python)

def two_sum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        checking = target - num
        if num in num_map:
            return [num_map[num], i]
        else:
            num_map[checking] = i
    return []

# Example Usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # Output: [0, 1]

Conclusion

LeetCode’s “Two Sum” problem serves as an excellent introduction to the platform’s array-related challenges. By employing a hashmap-based approach, we can efficiently find a pair of numbers that sum up to a specific target. This problem not only hones our coding skills but also reinforces our understanding of basic data structures and algorithms. Happy coding!