[LintCode] Nuts & Bolts Problem

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Example

Nuts represented as array of integers nuts[] = {1, 5, 8, 2}. Bolts represented as array of integers bolts[] = {3, 6, 7, 9}. We will give you a compare function to compare nut with bolt. Sort the nuts in increasing order so that nut match with the bolt with the same position.

Reference quick sort:

/**
 * class Compare {
 *     public:
 *     static int cmp(int a, int b);
 * };
 * You can use Compare::cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
public:
    void sortNutsAndBolts(vector<int> &nuts, 
                          vector<int> &bolts,
                          int s, int e) {
        if(s >= e) return;
        
        int start = s, end = s, match;
        
        while(end <= e){
            if(Compare::cmp(nuts[end], bolts[s])<=0){
                if(Compare::cmp(nuts[end], bolts[s]) == 0)
                    match = start;
                swap(nuts[start], nuts[end]);
                start ++;
            }
            end ++;
        }
        swap(nuts[start-1], nuts[match]);
        int pivot = start - 1;
        
        start = s;
        end = s;
        while(end <= e) {
            if(Compare::cmp(nuts[pivot], bolts[end])>=0) {
                if(Compare::cmp(nuts[pivot], bolts[end]) == 0)
                    match = start;
                swap(bolts[start], bolts[end]);
                start ++;
            }
            end ++;
        }
        swap(bolts[pivot], bolts[match]);   
        
        sortNutsAndBolts(nuts, bolts, s, pivot-1);
        sortNutsAndBolts(nuts, bolts, pivot+1, e);
    }
    
    void sortNutsAndBolts(vector<int> &nuts, vector<int> &bolts) {
        sortNutsAndBolts(nuts, bolts, 0, bolts.size()-1);
    }
};

[LintCode] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]

Challenge

O(n log n) time and O(1) extra space.

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
    static bool compFunc(const Interval &i1, const Interval& i2)
    {
        return i1.start < i2.start;
    }
public:
    vector<Interval> merge(vector<Interval> &intervals) {

        int size = intervals.size();
        vector<Interval> res;
        if(0 == size) return res;
        sort(intervals.begin(), intervals.end(), compFunc);
        
        res.push_back(intervals[0]);
        for(int i=1;i<size;i++)
        {
            if(!(res.back().start>intervals[i].end 
                || res.back().end < intervals[i].start)){
                res.back().start = min(res.back().start, intervals[i].start);
                res.back().end = max(res.back().end, intervals[i].end);
            }
            else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

[LintCode/LeetCode] Maximum Gap

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

Return 0 if the array contains less than 2 elements.

Example

Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.

Note

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

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

Analysis:

Find the max and min element of the array, and map all elements into n buckets based their relative value to the min value. Element a will be mapped into the index i = (a-min)*(n-1)/(max-min).

Maintain the max and min elements in each bucket. The maximum gap must be one of the gaps of max and min in adjacent buckets.

class Solution {
public:
    int maximumGap(vector<int> nums) {
        // write your code here
        int len = nums.size();
        if(len < 2) return 0;
        int minV = INT_MAX, maxV = INT_MIN;
        for(auto e : nums){
            minV = min(minV, e);
            maxV = max(maxV, e);
        }
        if(maxV == minV) return 0;
        
        float gap = (maxV - minV)/(float)(len-1);
        vector<int> maxBucket(len, INT_MIN),minBucket(len, INT_MAX);

        for(auto e: nums){
            int i = (e-minV)/gap;
            maxBucket[i] = max(maxBucket[i], e);
            minBucket[i] = min(minBucket[i], e);
        }
        
        int previous = minV;
        int res = INT_MIN;
        for(int i=1;i<len;i++){
            if(maxBucket[i] == INT_MIN && 
                minBucket[i] == INT_MAX) continue;
            res = max(res, minBucket[i]-previous);
            previous = maxBucket[i];
        }
        return res;
    }
};

[LeetCode] Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Quick select:

class Solution {
public:
    int partition(vector<int>& nums, int start, int end, int k)
    {
        int pivot = nums[k];
        swap(nums[end], nums[k]);
        int storedIndex = start;
        for(int i=start;i<=end-1;i++)
        {
            if(nums[i]>pivot)
            {
                swap(nums[i], nums[storedIndex]);
                storedIndex ++;
            }
        }
        swap(nums[end], nums[storedIndex]);
        return storedIndex;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int end = nums.size()-1;
        if(end<0) return 0;
        int start = 0;
        k--;
        int ret = partition(nums, start, end, k);
        while(k != ret)
        {
            if(ret < k) ret = partition(nums, ret+1, end, k);
            else ret = partition(nums, start, ret-1, k);
        }
        return nums[k];
    }
};

[LintCode] Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.

Example

A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

class Solution {
public:
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    int getPos(vector<int> &A, int start, int end, int target)
    {
        if(target > A[end]) return end+1;
        
        while(start<end)
        {
            int mid = (start+end)/2;
            if(A[mid] < target) start = mid + 1;
            else end = mid;
        }
        return start;
    }
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        int lenA = A.size(), lenB = B.size();
        vector<int> *pLarge, *pSmall;
        if(lenA > lenB){
            pLarge = &A;
            pSmall = &B;
        }
        else{
            pLarge = &B;
            lenA = B.size();
            pSmall = &A;
            lenB = A.size();
        }
        
        int i = 0, j = 0;
        while(j<lenB){
            i = getPos(*pLarge, i, lenA-1, (*pSmall)[j]);
            pLarge->insert(pLarge->begin()+i, (*pSmall)[j++]);
            if(i == lenA) break;
            lenA++;
        }
        while(j<lenB) pLarge->push_back((*pSmall)[j++]);
        return *pLarge;
    }
};

[LintCode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Example

A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

Note

You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.

Analysis: We can just take advantage of the extra space of A to accommodate B.

class Solution {
public:
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    void reverse(int A[], int start, int end)
    {
        while(start < end)
        {
            int tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            start++;
            end --;
        }
    }
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        if(0 == n) return ;
        int index = m;
        int i = 0, j = 0;
        while(j<n)
        {
            int toFit = index++ % (m+n);
            if(i<m && A[i] < B[j]) A[toFit] = A[i++];
            else A[toFit] = B[j++];
        }
        reverse(A, m,m+n-1);
        reverse(A, 0, m-1);
        reverse(A, 0,m+n-1);
    }
};

[LintCode] Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order andnon-overlapping (merge intervals if necessary).

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
public:
    static bool comp(Interval i1, Interval i2)
    {
        return i1.start < i2.start;
    }
    
    Interval merge(Interval &i1, Interval &i2)
    {
        Interval res(min(i1.start, i2.start), max(i1.end, i2.end));
        return res;
    }
    
    bool hasOverlap(Interval &i1, Interval &i2)
    {
        if(i1.end < i2.start || i2.end < i1.start) return false;
        return true;
    }
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) 
    {
        sort(intervals.begin(), intervals.end(), comp);
        vector<Interval> res;
        for(int i=0;i<intervals.size();i++)
        {
            if(hasOverlap(intervals[i], newInterval))
            {
                newInterval = merge(intervals[i], newInterval);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        int i=0;
        while(i<res.size() && newInterval.end>res[i].start) i++;
        res.insert(res.begin()+i, newInterval);
        return res;
    }
};

[LeetCode] Merge Intervals

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].

/**
 * 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 {
    static bool compare(Interval & i1, Interval & i2)
    {
        return i1.start < i2.start;
    }
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        int len = intervals.size();
        vector<Interval> res;
        if(0 == len) return res;
        res.push_back(intervals[0]);
        for(int i=1;i<len;i++)
        {
            Interval & cur = res[res.size()-1];
            if(cur.end >= intervals[i].start)
            {
                cur.end = max(cur.end, intervals[i].end);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

[LeetCode] Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode node(0);
        ListNode *head = &node;
        
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                head->next = l2;
                l2 = l2->next;
            }
            else
            {
                head->next = l1;
                l1 = l1->next;
            }
            head = head->next;
        }
        if(l1) head->next = l1;
        else head->next = l2;
        
        return node.next;
    }
    ListNode* mergeSort(vector<ListNode *> &lists, int start, int end)
    {
        if(end - start == 1) return mergeTwoLists(lists[start], lists[end]);
        if(start == end) return lists[start];
        return mergeTwoLists(mergeSort(lists, start, (start+end)/2), 
                             mergeSort(lists,(start+end)/2 + 1, end));
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) 
    {
        if(0 == lists.size()) return NULL;
        return mergeSort(lists, 0, lists.size()-1);
    }
};