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
and1
in the arraynums
are2
and7
, 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:
- Initialize an empty hashmap to store elements and their corresponding indices.
- Iterate through the array
nums
. - For each element
num
, calculate the differencediff = target - num
. - Check if
diff
exists in the hashmap.
- If it does, return the indices of
num
anddiff
. - 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!