Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

 

Note: There are at least two nodes in this BST.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

vector<int> v;
void dfs(TreeNode *root)
{
    if (root == NULL)
        return;
    dfs(root->left);
    v.push_back(root->data);
    dfs(root->right);
}
int getMinimumDifference(TreeNode *root)
{
    int minimumDiff = INT_MAX;
    v.clear();
    dfs(root);
    for (int i = 1; i < v.size(); i++)
    {
        minimumDiff = min(minimumDiff, v[i] - v[i - 1]);
    }
    return minimumDiff;
}

int main()
{
    TreeNode *root = new TreeNode(1);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(2);

    cout << getMinimumDifference(root);

    return 0;
}

Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the modes (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

1.The left subtree of a node contains only nodes with keys less than or equal to the node's key.

2.The right subtree of a node contains only nodes with keys greater than or equal to the node's key.

3.Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

 

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Example:

Input:  tree[]=[1,null,2,2]
Output: [2]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
map<int, int> mp;
int max1 = INT_MIN;
void dfs(TreeNode *root)
{
    if (root == NULL)
        return;
    dfs(root->left);
    mp[root->data]++;
    max1 = max(max1, mp[root->data]);
    dfs(root->right);
}
vector<int> findMode(TreeNode *root)
{
    vector<int> res;
    mp.clear();
    dfs(root);
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        if (it->second == max1)
            res.push_back(it->first);
    }

    return res;
}

int main()
{
    TreeNode *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(2);
    vector<int> modes = findMode(root);

    cout << "[";

    for (int i = 0; i < modes.size(); i++)
    {
        cout << modes[i];
        if (i != modes.size() - 1)
            cout << ",";
    }
    cout << "]";

    return 0;
}

License Key Formatting

You are given a license key represented as a string S which consists of only alphanumeric characters and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example:

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

string licenseKeyFormatting(string S, int K)
{
    int n = S.size();
    string res = "";
    int cnt = 0;
    vector<char> v;
    for (int i = 0; i < n; i++)
        if (S[i] != '-')
            v.push_back(S[i]);
    if (v.size() == 0)
        return res;
    for (int i = 0; i < v.size(); i++)
        if (v[i] >= 'a' && v[i] <= 'z')
            v[i] = v[i] - 32;
    for (int i = v.size() - 1; i >= 0; i--)
    {
        res += v[i];
        cnt++;
        if (cnt == K)
        {
            cnt = 0;
            res += '-';
        }
    }
    if (res[res.size() - 1] == '-')
        res.erase(res.begin() + res.size() - 1);
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string S = "5F3Z-2e-9-w";
    int K = 4;

    cout << licenseKeyFormatting(S, K);

    return 0;
}

Number Complement

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

long long findComplement(long long n)
{
    long long binaryNum[32];
    long long i = 0;
    while (n > 0)
    {
        binaryNum[i] = n % 2;
        n = n / 2;
        i++;
    }
    for (long long j = i - 1; j >= 0; j--)
    {
        if (binaryNum[j] == 1)
            binaryNum[j] = 0;
        else
            binaryNum[j] = 1;
    }
    long long x = 1, res = 0;
    for (long long j = 0; j <= i - 1; j++)
    {
        res = res + binaryNum[j] * x;
        x = x * 2;
    }
    return res;
}

int main()
{
    int num = 5;

    cout << findComplement(num);

    return 0;
}

Minimum Moves to Equal Array Elements II

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

Example:

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int minMoves2(vector<int> &nums)
{
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int len = n / 2;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += abs(nums[i] - nums[len]);
    }
    return ans;
}

int main()
{
    vector<int> nums = {1, 2, 3};

    cout << minMoves2(nums);

    return 0;
}

Minimum Moves to Equal Array Elements

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 element by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

long long int minMoves(vector<int> &nums)
{
    long long int n = nums.size();
    long long int sum = 0;
    int min1 = INT_MAX;
    for (long long int i = 0; i < n; i++)
    {
        sum += nums[i];
        min1 = min(nums[i], min1);
    }
    return sum - n * min1;
}

