bool customEqualsFunction (const obj a, const obj b)
{
    /// implementation here
}

bool cmp (const obj a, const obj b)
{
    // implementation here
}


std::next_permuation(something.begin(), something.end(), &customEqualsFunction)
    modifies something to the next available permutation
    returns true if there is a permutatin greater than the last one, false if not
    worst case : last-first / 2 swaps
    avg: 3 comparisions and 1.5 swaps per call


std::is_permutation (required.begin(),required.end(),sample.begin(), &customEqualsFunction)
    yes, just the beginning of the text to be compared to is required



sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs )
{
    return <do comparision here>
});


intersection points of two rectangles:
    int x5 = max(x1, x3);
    int y5 = max(y1, y3);
    int x6 = min(x2, x4);
    int y6 = min(y2, y4);

    where x1y1 x2y2 are bottom left and top right resply for the first rectangle


unordered_set:
    find(key)
        returns an iterator to the element or returns an end iterator
            set.find(something) != set.end() => means the element exists
        O(constant) average
    count(key)
        returns number of elements with required key
            kind of useless because unordered set does not allowe duplicates so the only possible answers are 0 and 1

    so instead of using set.find(key) != set.end() for comparision, you can use if(set.count(key)) which is the same thing



https://leetcode.com/problems/flood-fill/

    floodfill ( r, c, color) {
        adj_values = {all the adjacent values}
        for ( auto i : adj_values )
        {
            if ( i is within bounds )
            {
                floodfill(i.x, i.y, color)
            }
        }

        this.color = color;
    }



subarray with given sum:
                    int subArraySum(int arr[], int n, int sum)
                {
                    int curr_sum = arr[0], start = 0, i;

                    for (i = 1; i <= n; i++)
                    {
                        while (curr_sum > sum && start < i-1)
                        {
                            curr_sum = curr_sum - arr[start];
                            start++;
                        }

                        if (curr_sum == sum)
                        {
                            printf ("Sum found between indexes %d and %d", start, i-1);
                            return 1;
                        }

                        if (i < n)
                        curr_sum = curr_sum + arr[i];
                    }

                    printf("No subarray found");
                    return 0;
                }
    the logic here is to assign the first element as cur, and keep adding elements to it by iterating over the array
    if cur exceeds sum, then start a while loop which runs while cur > sum, and while it is, remove the elements from the back side
    keep track of which element from the back youve removed so far by using a variable called start which tells you where the start of the current summed up sub array is


pairs with given sum:
    unordered_set set1(vec1.begin(),vec1.end())
    unordered_set set2(vec2.begin(),vec2.end())

    for ( auto i : set1 )
    {
        if ( set2.count(sum-i) )
        {
            cout << i << sum-i
        }
    }

std::lower_bound(vec.begin(), vec.end(), value, comparisionFunction) returns first element that is greater than value
std::uper_bound(vec.begin(),vec.end(),value, comparisionFunction) returns first element that is lesser than value

unordered_set uses hashing to store the keys in no particular order, only unique keys
set does not use hashing, keys are stored in ascending order, only unique keys
multiset does not using hashing, keys are stored in ascending order, duplicate keys allowed


iterating over a set/multiset/unordered_set
for (std::multiset<T>::const_iterator i(mlt.begin()), end(mlt.end()); i != end; ++i)
    std::cout << *i << "\n";

find median of a stream of integers as they arrive:

    std::multiset<int> stream;
    int middle;

    int x;
    int n;
    while ( cin >> x )
    {
        stream.insert(x);
        n = n + 1;

        std::multiset<int>::const_iterator it(stream.begin());
        if ( n%2 == 0)
        {
            calcs
        } else {
            calcs
        }
    }


minimum depth in a tree:

    int minimum(node* root, int level)
    {
        if ( root == null )
        {
            return level
        }
        level++;

        return min(minimum(root.lefbool startsWith(string given, string searchTerm) {
  return (given.rfind(searchTerm, 0) == 0);
}
t,level),(root.right,level))
    }

