SDE - 1

class Solution {
public:
vector threeSum(vector& nums) {
int n = nums.size();
vector ans;
int lp, rp, rq;
sort(nums.begin(), nums.end());
for(int i = 0; i < (n -2); ++i){
if(i && nums[i] == nums[i-1]){
continue;
}
rq = -nums[i];
lp = i + 1;
rp = n - 1;
while(lp < rp){
if(nums[lp] + nums[rp] == rq){
vector v(3);
v[0] = nums[i]; v[1] = nums[lp]; v[2] = nums[rp];
ans.push_back(v);
lp++; rp--;
while(lp < rp && nums[lp] == nums[lp - 1]){
lp++;
}
while(rp > lp && nums[rp] == nums[rp + 1]){
rp--;
}
}
else if(nums[lp] + nums[rp] > rq){
rp--;
}
else{
lp++;
}
}
}
return ans;
}
};

public class Solution {
public bool IsValid(string s) {
Dictionary brackets = new Dictionary();
brackets.Add(')', '(');
brackets.Add('}', '{');
brackets.Add(']', '[');

Stack stack = new Stack();

for(int i = 0; i < s.Length; i++)
{
if(!brackets.ContainsKey(s[i]))
{
stack.Push(s[i]);
}
else
{
char topStack = stack.Count != 0 ? stack.Pop() : 'a';

if(topStack != brackets[s[i]])
{
return false;
}
}
}
return stack.Count == 0;
}
}

class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end()); //Reversing both strings (if you get this, then you got the code very well)
reverse(b.begin(), b.end());

if(a.size()>b.size()){ //These two conditions are for making both strings equal sized by adding '0' to smaller string
for(int i=b.size(); i b.push_back('0');
}
}
else if(a.size() for(int i=a.size(); i a.push_back('0');
}
}

string res; //Result string
char carry='0'; //Carry
for(int i=0; i if(a[i]=='1'&&b[i]=='1'){
res.push_back(carry);
carry='1';
}
else if((a[i]=='1' || b[i]=='1')){
if(carry=='1') res.push_back('0');
else res.push_back('1');
}
else{
res.push_back(carry);
if(carry=='1') carry='0';
}
}
if(carry=='1') res.push_back('1'); //if carry is present after looping, add it at the end (remember, we first reversed strings. So everything we need to add to the front, we will push back)

reverse(res.begin(), res.end()); //Reverse again to get the final string
return res; 
}
};

Sort intervals by beginning index. First we start with the laft most interval. After that for each interval we see if the beginning of the current left most interval. If not, we push the new interval and that becomes the left most interval. If the intervals overlap, we merge the currsent left most interval with the new interval. To do this, we pop the current left most interval. The lesft end point remains the same. The right end point is the max of the current interval and the current left most interval. Once the merge is done, we push back thge new interval and that becomes the new left most interval


class Solution {
// Need a custom comparator. For C++ use a static declarator. 
private:
static bool my_sort(const vector& x, const vector& y)
{
// Compare the first (left end point) of two vectors.
return x[0] < y[0];
}

public:
vector> merge(vector>& intervals) {

// First things, first. Sort the array by intervals.
std::sort(intervals.begin(),intervals.end(),my_sort);

// Second things second... Declare variables.
vector> sol;

vector tmp;

for(auto& v: intervals){ // Iterate through intervals. 
if(sol.size()<=0)
sol.push_back(v); // If soliution set is empty push back the interval.
else{
tmp = sol.back();
if(tmp[1] sol.push_back(v);
else{ // merge
sol.pop_back();
tmp[1]=max(v[1],tmp[1]);
sol.push_back(tmp);
}
}
}
return sol;
}
};

We can solve this question using Recursion.
We can start iterate over the array and we will doing partition. Partition would mean that we will be generating sub strings and checking if each of the sub string is palindrome or not. After every partition, every sub string which is palindrome is pushed into a new array.

void f(int ind, string& s,vector>& ans,vector&path){
if(ind==s.size()){
ans.push_back(path);
return;
}
for(int i=ind;i> partition(string s) {
vector>ans;
vectorpath;
f(0,s,ans,path);
return ans;
}
TC - O( (2^N) * average length * (N/2) )
Sc - O(average length * no. of combination)