697. Degree of an Array

 

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

 

Example 1:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

class Solution 
{
public:
    int findShortestSubArray(vector<int>& nums)
    {
        // map to store the frequencies
        unordered_map<int,int>m;
        
        // map to store the first and the last occurence of an element
        unordered_map<int,vector<int>>dict;
        
        // d is the degree of the array and ans is the answer
        int d=0,ans=INT_MAX;
        
        // populate the frequnecy map and calculate the degree
        for(int i=0;i<nums.size();i++)
        {
            m[nums[i]]++;
            d=max(d,m[nums[i]]);
        }
        
        // store the first occurence of the elements which has frequency=degree of the whole array
        for(int i=0;i<nums.size();i++)
        {
            if(m[nums[i]]==d)
            {
                if(dict.find(nums[i])==dict.end())
                {
                    dict[nums[i]].push_back(i);
                }
            }
        }
        
        // take the last occurence of the elements (having frequency=degree of the whole array) and calculate the length of a potential sub-array
        for(int i=nums.size()-1;i>=0;i--)
        {
            if(m[nums[i]]==d)
            {
                if(dict[nums[i]].size()==1)
                {
                    ans=min(ans,abs(i-dict[nums[i]][0])+1);
                    dict[nums[i]].push_back(i);
                }
            }
        }
        
        // finally return the answer
        return ans;
    }
};

Random Pick with Weight

 

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

• For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

 

Example 1:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

 

Constraints:

• 1 <= w.length <= 104
• 1 <= w[i] <= 105
• pickIndex will be called at most 104 times.

 

class Solution {
private:
    vector<int> sum;
public:
    Solution(vector<int>& w) {
        sum = w;
        for (int i = 1; i < w.size(); i++) {
            sum[i] = sum[i - 1] + w[i];
        }
    }
    
    int pickIndex() {
        int size = sum.size();
        int random = rand() % sum.back() + 1;  // range: 1 to sum[last]
        
        int st = 0, end = size - 1;
        while (st <= end) {
            int mid = st + (end - st)/2;
            if (sum[mid] == random) {
                return mid;
            } else if (sum[mid] < random) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return st;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

1592. Rearrange Spaces Between Words

 

You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

 

Example 1:

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Example 2:

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

 

Constraints:

• 1 <= text.length <= 100
• text consists of lowercase English letters and ' '.
• text contains at least one word.

 

 

class Solution {
public:
    string reorderSpaces(string text) {
        queue<string> q;
        int count = 0;
        string word;
        for (int i = 0; i < text.size(); i++) {
            if (text[i] == ' ') {
                count++;
                if (!word.empty()) {
                    q.push(word);
                }
                word = "";
            } else {
                word += text[i];
            }
        }
        if (!word.empty()) {
            q.push(word);
        }
       
        int word_size = q.size();
        string ans;
        if (word_size == 1) {
            ans = q.front(); q.pop();
            for (int i = 0; i < count; i++) {
                ans += " ";
            }
            return ans;
        }
       
        int space_count = count / (word_size - 1);
        int remaining_space = count % (word_size - 1);
       
        while (!q.empty()) {
            if (ans.empty()) {
                ans = q.front(); q.pop();
            } else {
                for (int i = 0; i < space_count; i++) {
                    ans += " ";
                }
                ans += q.front(); q.pop();
            }
        }
        for (int i = 0; i < remaining_space; i++) {
            ans += " ";
        }
        return ans;
    }
};

252. Meeting Rooms

 

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

 

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if (intervals.size() < 2) {
            return true;
        }
        sort(intervals.begin(), intervals.end(), [](auto &first, auto &second) {
            return first[0] < second[0];
        });
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

 

245. Shortest Word Distance III

 

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

 

Constraints:

• 1 <= wordsDict.length <= 105
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.

 

 

class Solution {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        if (wordsDict.size() == 0) {
            return 0;
        }
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < wordsDict.size(); i++) {
            mp[wordsDict[i]].push_back(i);
        }
        int ans = INT_MAX;
        if (word1 != word2) {
            int i = 0, j = 0;
            auto dist_vec1 = mp[word1];
            auto dist_vec2 = mp[word2];
            while (i < dist_vec1.size() && j < dist_vec2.size()) {
                ans = min(ans, abs(dist_vec1[i] - dist_vec2[j]));
                if (dist_vec1[i] <= dist_vec2[j]) {
                    i++;
                } else {
                    j++;
                }
            }
        } else {
            auto vec = mp[word1];
            if (vec.size() == 1) {
                return 0;
            }
            int i = 1;
            while (i < vec.size()) {
                ans = min(ans, vec[i] - vec[i - 1]);
                i++;
            }
        }
        return ans;
    }
};

243. Shortest Word Distance

 

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

 

Constraints:

• 2 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2
•  
•  

 

 

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        if (wordsDict.size() == 0) {
            return 0;
        }
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < wordsDict.size(); i++) {
            mp[wordsDict[i]].push_back(i);
        }
       
        int ans = INT_MAX, i = 0, j = 0;
        auto dist_vec1 = mp[word1];
        auto dist_vec2 = mp[word2];
        while (i < dist_vec1.size() && j < dist_vec2.size()) {
            ans = min(ans, abs(dist_vec1[i] - dist_vec2[j]));
            if (dist_vec1[i] <= dist_vec2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};


 

 

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;

    }

};