int main()
{
    vector<int> nums = {1, 2, 3};

    cout << minMoves(nums);

    return 0;
}

Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of the array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findDisappearedNumbers(vector<int> &nums)
{
    sort(nums.begin(), nums.end());
    vector<int> res;
    set<int> st;
    for (int i = 0; i < nums.size(); i++)
        st.insert(nums[i]);
    for (int i = 1; i <= nums.size(); i++)
        if (st.find(i) == st.end())
            res.push_back(i);
    return res;
}

int main()
{
    vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};

    vector<int> res = findDisappearedNumbers(nums);

    cout << "[";
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i];
        if (i != res.size() - 1)
            cout << ", ";
    }
    cout << "]";

    return 0;
}

Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note: The input array will only contain 0 and 1.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int findMaxConsecutiveOnes(vector<int> &nums)
{
    int res = 0;
    int cnt = 0;
    int n = nums.size();
    if (n == 0)
        return res;
    int i = 0;
    while (i < n)
    {
        if (nums[i] == 1)
        {
            cnt++;
            i++;
        }
        else
        {
            res = max(res, cnt);
            i++;
            cnt = 0;
        }
    }
    res = max(res, cnt);
    return res;
}

int main()
{
    vector<int> nums = {1, 1, 0, 1, 1, 1};

    cout << findMaxConsecutiveOnes(nums);

    return 0;
}

Keyboard Row

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

In the American keyboard:

1.the first row consists of the characters "qwertyuiop",

2.the second row consists of the characters "asdfghjkl", and

3.the third row consists of the characters "zxcvbnm".

Example :

Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<string> findWords(vector<string> &words)
{
    set<char> st1, st2, st3;
    st1.insert('Q');
    st1.insert('W');
    st1.insert('E');
    st1.insert('R');
    st1.insert('T');
    st1.insert('Y');
    st1.insert('U');
    st1.insert('I');
    st1.insert('O');
    st1.insert('P');

    st1.insert('q');
    st1.insert('w');
    st1.insert('e');
    st1.insert('r');
    st1.insert('t');
    st1.insert('y');
    st1.insert('u');
    st1.insert('i');
    st1.insert('o');
    st1.insert('p');

    st2.insert('A');
    st2.insert('S');
    st2.insert('D');
    st2.insert('F');
    st2.insert('G');
    st2.insert('H');
    st2.insert('J');
    st2.insert('K');
    st2.insert('L');

    st2.insert('a');
    st2.insert('s');
    st2.insert('d');
    st2.insert('f');
    st2.insert('g');
    st2.insert('h');
    st2.insert('j');
    st2.insert('k');
    st2.insert('l');

    st3.insert('Z');
    st3.insert('X');
    st3.insert('C');
    st3.insert('V');
    st3.insert('B');
    st3.insert('N');
    st3.insert('M');

    st3.insert('z');
    st3.insert('x');
    st3.insert('c');
    st3.insert('v');
    st3.insert('b');
    st3.insert('n');
    st3.insert('m');
    vector<string> res;
    for (int i = 0; i < words.size(); i++)
    {
        bool one = false, two = false, three = false;
        for (int j = 0; j < words[i].size(); j++)
        {
            if (st1.find(words[i][j]) != st1.end())
                one = true;
            else if (st2.find(words[i][j]) != st2.end())
                two = true;
            else
                three = true;
        }
        if (one == true && two == false && three == false)
            res.push_back(words[i]);
        else if (one == false && two == true && three == false)
            res.push_back(words[i]);
        else if (one == false && two == false && three == true)
            res.push_back(words[i]);
    }
    return res;
}

int main()
{
    vector<string> words = {"Hello", "Alaska", "Dad", "Peace"};

    vector<string> res = findWords(words);

    cout << "[";
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i];
        if (i != res.size() - 1)
            cout << ",";
    }
    cout << "]";

    return 0;
}