forked from lemonbashar/java-algo-expert
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFourSum.java
More file actions
124 lines (108 loc) · 3.78 KB
/
FourSum.java
File metadata and controls
124 lines (108 loc) · 3.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package algoexpert.hard;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
/*
PROBLEM:
Given array, find all quadruplets that sum to target
a + b + c + d = target
LOGIC:
loop through array
- for unseen elements | check sum in hash table
- for seen elements | add sum in hash table
SOLUTIONS:
1. Forward and Backward Loop - time : O(n^2) | space : O(n^2) - n^2 currentSum combinations
- worst case : O(n^3) [going through HashMap]
2. Sort and Three Sum (Two Pointer) - time : O(n^3) | space : O(1) - not accounting space for quadruplets
*/
public class FourSum
{
public static void test()
{
int [] test = {-2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int target = 4;
ArrayList<Integer []> quadruplets = fourNumberSum(test, target);
for (Integer[] quad : quadruplets)
{
for (int x : quad)
{ System.out.print(x + " ");}
System.out.println();
}
}
public static ArrayList<Integer[]> fourNumberSum(int[] array, int targetSum)
{
return faster(array, targetSum);
}
// time : O(n^2) | space : O(n^2)
public static ArrayList<Integer[]> faster(int[] array, int targetSum)
{
ArrayList<Integer[]> solution = new ArrayList<Integer[]>();
HashMap<Integer, ArrayList<Integer[]>> sumPairs = new HashMap<>();
for (int i = 0; i < array.length - 1; ++i)
{
for (int j = i+1; j < array.length; ++j)
{
int findSum = targetSum - array[i] - array[j];
if (sumPairs.containsKey(findSum))
{
ArrayList<Integer []> list = sumPairs.get(findSum);
for (Integer[] pair : list)
{ solution.add(new Integer[] {pair[0], pair[1], array[i], array[j]} ); }
}
}
for (int k = 0; k < i; ++k)
{
int currentSum = array[i] + array[k];
if (sumPairs.containsKey(currentSum))
{
ArrayList<Integer []> list = sumPairs.get(currentSum);
list.add(new Integer[] {array[k], array[i]});
sumPairs.put(currentSum, list);
}
else
{
ArrayList<Integer []> list = new ArrayList<>();
list.add(new Integer[] {array[k], array[i]});
sumPairs.put(currentSum, list);
}
}
}
return solution;
}
// time : O(n^3) | space : O(1) - not accounting space for quadruplets
public static ArrayList<Integer[]> slower(int[] array, int targetSum)
{
ArrayList<Integer[]> solution = new ArrayList<Integer[]>();
Arrays.sort(array);
for (int i = 0; i < array.length - 1; ++i)
{
for (int j = i+1; j < array.length; ++j)
{
int first = array[i];
int second = array[j];
int newTarget = targetSum - first - second;
int front = j + 1;
int back = array.length - 1;
while (front < back)
{
if (array[front] + array[back] == newTarget)
{
Integer [] fourNums = {first, second, array[front], array[back]};
solution.add(fourNums);
front += 1;
back -= 1;
}
else if (array[front] + array[back] < newTarget)
{
front += 1;
}
else
{
back -= 1;
}
}
}
}
return solution;
}
}