The trick here is to name the state correctly, then let the implementation follow. For 645. Set Mismatch, the solution in this repository is mainly a bit manipulation solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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: bit manipulation, greedy.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findErrorNums, v, count.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- 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.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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(1)
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 144 ms, faster than 5.63% of C++ online submissions for Set Mismatch.
02//Memory Usage: 35.1 MB, less than 6.56% of C++ online submissions for Set Mismatch.
03
04class Solution {
05public:
06 vector<int> findErrorNums(vector<int>& nums) {
07 multiset<int> m1(nums.begin(), nums.end());
08 //if using iota, need to allocate memory for v beforehand
09 vector<int> v(nums.size());
10 iota(v.begin(), v.end(), 1);
11 //build a multiset containing 1~N
12 multiset<int> m2(v.begin(), v.end());
13
14 vector<int> ans(nums.size());
15 //find duplicate element first
16 vector<int>::iterator it = set_difference(m1.begin(), m1.end(), m2.begin(), m2.end(), ans.begin());
17 //and then find the missing element
18 it = set_difference(m2.begin(), m2.end(), m1.begin(), m1.end(), ans.begin()+1);
19 ans.resize(2);
20 return ans;
21 }
22};
23
24/**
25Approach 1: Brute Force
26check the occurence of 1~N in nums
27**/
28
29/**
30time complexity: O(n^2)
31space complexity: O(1)
32**/
33
34/**
35 class Solution {
36public:
37 vector<int> findErrorNums(vector<int>& nums) {
38 int dup = -1, missing = -1;
39 for(int i = 1; i <= nums.size(); i++){
40 //i from 1~N
41 //count the occurence of i in nums
42 int count = 0;
43 for(int n : nums){
44 if(n == i) count++;
45 }
46 if(count == 2) dup = i;
47 if(count == 0) missing = i;
48 }
49 return vector<int> {dup, missing};
50 }
51};
52**/
53
54/**
55Approach 2: Better brute Force
56early stop when we've found dup and missing
57**/
58
59/**
60time complexity: O(n^2)
61space complexity: O(1)
62**/
63
64/**
65class Solution {
66public:
67 vector<int> findErrorNums(vector<int>& nums) {
68 int dup = -1, missing = -1;
69 for(int i = 1; i <= nums.size(); i++){
70 //i from 1~N
71 //count the occurence of i in nums
72 int count = 0;
73 for(int n : nums){
74 if(n == i) count++;
75 }
76 if(count == 2) dup = i;
77 if(count == 0) missing = i;
78 if(dup > 0 && missing > 0) break;
79 }
80 return vector<int> {dup, missing};
81 }
82};
83**/
84
85/**
86Approach 3: Using Sorting
87sort and then scan to determine dup and missing
88note that there are two boundary conditions when detecting missing,
89so we need to initialize missing as 1 and do the following post-processing
90**/
91
92/**
93time complexity: O(nlogn) sorting
94space complexity: O(logn) used by sorting
95**/
96
97/**
98class Solution {
99public:
100 vector<int> findErrorNums(vector<int>& nums) {
101 sort(nums.begin(), nums.end());
102 int dup = -1, missing = 1;
103 for(int i = 1; i < nums.size(); i++){
104 if(nums[i] == nums[i-1]) dup = nums[i];
105 //this line can only detect missing when missing is not 1 or N
106 //[1,2,2,4]: 4>2+1
107 //[2,3,3,4,5,6]: 1 can't be detected as missing, so we initialize missing as 1
108 //[1,2,3,3]: 4 can't be detected as missing, so later we check if nums[nums.size()-1] equals to nums.size()
109 else if(nums[i] > nums[i-1]+1) missing = nums[i-1]+1;
110 }
111 return vector<int> {dup, nums[nums.size()-1] != nums.size() ? nums.size() : missing};
112 }
113};
114**/
115
116/**
117Approach 4: Using Map
118record the count of elements in nums in a map
119**/
120
121/**
122time complexity: O(n)
123space complexity: O(n)
124**/
125
126//Runtime: 148 ms, faster than 5.63% of C++ online submissions for Set Mismatch.
127//Memory Usage: 21.8 MB, less than 11.48% of C++ online submissions for Set Mismatch.
128
129/**class Solution {
130public:
131 vector<int> findErrorNums(vector<int>& nums) {
132 map<int, int> count;
133 int dup = -1, missing = -1;
134 for(int n : nums){
135 if(count.find(n) == count.end()){
136 count[n] = 1;
137 }else{
138 count[n]++;
139 }
140 }
141 for(int i = 1; i <= nums.size(); i++){
142 if(count.find(i) != count.end()){
143 if(count[i] == 2) dup = i;
144 }else{
145 missing = i;
146 }
147 }
148 return vector<int> {dup, missing};
149 }
150};
151**/
152
153/**
154Approach 5: Using Extra Array
155use array to replace map
156**/
157
158/**
159time complexity: O(n)
160space complexity: O(n)
161**/
162
163//Runtime: 40 ms, faster than 70.99% of C++ online submissions for Set Mismatch.
164//Memory Usage: 11.1 MB, less than 37.71% of C++ online submissions for Set Mismatch.
165
166/**
167class Solution {
168public:
169 vector<int> findErrorNums(vector<int>& nums) {
170 vector<int> count(nums.size()+1); //count[0] is useless here
171 int dup = -1, missing = -1;
172 for(int i = 0; i < nums.size(); i++){
173 count[nums[i]]++;
174 }
175 for(int i = 1; i < count.size(); i++){
176 if(count[i] == 0) missing = i;
177 else if(count[i] == 2) dup = i;
178 }
179 return vector<int> {dup, missing};
180 }
181};
182**/
183
184/**
185Approach 6: Using Constant Space
186don't maintain count anymore,
187mark a element as visited by invert the corresponding element in its (index-1)
188**/
189
190/**
191time complexity: O(n)
192space complexity: O(n)
193**/
194
195//Runtime: 36 ms, faster than 90.00% of C++ online submissions for Set Mismatch.
196//Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Set Mismatch.
197
198/**
199class Solution {
200public:
201 vector<int> findErrorNums(vector<int>& nums) {
202 int dup = -1, missing = -1;
203 for(int n : nums){
204 //if n is visited, the (n-1)th element of nums will be negative
205 if(nums[abs(n)-1] < 0) dup = abs(n);
206 else nums[abs(n)-1] *= -1;
207 }
208 for(int i = 0; i < nums.size(); i++){
209 //we use index n-1 to represent whether n is visited or not
210 if(nums[i] > 0) missing = i+1;
211 }
212 return vector<int> {dup, missing};
213 }
214};
215**/
216
217/**
218Approach 7: Using XOR
219?
220**/
221
222/**
223time complexity: O(n)
224space complexity: O(1)
225**/
226
227//Runtime: 40 ms, faster than 70.99% of C++ online submissions for Set Mismatch.
228//Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Set Mismatch.
229
230/**
231class Solution {
232public:
233 vector<int> findErrorNums(vector<int>& nums) {
234 int xorall = 0, xor0 = 0, xor1 = 0;
235 for(int n : nums) xorall ^= n;
236 for(int i = 1; i <= nums.size(); i++) xorall ^= i;
237 int rightmostbit = xorall & ~(xorall-1);
238 for(int n : nums){
239 if((n & rightmostbit) != 0){
240 xor1 ^= n;
241 }else{
242 xor0 ^= n;
243 }
244 }
245 for(int i = 1; i <=nums.size(); i++){
246 if((i & rightmostbit) != 0){
247 xor1 ^= i;
248 }else{
249 xor0 ^= i;
250 }
251 }
252 for(int i = 0; i < nums.size(); i++){
253 if(nums[i] == xor0){
254 return vector<int> {xor0, xor1};
255 }
256 }
257 return vector<int> {xor1, xor0};
258 }
259};
260**/Cost
Complexity
Time
O(n^2)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(1)
Auxiliary state plus the answer structure where the problem requires one.