Hello,
Update:
Revised the solution a bit to handle the construction of sub-array inside the twoSum base case method. I also realized that when I run the solution, the test case in question passes. Not sure if the test case expectations was revised / corrected by leetcode post the submission of this clarification.
Whle trying to work out a solution of the 4Sum problem using twoSum solution based on hashing as the underlying base case, I am finding that the official solution / implementation expected by leetcode / provided in leetcode may have a gap / bug.
In summary, the base case twoSum implementaion linear scans the input array only from the passed in start index for finding the second possible pair for the solution, given that the caller would have fixed the first pair combination, This inabiliy to pick elements that are behind the passed in start index may result in missed quadruplet combinations that are valid.
e.g. Test Case Input 1:
[5,5,3,5,1,-5,1,-2]
4
In here, there are two possible valid quadruplets that sum up to 4 namely
[ [-5,1,3,5] , [-2,0,1,5] ]
However due to the above mentioned gap in the implementation, the expected output in leetcode only mentions [ [-5,1,3,5] ]
Becase of this I am unable to submit my solution.
Can you please check the above and accept my submission?
I am dumpinhg my solution below for review and acceptance.
class Solution {
final int tupleLength = 4;
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<Integer> fixElements = new ArrayList<>();
List<List<Integer>> result = findKsum_Approach2UsingHashSet(nums, target, 0, 4, fixElements);
Set<List<Integer>> resultSet = new HashSet<>();
for(List<Integer> res : result) {
Collections.sort(res);
resultSet.add(res);
}
return new ArrayList<List<Integer>>(resultSet);
}
private static List<List<Integer>> findKsum_Approach2UsingHashSet(int[] arr, int targetSum, int start, int tupleLength,
List<Integer> fixedElements) {
List<List<Integer>> result = new ArrayList<>();
if(start == arr.length || (arr[start]*tupleLength > targetSum) || (arr[arr.length-1]*tupleLength < targetSum))
return result;
if(tupleLength == 2)
return findTwoSumUsingHashMap(arr, targetSum, fixedElements);
for(int i=start; i<arr.length; i++) {
if(i==start || arr[i] != arr[i-1]) {
List<Integer> tmpFixedElements = new ArrayList<>(fixedElements);
tmpFixedElements.add(arr[i]);
for(List<Integer> res : findKsum_Approach2UsingHashSet(arr, targetSum - arr[i], i + 1,
tupleLength - 1, tmpFixedElements)) {
result.add(new ArrayList<>(Arrays.asList(arr[i])));
result.get(result.size()-1).addAll(res);
}
}
}
return result;
}
private static List<List<Integer>> findTwoSumUsingHashMap(int[] arr, int targetSum, List<Integer> fixedElements) {
Set<Integer> elementSet = new HashSet<>();
List<List<Integer>> twoSumResult = new ArrayList<>();
//Remove already fixed elements from arr
int [] newArr =new int[arr.length - fixedElements.size()];
List<Integer> fixedElementsCopy = fixedElements.stream().map(element -> new Integer(element)).collect(Collectors.toList());
int j=0;
for(int i=0; i<arr.length; i++) {
if(!fixedElementsCopy.contains(arr[i])) {
newArr[j++] = arr[i];
}
else {
fixedElementsCopy.remove((Object)arr[i]);
}
}
for(int i = 0; i < newArr.length; i++) {
if(twoSumResult.isEmpty() || twoSumResult.get(twoSumResult.size()-1).get(0) != newArr[i]) {
if (elementSet.contains(targetSum - newArr[i])) {
List<Integer> elementList = Arrays.asList(newArr[i], targetSum - newArr[i]);
twoSumResult.addAll(Collections.singleton(elementList));
}
}
elementSet.add(newArr[i]);
}
return twoSumResult;
}}
bug in leetcode