164. Maximum Gap

Difficulty: Hard

Frequency: N/A

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector countSort(vector& nums, int w) {
        vector counts(11, 0);
        for (int n : nums) {
            int v = n / w % 10;
            counts[v + 1]++;
        }
        for (int i = 1; i <= 10; i++) counts[i] += counts[i - 1];
        vector results(nums.size(), 0);
        for (int n : nums) {
            int v = n / w % 10;
            results[counts[v]++] = n;
        }
        return results;
    }
    void radixSort(vector& nums) {
        int max_n = 0;
        for (int n : nums) max_n = max(max_n, n);
        int w = 1;
        while (w <= max_n) {
            nums = countSort(nums, w);
            w *= 10;
        }
    }
    int maximumGap(vector& nums) {
        radixSort(nums);
        int gap = 0, n = nums.size();
        for (int i = 1; i < n; i++) {
            gap = max(gap, nums[i] - nums[i - 1]);
        }
        return gap;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

057. Insert Interval

Difficulty: Hard

Frequency: N/A

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> results;
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), compare);
        int i = 0, n = intervals.size();
        while (i < n) {
            int j = i + 1;
            while (j < n && intervals[i].end >= intervals[j].start) {
                intervals[i].end = max(intervals[i].end, intervals[j].end);
                j++;
            }
            results.push_back(intervals[i]);
            i = j;
        }
        return results;
    }
    static bool compare(Interval& i1, Interval& i2) {
        return i1.start < i2.start;
    }
};

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

Things to learn:

056. Merge Intervals

Difficulty: Hard

Frequency: N/A

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<Interval> results;
        int i = 0, n = intervals.size();
        while (i < n) {
            int j = i + 1;
            while (j < n && intervals[i].end >= intervals[j].start) {
                intervals[i].end = max(intervals[i].end, intervals[j].end);
                j++;
            }
            results.push_back(intervals[i]);
            i = j;
        }
        return results;
    }
    static bool compare(Interval& i1, Interval& i2) {
        return i1.start < i2.start;
    }
};

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

Things to learn:

324. Wiggle Sort II

Difficulty: Medium

Frequency: N/A

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), m = (n + 1) / 2;
        vector<int> small(nums.begin(), nums.begin() + m);
        vector<int> large(nums.begin() + m, nums.end());
        reverse(small.begin(), small.end());
        reverse(large.begin(), large.end());
        
        vector<int> result;
        for (int i = 0; i < m; i++) {
            result.push_back(small[i]);
            if (i < large.size()) result.push_back(large[i]);
        }
        nums = result;
    }
};

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

Things to learn:

280. (Locked)Wiggle Sort

Difficulty: Medium

Frequency: N/A

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 1; i < n - 1; i += 2) swap(nums[i], nums[i + 1]);
    }
};

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

Things to learn:

179. Largest Number

Difficulty: Medium

Frequency: N/A

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), compare);
        string result;
        for (int i = nums.size() - 1; i >= 0; i--) {
            result += to_string(nums[i]);
        }
        if (result.find_first_not_of('0') == string::npos) return "0";
        else return result = result.substr(result.find_first_not_of('0'));
    }
private:
    static bool compare(int& num1, int& num2) {
        string s1 = to_string(num1);
        string s2 = to_string(num2);
        if ((s1 + s2) < (s2 + s2)) return true;
        else return false;
    }
};

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

Things to learn:

148. Sort List

Difficulty: Medium

Frequency: N/A

Sort a linked list in O(n log n) time using constant space complexity.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode *p = head;
        int n = 0;
        while (p) {
            n++;
            p = p->next;
        }
        return divide(head, n);
    }
    ListNode* divide(ListNode *&head, int n) {
        if (n == 0) return NULL;
        if (n == 1) {
            ListNode *newHead = head;
            head = head->next;
            newHead->next = NULL;
            return newHead;
        }
        ListNode *head1 = divide(head, n/2);
        ListNode *head2 = divide(head, n - n/2);
        return merge(head1, head2);
    }
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode *dummy = new ListNode(0);
        ListNode *p = dummy;
        while (head1 && head2) {
            if (head1->val < head2->val) {
                p->next = head1;
                head1 = head1->next;
            } else {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        if (head1) p->next = head1;
        if (head2) p->next = head2;
        return dummy->next;
    }
};

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

Things to learn:

252. (Locked) Meeting rooms

Difficulty: Easy

Frequency: N/A

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

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


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i - 1].end) return false;
        }
        return true;
    }
private:
    static bool compare(Interval& interval1, Interval& interval2) {
        return interval1.start < interval2.start;
    }
};

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

Things to learn:

075. Sort Colors

Difficulty: Medium

Frequency: N/A

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int sec = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] == 0) {
                        nums[j] = nums[i];
                        nums[i] = 0;
                        sec = i + 1;
                    }
                }
            }
        }
        for (int i = sec; i < nums.size(); i++) {
            if (nums[i] == 2) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] == 1) {
                        nums[j] = nums[i];
                        nums[i] = 1;
                    }
                }
            }
        }
    }
};

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

Things to learn:

147. Insertion Sort List

Difficulty: Medium

Frequency: N/A

Sort a linked list using insertion sort.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(INT_MIN);
        while (head) {
            ListNode *cur = dummy, *curNext = cur->next, *headNext = head->next;
            while (cur) {
                if (!curNext) {
                    cur->next = head;
                    head->next = curNext;
                    break;
                } else if (head->val < curNext->val) {
                    cur->next = head;
                    head->next = curNext;
                    break;
                } else {
                    cur = cur->next;
                    curNext = curNext->next;
                }
            }
            head = headNext;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

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

Things to learn: