321. Create Maximum Number

Difficulty: Hard

Frequency: N/A

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        vector<int> result;
        for (int i = max(0, k - m); i <= k && i <= n; i++) {
            vector<int> tmp = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if (greater(tmp, 0, result, 0)) result = tmp;
        }
        return result;
    }
    vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
        vector<int> result;
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            if (greater(nums1, i, nums2, j)) result.push_back(nums1[i++]);
            else result.push_back(nums2[j++]);
        }
        return result;
    }
    bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.size() || i < nums1.size() && nums1[i] > nums2[j];
    }
    vector<int> maxArray(vector<int> nums, int k) {
        int n = nums.size();
        vector<int> result(k, 0);
        for (int i = 0, j = 0; i < n; i++) {
            while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) j--;
            if (j < k) result[j++] = nums[i];
        }
        return result;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

Advertisements

253. (Locked)Meeting Rooms II

Difficulty: Medium

Frequency: N/A

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
bool myComp(const Interval &amp;a, const Interval &amp;b){
    return (a.start&lt;b.start);
}
class Solution {
public:
    int minMeetingRooms(vector<interval> intervals) {
        map<int, int> changes;
        for (auto i : intervals) {
            changes[i.start] += 1;
            changes[i.end] -= 1;
        }
        int rooms = 0, maxRooms = 0;
        for (auto change : changes) {
            maxRooms = max(maxRooms, rooms += change.second);
        }
        return maxRooms;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

135. Candy

Difficulty: Hard

Frequency: N/A

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?


 

My solution:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int result = 0;
        vector<int> candies(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) 
                candies[i] = candies[i + 1] + 1;
        }
        for (int n : candies) result += n;
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

316. Remove Duplicate Letters

Difficulty: Medium

Frequency: N/A

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    string removeDuplicateLetters(string s) {
        string result;
        int cnt[26] = {0};
        bool exists[26] = {false};
        for (char c : s) cnt[c - 'a']++;
        for (char c : s) {
            cnt[c - 'a']--;
            if (!exists[c - 'a']) {
                while (!result.empty() && c < result.back() && cnt[result.back() - 'a']) {
                    exists[result.back() - 'a'] = false;
                    result.pop_back();
                }
            }
            if (result.empty() || !exists[c - 'a']) {
                result += c;
                exists[c - 'a'] = true;
            }
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

330. Patching Array

Difficulty: Medium

Frequency: N/A

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long miss = 1, added = 0, i = 0;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                added++;
            }
        }
        return added;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

134. Gas Station

Difficulty: Medium

Frequency: N/A

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0, total = 0, tank = 0;
        for(int i = 0; i < gas.size(); i++) {
            if ((tank = tank + gas[i] - cost[i]) < 0) {
                start = i + 1;
                total += tank;
                tank = 0;
            }
        }
        return (total + tank < 0) ? -1 : start;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

045. Jump Game II

Difficulty: Hard

Frequency: N/A

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), start = 0, reach = 0, steps = 0;
        while (reach < n - 1) {
            int newReach = reach;
            for (int i = start; i <= reach; i++) {
                newReach = max(newReach, i + nums[i]);
            }
            if (newReach > reach) {
                start = reach;
                reach = newReach;
                steps++;
            } else return -1;
        }
        return steps;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: