I think AC is the abbreviation of ACCEPTED. It weird at the beginning though.
kun3
@kun3
Posts made by kun3

RE: Share my clean AC C++ solution, with explanation.

RE: Share my clean AC C++ solution, with explanation.
Thank you for your comment. However after 4 times of
pop
, the stack should be[7, 8]
. Because before the 4thpop
, the currenttop
of the stack and the min stack are both4
, which should all be poped. 
RE: Share my clean AC C++ solution, with explanation.
Thank you for your comment. In my opinion, using 2 stacks will reduce the usage of space. For example, say a stack with
N
elements, and the minimum is the first element pushed onto the stack. Then your method will have to pushN
duplicates of the minimum, which is not necessary here. You don't need to store the minimum every time since it's not updated. 
C++ AC solution, with explanations and comments.
This idea is to find the the intervals with continuous discrete numbers like
[1, 2, 3]
or[7, 8, 9]
in[1, 2, 3, 7, 8, 9]
. And then we can summarize the interval with the begin number and the end number. This problem is somehow liketruncate the words from one string
orfind the length of the Nth word in a sentence
.Here is the algorithm:
 Set
bgn
to the current index iteratori
.  While
nums[i + 1] == nums[i]
theni++
;  If
i != bgn
which means we have more then one element in this sub interval, otherwise, we have a oneelement interval.
Code:
vector<string> summaryRanges(vector<int>& nums) { vector<string> res; if (nums.empty()) return res; int i = 0; while (i < nums.size()) { int bgn = i; while (i + 1 < nums.size() and nums[i + 1] == nums[i] + 1) i++; if (bgn != i) { stringstream ss; ss << nums[bgn] << ">" << nums[i]; res.push_back(ss.str()); } else { res.push_back(std::to_string(nums[bgn])); } i++; } return res; }
 Set

Iterative and recursive version in C++, easy to understand and with explanations
Recursive Version
Recursive version is rather simply and I think no further explanation is needed but showing the code.
void ConvertHelper(TreeNode* root) { if (root) { swap(root>left, root>right); ConvertHelper(root>left); ConvertHelper(root>right); } } TreeNode* invertTree(TreeNode* root) { ConvertHelper(root); return root; }
Iterative Version
Here I've used a Preorder Traversal to traverse the tree (same idea if you prefer Inorder, but you'll need to modify the code a little bit). First you construct a
stack
to storeTreeNode*
s and pop out one at a time to process it. if the stack is empty, which means even the upmost root node and its right node is processed, then we can safely jump out of the loop. The only point is that when we've done theswap
, we were supposed to dot = t>right
, but here since we've swapped the left and the right node, theright
should be currently theleft
node.TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; stack<TreeNode*> s; TreeNode *t = root; while(true) { while (t) { s.push(t); t = t>left; } if (s.empty()) break; t = s.top(); s.pop(); swap(t>left, t>right); t = t>left; } return root; }

Few lines of C++ recursive version, easy to understand.
The code is selfexplanatory.
class Solution { public: TreeNode* Convert(const vector<int>& nums, int lo, int hi) { if (lo > hi) return NULL; int mid = (lo + hi) / 2; TreeNode *t = new TreeNode(nums[mid]); t>left = Convert(nums, lo, mid  1); t>right = Convert(nums, mid + 1, hi); return t; } TreeNode* sortedArrayToBST(vector<int>& nums) { return Convert(nums, 0, nums.size()  1); } };

RE: 4Sum C++ solution with explanation and comparison with 3Sum problem. Easy to understand.
That's true. Nevertheless, I do remember that at somewhere I've read about the rigorous proof about this problem of which the result is bounded by
O(m^n)
, whereM
is the size of the array andn
is the same number as then
innth sum problem
. Correct me if I'm wrong. 
RE: Share my AC C++ solution, around 50ms, O(N*N), with explanation and comments
Thank you for your comment. The
rear
word just came out of my mind beforeback
at that time, and they have almost the same meaning. But anyway, thank you for pointing that out. 
RE: C++ solution, easy to understand with explanations.
@suleman, I don't know the part
ListNode *newhead = new ListNode
in your comment is a typo or not. If it's not, then please have a look at the C++ syntax ofnew
.new
calls theconstructor
function. The good thing about using a static temp variable is that you don't have to manully release the dynamically allocated memory. 
4Sum C++ solution with explanation and comparison with 3Sum problem. Easy to understand.
For the reference, please have a look at my explanation of
3Sum
problem because the algorithm are exactly the same. The link is as blow.The key idea is to downgrade the problem to a
2Sum
problem eventually. And the same algorithm can be expand toNSum
problem.After you had a look at my explanation of
3Sum
, the code below will be extremely easy to understand.class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > res; if (num.empty()) return res; std::sort(num.begin(),num.end()); for (int i = 0; i < num.size(); i++) { int target_3 = target  num[i]; for (int j = i + 1; j < num.size(); j++) { int target_2 = target_3  num[j]; int front = j + 1; int back = num.size()  1; while(front < back) { int two_sum = num[front] + num[back]; if (two_sum < target_2) front++; else if (two_sum > target_2) back; else { vector<int> quadruplet(4, 0); quadruplet[0] = num[i]; quadruplet[1] = num[j]; quadruplet[2] = num[front]; quadruplet[3] = num[back]; res.push_back(quadruplet); // Processing the duplicates of number 3 while (front < back && num[front] == quadruplet[2]) ++front; // Processing the duplicates of number 4 while (front < back && num[back] == quadruplet[3]) back; } } // Processing the duplicates of number 2 while(j + 1 < num.size() && num[j + 1] == num[j]) ++j; } // Processing the duplicates of number 1 while (i + 1 < num.size() && num[i + 1] == num[i]) ++i; } return res; } };