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:
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:
Day 2 : FaceBook Asked interview Quetion :- Add Binary Sum – Java ,Python ,Cpp
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:
- Leet Code 2612 Minimum Reverse Operations
- Leet code 206 Reverse Linked List
- Leet Code 420 Strong Password Checker
- Leetcode 1359 Count All Valid Pickup and Delivery
- Leet code 799. Champagne Tower
- LeetCode 389. Find The Difference
- Leetcode 775. Find The Global and Local Inversions
- Leetcode 316. Remove Duplicate Letters
- LeetCode 2233 Maximum Product After K Increments
- LeetCode 880. Decoded String at Index
- LeetCode 905. Sort Array By Parity
- LeetCode 896. Monotonic Array
- LeetCode 132. Pattern