program to multiply two integers stored as large integers :

    string multiply ( string s1, string s2)
    {
        std::reverse(s1.begin(), s1.end())
        std::reverse(s2.begin(), s2.end())
        vector<string> levels;

        for ( auto j : s2)
        {
            stringstream ss;
            int multiplier = j - '0'
            int carry = 0 ;
            for ( auto i : s1 )
            {
                int thisnumber = multiplier * (int)(i - '0');
                if ( carry != 0 )
                {
                    thisnumber += carry
                    carry = 0
                }

                if ( thisnumber > 9 )
                {
                    carry = thisnumber/10;
                    thisnumber = thisnumber%10
                }

                ss << thisnumber%10;
            }

            if ( carry != 0 )
            {
                ss << carry
            }
            string str = ss.str();
            std::reverse(str);
            levels.push_back(str)
            ss.str("");
            ss.clear();
        }

        vector<string> tobeadded
        for (int i = 0 ; i < levels.size(); ++i)
        {
            stringstream ss;
            ss << levels[i]

            for ( int j = 0 ; j < i ; ++j)
            {
                ss << '0'
            }
            string sth = ss.str();
            std::reverse(sth.begin(),sth.end())
            tobeadded.push_back(sth);
        }

        int i = 0 ;
        int max = s1.size() + s2.size()
        int carry = 0 ;
        stringstream final;
        while(i < max )
        {
            int tempsum = 0 ;

            for ( auto j : tobeadded )
            {
                tempsum += (int)(j[i]-'0')
            }

            tempsum += carry
            carry = 0

            if ( tempsum > 9 )
            {
                carry = tempsum/10
                tempsum = tempsum%10
            }

            final << tempsum%10
            i++;

        }

        string answer = final.str();
        std::reverse(answer.begin(),answer.end());
    }




gcd of two numbers:
    recursive solution, euclidean algorithm:

    int func( int a , int b )
    {
        if b == 0
            return a
        return gcd( b, a%b )
    }

sorting elements of a map by value using a vector:

    map<T,T> freq;
    vector<std::pair<T,T>> vec;
    for ( auto &it = freq.begin(), it != freq.end(), it++)
    {
        vec.push_back(*it)
    }

    std::sort(vec.begin(),vec.end(), [](std::pair<T,T> lhs, std::pair<T,T> rhs) {
        return lhs.second > rhs.second;
    });

    //OR JUST USE A MULTIMAP


Multimaps:
    multimaps store in ascending order of keys
    duplicate keys are allowed
        if there are duplicate keys then the they are stored in ascending order of the values
    to access elements in multimaps, you will have to use m.find(key) which will return an iterator to the pair, so dereference it like this (*x).first or whatever

integer to binary :
    std::string binary = std::bitset<8>(128).to_string();

stepping number:
    Given N and M find all stepping numbers in range N to M


                vector<int> Ans;
                void dfs(int len, int N, int M, int num = 0) {
                    if(num >= N && num <= M) {
                            Ans.push_back(num);
                    }
                    if(len == 0)
                        return;


                    if(num == 0) {
                        for(int i = 1; i <= 9; ++i) {
                            dfs(len - 1, N, M, i);
                        }
                        return;
                    }

                    int last_dig = num%10;
                    if(last_dig == 0) {

                        dfs(len - 1, N, M, (num * 10) + (last_dig + 1));

                    } else if(last_dig == 9) {

                        dfs(len - 1, N, M, (num * 10) + (last_dig - 1));

                    } else {
                        dfs(len - 1, N, M, (num * 10) + (last_dig - 1));
                        dfs(len - 1, N, M, (num * 10) + (last_dig + 1));
                    }
                }

                vector<int> stepnum(int N, int M) {
                    int len = 0;
                    int temp = M;
                    while(temp) {
                        temp /= 10;
                        len++;
                    }

                    Ans.clear();
                    dfs(len, N, M);
                    sort(Ans.begin(), Ans.end());
                    return Ans;
                }

putting horses into K stables such that the product of black and white horses is minimum

            vector<vector<int> > dp;

            int rec(int start, int stables, string str, int K) {
                int N = str.size();
                if(start == N) {
                    if(stables == K)
                            return 0;
                    return INT_MAX;
                }

                if(stables == K)
                        return INT_MAX;

                if(dp[start][stables] != -1)
                        return dp[start][stables];

                int W = 0;
                int B = 0;
                int ans = INT_MAX;

                for(int i = start; i < N; ++i) {
                    W += str[i] == 'W';
                    B += str[i] == 'B';
                    if (W * B > ans) break;
                    int Temp = rec(i + 1, stables + 1, str, K);
                    if(Temp != INT_MAX) {
                        ans = min(ans, Temp + (W * B));
                    }
                }

                return dp[start][stables] =  ans;
            }

            int arrange(string str, int K) {
                int N = str.size();
                dp.clear();
                dp.resize(N, vector<int>(K, -1));

                int ans = rec(0, 0, str, K);
                return ans == INT_MAX ? -1 : ans;
            }

