1361. Validate Binary Tree Nodes

 You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

 

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

 

class Solution {

public:

    /*

    single tree: one root:   [one missing value in both of the lists] [otherwise false]

    single parent:    [If same value repeated ]

    no cycle:   [all the values appear means cycle]

    

    */

    

    

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {

        if (leftChild.size() != rightChild.size()) {

            return false;

        }

        vector<bool> dp(n, true);

        for (auto val : leftChild) {

            if (val != -1) {

                if (!dp[val]) {

                    return false;

                }

                dp[val] = false;

            }

        }

        for (auto val : rightChild) {

            if (val != -1) {

                if (!dp[val]) {

                    return false;

                }

                dp[val] = false;

            }

        }

        int root = -1;

        int count = 0;

        for (int i = 0; i < dp.size(); i++) {

            bool val = dp[i];

            if (val) {

                root = i;

                count++;

            }

        }

        if (count != 1) {

            return false;

        }

        if (!dfs(n, leftChild, rightChild, root)) {

            return false;

        }

        return true;

    }

    

    bool helper(int root, vector<int>& leftChild, vector<int>& rightChild,

                vector<int>& visited) {

        if (visited[root] == 1) {

            return false;

        }

        if (visited[root] == 2) {

            return true;

        }

        visited[root] = 1;

        if (leftChild[root] != -1) {

            if (!helper(leftChild[root], leftChild, rightChild, visited)) {

                return false;

            }

        }

        if (rightChild[root] != -1) {

            if (!helper(rightChild[root], leftChild, rightChild, visited)) {

                return false;

            }

        }

        visited[root] = 2;

        return true;

    }

    

    bool dfs(int n, vector<int>& leftChild, vector<int>& rightChild, int root) {

        vector<int> visited(n, 0);

        if (!helper(root, leftChild, rightChild, visited)) {

            return false;

        }

        for (auto val: visited) {

            if (val == 0) {

                return false;

            }

        }

        return true;

    }

};

791. Custom Sort String

 order and str are strings composed of lowercase letters. In order, no letter occurs more than once.

order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted. More specifically, if x occurs before y in order, then x should occur before y in the returned string.

Return any permutation of str (as a string) that satisfies this property.

Example:
Input: 
order = "cba"
str = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

 

Note:

• order has length at most 26, and no character is repeated in order.
• str has length at most 200.
• order and str consist of lowercase letters only.

class Solution {

public:

    

    string customSortString(string order, string str) {

        vector<int> str_map(26, 0);   // [1, 1, 1, 1, 0, 0 ..]

        for (auto ch : str) {

            str_map[ch - 'a']++;

        }

        // better to use map.

        

        string ans;

        for (auto ch : order) {

            while (str_map[ch - 'a'] > 0) {

                ans += string(1, ch);

                str_map[ch - 'a']--;

            }

        }

        

        for (int i = 0; i < 26; i++) {

            while (str_map[i] > 0) {

                ans += string(1, 'a' + i);

                str_map[i]--;

            }

        }

        return ans;

    }

};

stickers to spell word

 https://leetcode.com/problems/stickers-to-spell-word/discuss/740524/C%2B%2B-top-down-dp-solution

class Solution {
public:
    
    int n;
    vector<vector<int> > pre; //pre[i] stores the count of each character in word s[i]
    unordered_map<string, int> dp;
    
    int util(string target, vector<int>& t){
        if(target.size()==0)
            return 0;
        if(dp.find(target)!=dp.end())
            return dp[target];
        int flag=0, ans=2e9;
        for(int i=0; i<n; i++){
            vector<int> nt(26, 0);
            for(int j=0; j<26; j++)
                if(t[j]>0 && pre[i][j]>0)
                    nt[j]=max(0, t[j]-pre[i][j]);
                else
                    nt[j]=t[j];
            string nts="";
            for(int j=0; j<26; j++)
                for(int k=1; k<=nt[j]; k++)
                    nts+=(char)(j+'a');
            if(nts!=target){
                flag=1;
                ans=min(ans, 1+util(nts, nt));
            }
        }
        return dp[target]=ans;
    }
    
    int minStickers(vector<string>& s, string target) {
        n=s.size(), pre=vector<vector<int> >(n, vector<int>(26, 0));
        for(int i=0; i<n; i++)
            for(char ch: s[i])
                pre[i][ch-'a']++;
        vector<int> t(26, 0);
        for(char ch: target)
            t[ch-'a']++;
        int ans=util(target, t);
        if(ans>=2e9)
            return -1;
        else
            return ans;
    }
};

658. Find K Closest Elements

 Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

 

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

 

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 104
• arr is sorted in ascending order.
• -104 <= arr[i], x <= 104

class Solution {

public:

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {  // k = 4, x = 3

        if (k > arr.size() || arr.size() == 0) {

            return arr;

        }

        

        if (x < arr[0]) {

            return vector<int>(arr.begin(), arr.begin() + k);

        } else if (x > arr[arr.size() - 1]) {

            return vector<int>(arr.begin() + arr.size() -  k, arr.end());

        }

        

        // Matching case.

        int idx = upper_bound(arr.begin(), arr.end(), x) - arr.begin();  // idx = 2

        if (idx == arr.size()) {

            idx--;

        }

        vector<int> ans;

        if (arr[idx] == x) {

            // Matching and find k - 1 elements

            ans.push_back(x);

            find(arr, idx - 1, idx + 1, ans, k - 1, x);  // left, 1,  right = 3

        } else {

            // find k elements

            find(arr, idx - 1, idx, ans, k, x);

        }

        sort(ans.begin(), ans.end());

        return ans;

    }

    

    void find(vector<int>& arr, int left, int right, vector<int>& ans, int k, int x) {

        if (k == 0) {

            return;

        }

        

        while (left >= 0 || right < arr.size()) {

            int left_val = (left < 0 ? INT_MAX : x - arr[left]);

            int right_val = (right >= arr.size() ? INT_MAX : arr[right] - x);

            if (left_val <= right_val) {

                ans.push_back(arr[left]);

                left--;

            } else {

                ans.push_back(arr[right]);

                right++;

            }

            k--;

            if (k == 0) {

                return;

            }

        }

    }

};

======== Much better and efficient ======

vector<int> findClosestElements(vector<int>& arr, int k, int x) { int low=0; int high=arr.size()-1; while(high-low+1>k){ if(abs(arr[high]-x)>=abs(arr[low]-x)){ high--;} else low++; } return vector<int>(arr.begin()+low,arr.begin()+high+1); }