Bubble Sort Algorithm
This is kind of preliminary technique of sorting. And, this is the first…
September 13, 2019
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
A simple brute force is the start. But, it is so simple. Lets not discuss it. You just need to make sure that result must have unique entries
Like, in two-sum problem. We used a HashSet. We can use it here as well. Again, to maintain unique elements, it added complexity.
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet();
int l = nums.length;
for (int i=0; i<l; i++) {
Set<Integer> vals = new HashSet();
for (int j=i+1; j<l; j++) {
if (j == i) continue;
int requiredNum = 0 - (nums[i] + nums[j]);
if (vals.contains(requiredNum)) {
List<Integer> iRes = new ArrayList();
iRes.add(requiredNum);
iRes.add(nums[j]);
iRes.add(nums[i]);
Collections.sort(iRes);
result.add(iRes);
}
if (!vals.contains(nums[j])) {
vals.add(nums[j]);
}
}
}
List<List<Integer>> r = new ArrayList(result);
return r;
}
Lets look at most optimized one.
public List<List<Integer>> threeSum_2(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i=0; i<len; i++) {
//to avoid processing duplicate values
if (i > 0 && nums[i-1] == nums[i]) continue;
int l = i+1;
int r = len-1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
List<Integer> ir = new ArrayList<>();
ir.add(nums[i]); ir.add(nums[l]); ir.add(nums[r]);
res.add(ir);
l++;
r--;
//to move over duplicate values
while (l < r && nums[l-1] == nums[l]) l++;
while (l < r && nums[r+1] == nums[r]) r--;
}
else if (s < 0) {
l++;
}
else {
r--;
}
}
}
return res;
}
This is kind of preliminary technique of sorting. And, this is the first…
First try to understand question. Its a binary tree, not a binary search tree…
Problem Statement Implement atoi which converts a string to an integer…
Problem Statement Roman numerals are represented by seven different symbols: I…
This algorithm is very efficient one, and is classic example of Divide and…
Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…