divide an array into two parts such that the average of both the parts is the same (subarrays)
        Lets try to simplify the problem.
        Lets assume the two sets are set1 and set2.
        Assume sum of set1 = Sum_of_Set1, with size = size_of_set1.
        Assume sum of set2 = Sum_of_Set2, with size = size_of_set2

            SUM_of_Set1 / size_of_set1 = SUM_of_Set2 / size_of_set2
            SUM_of_Set1 = SUM_of_Set2 * (size_of_set1 / size_of_set2)

            total_sum = Sum_of_Set1 + Sum_of_Set2
            AND size_of_set2 = total_size - size_of_set1

            Sum_of_Set1 = (total_sum - Sum_of_Set1) * (size_of_set1 / (total_size - size_of_set1))
            OR on simplifying,

            total_sum / Sum_of_Set1 - 1 = (total_size - size_of_set1) / size_of_set1
            total_sum / Sum_of_Set1 = total_size / size_of_set1
            Sum_of_Set1 / size_of_set1 = total_sum / total_size


                        vector<vector<vector<bool> > > dp;
                        vector<int> res;
                        vector<int> original;
                        int total_size;

                        bool possible(int index, int sum, int sz) {
                            if (sz == 0) return (sum == 0);
                            if (index >= total_size) return false;

                            if (dp[index][sum][sz] == false) return false;

                            if (sum >= original[index]) {
                                res.push_back(original[index]);
                                if (possible(index + 1, sum - original[index], sz - 1)) return true;
                                res.pop_back();
                            }

                            if (possible(index + 1, sum, sz)) return true;

                            return dp[index][sum][sz] = false;
                        }

                        vector<vector<int> > avgset(vector<int> &Vec) {

                            sort(Vec.begin(), Vec.end());
                            original.clear();
                            original = Vec;
                            dp.clear();
                            res.clear();

                            int total_sum = 0;
                            total_size = Vec.size();

                            for(int i = 0; i < total_size; ++i)
                                total_sum += Vec[i];

                            dp.resize(original.size(), vector<vector<bool> > (total_sum + 1, vector<bool> (total_size, true)));

                            // We need to minimize size_of_set1. So, lets search for the first size_of_set1 which is possible.
                            for (int i = 1; i < total_size; i++) {
                                // Sum_of_Set1 has to be an integer
                                if ((total_sum * i) % total_size != 0) continue;
                                int Sum_of_Set1 = (total_sum * i) / total_size;
                                if (possible(0, Sum_of_Set1, i)) {

                                    // Ok. Lets find out the elements in Vec, not in res, and return the result.
                                    int ptr1 = 0, ptr2 = 0;
                                    vector<int> res1 = res;
                                    vector<int> res2;
                                    while (ptr1 < Vec.size() || ptr2 < res.size()) {
                                        if (ptr2 < res.size() && res[ptr2] == Vec[ptr1]) {
                                            ptr1++;
                                            ptr2++;
                                            continue;
                                        }
                                        res2.push_back(Vec[ptr1]);
                                        ptr1++;
                                    }

                                    vector<vector<int> > ans;
                                    ans.push_back(res1);
                                    ans.push_back(res2);
                                    return ans;
                                }
                            }
                            // Not possible.
                            vector<vector<int> > ans;
                            return ans;
                        }


bfs traversal of tree:
    q.add(root)
    while ( q not empty )
    {
        head = q.pop()
        head.visited = true
        cout << head

            for ( auto i : head.adjacent or for auto i : head.children)
            {
                q.add(i)
            }

        OR

            if head.left != NULL : q.add(head.left)
            if head.right != NULL : q.add(head.right)
    }


dfs traversal of tree: (pre order)

    dfs(root):
        root.visited = true;
        cout << root
            for ( auto i : root.adjacent )
            {
                if i.visited == false:
                    dfs(i)
            }

        OR

            if ( root.left != null )
                dfs(root.left)
            if ( root.right != null )
                dfs(root.right)


