This problem looks busy at first, but the accepted solution is built around one steady invariant. For 454. 4Sum II, the solution in this repository is mainly a two pointers solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- https://leetcode.com/problems/4sum-ii/discuss/93917/Easy-2-lines-O(N2)-Python
- time: O(N^2), space: O(N^2)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are fourSumCount, biSearch.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N^2), space: O(N^2)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://leetcode.com/problems/4sum-ii/discuss/93917/Easy-2-lines-O(N2)-Python
02//Runtime: 464 ms, faster than 10.57% of C++ online submissions for 4Sum II.
03//Memory Usage: 49.8 MB, less than 9.09% of C++ online submissions for 4Sum II.
04//time: O(N^2), space: O(N^2)
05class Solution {
06public:
07 int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
08 map<int, int> ABSumCounter, CDSumCounter;
09
10 for(int a : A){
11 for(int b : B){
12 ABSumCounter[a+b] += 1;
13 }
14 }
15
16 for(int c : C){
17 for(int d : D){
18 CDSumCounter[c+d] += 1;
19 }
20 }
21
22 int ans = 0;
23
24 for(auto abit = ABSumCounter.begin(); abit != ABSumCounter.end(); abit++){
25 auto cdit = CDSumCounter.find(-abit->first);
26 if(cdit != CDSumCounter.end()){
27 //we are finding +`++combination, so use product
28 ans += (abit->second * cdit->second);
29 }
30 }
31
32 return ans;
33 }
34};
35
36//vector and find
37//TLE
38class Solution {
39public:
40 int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
41 vector<int> abSum, cdSum;
42 int N = A.size();
43
44 for(int i = 0; i < N; i++){
45 for(int j = 0; j < N; j++){
46 abSum.push_back(A[i] + B[j]);
47 }
48 }
49
50 for(int i = 0; i < N; i++){
51 for(int j = 0; j < N; j++){
52 cdSum.push_back(C[i] + D[j]);
53 }
54 }
55
56 sort(abSum.begin(), abSum.end());
57 sort(cdSum.begin(), cdSum.end());
58
59// for(int e : abSum){
60// cout << e << " ";
61// }
62// cout << endl;
63
64// for(int e : cdSum){
65// cout << e << " ";
66// }
67// cout << endl;
68
69 int ans = 0, curCount;
70 for(int i = 0; i < abSum.size(); i++){
71 if(i > 0 && abSum[i] == abSum[i-1]){
72 // cout << i << " add last curCount" << endl;
73 ans += curCount;
74 continue;
75 }
76 // cout << "finding " << -abSum[i] << endl;
77 auto leftIt = find(cdSum.begin(), cdSum.end(), -abSum[i]);
78 if(leftIt != cdSum.end()){
79 auto rightIt = find(cdSum.rbegin(), cdSum.rend(), -abSum[i]);
80 int left = leftIt - cdSum.begin();
81 int right = cdSum.rend() - rightIt - 1;
82 curCount = right-left+1;
83 // cout << left << " " << right << " " << curCount << endl;
84 ans += curCount;
85 }else{
86 curCount = 0;
87 }
88 }
89
90 return ans;
91 }
92};
93
94//Binary search
95//https://leetcode.com/problems/4sum-ii/discuss/93923/How-to-use-Binary-Search-with-%224Sum-II%22
96//Runtime: 256 ms, faster than 47.71% of C++ online submissions for 4Sum II.
97//Memory Usage: 24.7 MB, less than 95.45% of C++ online submissions for 4Sum II.
98class Solution {
99public:
100 int biSearch(vector<int> & nums, int x, bool LEFT) {
101 //if not found return 0 when LEFT, return -1 when not LEFT
102 int l = 0, r = nums.size()-1, m;
103 // cout << "finding " << x << ", left? " << LEFT << endl;
104 while (l <= r) {
105 m = (l+r) / 2;
106 // cout << l << " " << m << " " << r << " " << endl;
107 //if r = l + 1, then m = l
108 if (LEFT) {
109 /*
110 in the situation of there are multiple x in nums:
111 finding 0 in the array -1 0 0 1
112 0 1 3
113 0 0 0
114 if LEFT, we only care left bound
115 if nums[m] == x
116 we will set r = m-1, so r will equal to l,
117 in next iteration, we will set l = m+1 which becomes original m,
118 then break the loop and return l
119 */
120 if (nums[m] >= x) r = m - 1;
121 else l = m + 1;
122 }
123 else {
124 /*
125 in the situation of there are multiple x in nums:
126 finding 0 in the array -1 0 0 1
127 0 1 3
128 2 2 3
129 3 3 3
130 if not LEFT, we only care right bound
131 if nums[m]== x
132 we will set l = m+1, so l will equal to r
133 in next iteration, we will set r = m-1 which becomes original m,
134 then break the loop and return r
135 */
136 if (nums[m] <= x) l = m + 1;
137 else r = m - 1;
138 }
139 }
140 // cout << "found at " << (LEFT?l:r) << endl;
141 return LEFT?l:r;
142 }
143
144 int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
145 vector<int> abSum, cdSum;
146 int N = A.size();
147
148 for(int i = 0; i < N; i++){
149 for(int j = 0; j < N; j++){
150 abSum.push_back(A[i] + B[j]);
151 cdSum.push_back(C[i] + D[j]);
152 }
153 }
154
155 sort(abSum.begin(), abSum.end());
156 sort(cdSum.begin(), cdSum.end());
157
158// for(int e : abSum){
159// cout << e << " ";
160// }
161// cout << endl;
162
163// for(int e : cdSum){
164// cout << e << " ";
165// }
166// cout << endl;
167
168 int ans = 0, curCount;
169 for(int i = 0; i < abSum.size(); i++){
170 if(i > 0 && abSum[i] == abSum[i-1]){
171 // cout << i << " add last curCount" << endl;
172 ans += curCount;
173 continue;
174 }
175 curCount = biSearch(cdSum, -abSum[i], false) -
176 biSearch(cdSum, -abSum[i], true) + 1;
177 ans += curCount;
178 }
179
180 return ans;
181 }
182};Cost
Complexity
Time
O(N^2), space: O(N^2)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.