Convert String to Integer - atoi - Leet Code Solution
Problem Statement Implement atoi which converts a string to an integer…
November 17, 2020
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Input: nums = [], target = 0
Output: []
Lets take help of our two-sum problem.
private List<List<Integer>> twoSum(int[] nums, int target, int start) {
List<List<Integer>> res = new ArrayList<>();
int l = start;
int r = nums.length-1;
while (l < r) {
/**
* second conditions are for avoiding duplicates.
*/
if (nums[l] + nums[r] < target || (l > start && nums[l-1] == nums[l])) {
l++;
}
else if (nums[l] + nums[r] > target || (r < nums.length-1 && nums[r] == nums[r+1])) {
r--;
}
else {
List<Integer> t = new ArrayList<>();
t.add(nums[l]);
t.add(nums[r]);
res.add(t);
l++;
r--;
}
}
return res;
}
// -2 -1 0 0 1 2
private List<List<Integer>> helper(int[] nums, int target, int startIndex, int k) {
List<List<Integer>> res = new ArrayList<>();
if (startIndex >= nums.length || nums[startIndex] * k > target || target > nums[nums.length - 1] * k) {
return res;
}
else if (k == 2) {
return twoSum(nums, target, startIndex);
}
else {
for (int i=startIndex; i<nums.length; i++) {
//This condition is to avoid duplicates
if (i == startIndex || nums[i] != nums[i-1]) {
List<List<Integer>> res2 = helper(nums, target-nums[i], i+1, k-1);
for (List<Integer> t : res2) {
List<Integer> newRes = new ArrayList<>();
newRes.add(nums[i]);
newRes.addAll(t);
res.add(newRes);
}
}
}
}
return res;
}
public List<List<Integer>> fourSum(int[] nums, int target) {
//sorting will help in avoiding duplicates in easy manner
Arrays.sort(nums);
return helper(nums, target, 0, 4);
}
O(n^2)
Problem Statement Implement atoi which converts a string to an integer…
Problem Statement Determine whether an integer is a palindrome. An integer is a…
Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…
Counting sort runs on relatively smaller set of input. Counting sort calculates…
Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…
Problem Statement Given an array of integers, find if the array contains any…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…