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:
Advertisements

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: