Home » leet code » leet code 1. Two sum (easy)

# leet code 1. Two sum (easy)

Leet Code 1. Two Sum : Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “two sum ” or “Leet Code .1

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:

LeetCode 15 : Three (3) Sum

``````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:

Find the Longest Substring Without Repeating Characters: Solution and Algorithm

``````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 {};
}
};
``````

Leet Code: Rotate Array C++ Python || JavaScript || Java solution:

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!

List of Some important Leet code Questions: