Check whether an integer number given is palindrome or not - Leet Code Solution
Problem Statement Determine whether an integer is a palindrome. An integer is a…
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;
}
Problem Statement Determine whether an integer is a palindrome. An integer is a…
Problem Statement Given two strings s and t , write a function to determine if t…
Its a kind of incremental insertion technique, where the algorithm build up…
Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…
Problem Statement Write a function that reverses a string. The input string is…
It is one of a simple algorithm to study for a beginner to understanding sorting…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…