For the first time, I'm answering a Leetcode question and providing the approach I used to figure it out. Also sharing a modified strategy to reduce the complexity
Question -1 :-
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]
Initial approach:
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] indicesArray=new int[2];
for(int i=0;i<nums.length-1;i++) {
for(int j=i+1;j<nums.length;j++) {
if(target== nums[i]+nums[j]) {
indicesArray[0]=i;
indicesArray[1]=j;
return indicesArray;
}
}
}
return null;
}
}
Explanation:
The twoSum function takes two parameters: an array of integers nums and an integer target. The function returns an array of integers containing the indices of the two numbers in the input array that add up to the target.
The function starts by initializing a new integer array indicesArray of size 2. This array will be used to store the indices of the two numbers that add up to the target.
The function then uses two nested for loops to iterate over all possible pairs of numbers in the input array. For each pair of numbers, the function checks if their sum is equal to the target. If it is, the function sets the first element of indicesArray to the index of the first number in the pair and sets the second element of indicesArray to the index of the second number in the pair. Finally, the function returns indicesArray.
If no pair of numbers is found that adds up to the target, the function returns null.
In summary, this code is a simple brute-force solution to the "Two Sum" problem that iterates over all possible pairs of numbers in the input array until it finds a pair that adds up to the target.
The time complexity of this solution is O(n^2)
Final approach:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return new int[] { -1, -1 };
}
}
The twoSum function takes two parameters: an array of integers nums and an integer target. The function returns an array of integers containing the indices of the two numbers in the input array that add up to the target.
The function starts by initializing an empty HashMap called map. The HashMap will be used to store the values and their corresponding indices.
The function then uses a for loop to iterate over each element of the input array. For each element, the function computes its complement (the difference between the target and the current element) and checks if the complement is already in the map. If the complement is in the map, then the function has found a pair of elements that add up to the target, so it returns an array containing the indices of the two elements. If the complement is not in the map, then the current element and its index are added to the map.
If no pair of numbers is found that adds up to the target, the function returns an array containing two -1 values.
The time complexity of this solution is O(n), where n is the length of the input array. This is because the for loop iterates over each element of the input array exactly once, and the operations inside the loop (complement calculation, containsKey check, and put operation) all take constant time on average.
Therefore, this solution is much more efficient than the previous solution, especially for larger input sizes. It uses a hash table to store the values and their indices, allowing for constant-time lookup of complements.