Min Priority Queue Implementation with Heap Data structure
Min Priority Queue is a data structure which manage a list of keys(values). And…
July 08, 2019
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Simply iterate over array 2 times, and look if the sum equals to target.
public int[] twoSum(int[] nums, int target) {
int l = nums.length;
for (int i=0; i<l; i++) {
for (int j=i+1; j<l; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
Whenever this kind of problem comes, one thing came in mind is using HashSet. But, this problem is not asking you to return the values that sum upto a target value. It is asking you to return indexes of numbers.
So, you have to maintain a HashMap<Integer, Integer>, which is like the number itself, and its index in the original array. HashMap has the property of searching its key and value in O(1).
While iterating, we just have to check whether arrary has the remaining difference else where in array or not. For this purpose, we are keeping a copy of array values and its index into a HashMap.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<>();
int l = nums.length;
for (int i=0; i<l; i++) {
int pairValue = target-nums[i];
if (hashMap.containsKey(pairValue)) {
return new int[]{i, hashMap.get(pairValue)};
}
if (!hashMap.containsKey(nums[i])) {
hashMap.put(nums[i], i);
}
}
return null;
}
Min Priority Queue is a data structure which manage a list of keys(values). And…
System design interview is pretty common these days, specially if you are having…
Here are some tips while preparing for your coding interviews. 1. Do study or…
Graph Topological Sorting This is a well known problem in graph world…
This problem is a simple mathematical calculation. Lets start deriving some…
Problem Statement Given a string, determine if it is a palindrome, considering…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…