creating a binary tree from an array

    node* driverFunction(int[] arr, int n)
    {
        node* root = helperFunction(arr,n,0,root)
        return root
    }

    node* helperFunction( int[] arr, int i, int n, node* root)
    {
        if ( i < n )
        {
            node* temp = node(arr[i])
            root = temp

            root->left = helperFunction(arr,2i+1,n,root->left)
            root->right = helperFunction(arr,2i+2,n, root->right)
        }

        return root
    }

merge sort:
                void Merge(int *a, int low, int high, int mid)
                {
                    // We have low to mid and mid+1 to high already sorted.
                    int i, j, k, temp[high-low+1];
                    i = low;
                    k = 0;
                    j = mid + 1;

                    // Merge the two parts into temp[].
                    while (i <= mid && j <= high)
                    {
                        if (a[i] < a[j])
                        {
                            temp[k] = a[i];
                            k++;
                            i++;
                        }
                        else
                        {
                            temp[k] = a[j];
                            k++;
                            j++;
                        }
                    }

                    // Insert all the remaining values from i to mid into temp[].
                    while (i <= mid)
                    {
                        temp[k] = a[i];
                        k++;
                        i++;
                    }

                    // Insert all the remaining values from j to high into temp[].
                    while (j <= high)
                    {
                        temp[k] = a[j];
                        k++;
                        j++;
                    }


                    // Assign sorted data stored in temp[] to a[].
                    for (i = low; i <= high; i++)
                    {
                        a[i] = temp[i-low];
                    }
                }

                // A function to split array into two parts.
                void MergeSort(int *a, int low, int high)
                {
                    int mid;
                    if (low < high)
                    {
                        mid=(low+high)/2;
                        // Split the data into two half.
                        MergeSort(a, low, mid);
                        MergeSort(a, mid+1, high);

                        // Merge them to get sorted output.
                        Merge(a, low, high, mid);
                    }
                }


swapping two numbers with xor:
    x,y
        x = x xor y
        y = y xor x
        x = x xor y


bool startsWith(string given, string searchTerm) {
  return (given.rfind(searchTerm, 0) == 0);
}



LRU CACHE implementation
                    class entry {
                        int key ;
                        int value ;
                        entry left;
                        entry right;
                    };


                    unordered_map<int,entry> map;
                    entry start, end;


                    int size = // variable size  ;

                    void addAtTop (Entry node) {
                        node.right = start;
                        node.left = null

                        if ( start != null ) {
                            start.left = node
                        }

                        start = node

                        if ( end == null ) {
                            end = start
                        }

                    }

                    void removeNode(Entry node) {
                        if ( node.left != null ) {
                            node.left.right = node.right
                        } else {
                            start = node.right
                        }

                        if ( node.right != null ) {
                            node.right.left = node.left
                        } else {
                            end = node.left
                        }
                    }

                    int getValue ( int key ) {
                        if ( map.contains(key)) {
                            entry e = map.get(key);
                            removeNode(e)
                            addAtTop(e)
                            return entry.value
                        }
                    }

                    void addEntry ( int key, int value ) {
                        if (map.contains(key)) {
                            Entry e = map.get(key)
                            e.value = value
                            addAtTop(e);
                        } else {
                            entry newnode;
                            newnode.left = null
                            newnode.right = null
                            newnode.key = key ;
                            newnode.value = value
                            if ( map.size() > size ) {
                                map.remove(end.key)
                                removeNode(end)
                                addAtTop(newnode)
                            } else {
                                addAtTop(newnode)
                            }

                            map.put(key,newnode)
                        }
                    }

                    int lookup_entry(int key) { // key of the entry
                        if map.contains(key) { // key is found in cache
                            entry e = map.get(key);

                        }

                    }

to check if there are overlapping times in a list of given time intervals

                bool isThereAnOverlap(vector<pair<int,int>> listOfTimes) {

                    std::sort(listOfTimes.begin(),listOfTimes.end(), [] ( const auto &lhs, const auto&rhs) {
                        return lhs.first <= rhs.first;
                    });


                    for ( auto i : listOfTimes) {
                        cout << i.first << " " << i.second ;
                    }
                    std::vector<pair<int,int>>::iterator i;

                    bool truth = false;
                    for (i = listOfTimes.begin(); i < listOfTimes.end()-1 ; i++) {

                        auto p1 = *i ;

                        auto p2 = *(i+1);
                        // 12 26

                        if ( p1.second > p2.first ) {
                            truth = true;
                            break;
                        }

                    }

                    return truth;

                }