leetcode Question: Maximum Gap

Maximum Gap

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.

Analysis:

It took me a long time figuring out how to solve it, because I was going to a wrong direction after seeing the linear time/space requirement.  To be honest, I was only thinking  of common sorting algorithms (merge, heap, quick).   However, I missed the another type of sorting algorithm ---- Distribution sort (bucket, counting, radix), which happens to be the key of this problem.

We all know that, merge, heap or quick sorting algorithm can achieve no better than O(n Log n) time complexity.  But for linear time requirement, bucket sort, counting sort and radix sort are often good options.

For this specific problem, bucket sort is not a good option because it usually works well on uniform distributions. Otherwise, in each bucket, the insertion sort may cause heavy burden on time complexity. Counting sort, has time complexity O(n + k), where k is the range of the elements. But when k > n^2, it is worse than the common sorting algorithms. So we use the radix sort for solving this problem.

The idea of radix sort is as follows:

• Sort elements according to each digit (from lower to higher).
• For each digit, use counting sort.

For example, A = [36 504 79 98 8 55 2 113].

The Radix sorting goes like following steps:

Sort 1st digit:
A = [2, 113, 504, 55, 36, 98, 8, 79]

Sort 2nd digit:
A = [2, 504, 8, 113, 36, 55, 79, 98]

Sort 3rd digit:
A = [2, 8, 36, 55, 79, 98, 113, 504]

Done.


To sort array according to each digit, counting sort is used. Note that, we only need to have a array of size 10 to store the frequencies of elements. This is because we only consider and sort a single digit in each iteration of Radix sort.

The general form of counting sort is:
(1) Count the frequencies of each elements.  (count[a[i]] ++, this also considers the duplicates)
(2) Get the index of each number in the output array. (count[i]+= count[i-1])
(3) Put numbers in order. (output[count[a[i]] = a[i], count[a[i]]-- to handle the duplicates)

For radix sort, there is minor modifications, details see the code below.

Code(C++):

class Solution {
public:
    int getMax(vector<int> num){
        int m = INT_MIN;
        for (int i=0;i<num.size();i++){
            m = max(m,num[i]);
        }
        return m;
    }
    
    void countSort(vector<int> &num, int nd){
        int n = num.size();
        vector<int> output(n,0);
        vector<int> count(10,0);
 
        for (int i = 0; i < n; i++){
            count[ (num[i]/nd)%10 ]++;
        }
 
        for (int i = 1; i < 10; i++){
            count[i] += count[i - 1];
        }
 
        for (int i = n - 1; i >= 0; i--){
            output[ count[(num[i]/nd)%10] - 1] = num[i];
            count[ (num[i]/nd)%10 ]--;
        }
 
        for (int i = 0; i < n; i++){
            num[i] = output[i];
        }
    }

    void radixsort(vector<int> &num){
         int max_n = getMax(num);
         for (int nd = 1; max_n/nd > 0; nd *= 10){
             countSort(num, nd);
         }
    }
    
    int maximumGap(vector<int> &num) {
        if (num.size()<2){
            return 0;
        }
        radixsort(num);
        int res = abs(num[1] - num[0]);
        for (int i=2;i<num.size();i++){
            if (num[i]-num[i-1]>res){
                res = abs(num[i] - num[i-1]);
            }
        }
        return res;
        
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    
    def countsort(self, num, nd):
        count = [0]*10
        n = len(num)
        for i in xrange(0,n):
            count[ (num[i]/nd) %10] += 1
            
        for i in xrange(1,10):
            count[i] += count[i-1]
        
        output = [0]*n
        for i in xrange(n-1,-1,-1):
            output[count[ (num[i]/nd)%10 ] - 1 ] = num[i]
            count[ (num[i]/nd)%10 ] -= 1
        
        return output
    
    def radixsort(self, num):
        max_n = max(num)
        nd = 1
        while max_n / nd > 0:
            num = self.countsort(num, nd)
            nd = nd * 10
        return num
        
    def maximumGap(self, num):
        if len(num) < 2:
            return 0
        num = self.radixsort(num)
        res = abs(num[1] - num[0])
        for i in xrange(2,len(num)):
            res = max(res, abs(num[i] - num[i-1]))
        return res
        
        

leetcode Question: Find Peak Element

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Analysis:

It is required to have log(N) complexity, for the single array, binary search is usually considered since it satisfied the log(N) requirement.
Be careful with the boundary conditions, it is a pretty simple problem.

Code(C++):

class Solution {
public:
    void fp(int st, int ed, const vector<int> &num, int &idx){
        if (st > ed || idx != -1){
            return;
        } else {
            int mid = st + (ed - st)/2;
            
            if (mid == num.size()-1 && num[mid]>num[mid-1]){
                idx = mid;
                return;
            }
            if (mid == 0 && num[mid]>num[mid+1]){
                idx = mid;
                return;
            }
            if (num[mid]>num[mid-1] && num[mid]>num[mid+1]){
                idx = mid;
                return;
            } 
            fp(st,mid-1,num, idx);
            fp(mid+1,ed,num, idx);
        }
    }

    int findPeakElement(const vector<int> &num) {
        if (num.size() == 1){
            return 0;
        }
        int idx = -1;
        fp(0, num.size()-1,num,idx);
        return idx;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    
    idx = -1
    def findPeakElement(self, num):
        if len(num) == 1:
            return 0
        self.fp(0, len(num)-1, num)
        return self.idx
        
    def fp(self, st, ed, num):
        if st > ed or self.idx != -1:
            return
        else:
            mid = st + (ed - st)/2;
            if mid == len(num)-1 and num[mid]>num[mid-1]:
                self.idx = mid
                return
            if mid == 0 and num[mid]>num[mid+1]:
                self.idx = mid
                return
            if num[mid]>num[mid-1] and num[mid]>num[mid+1]:
                self.idx = mid
                return
            self.fp(st,mid-1,num)
            self.fp(mid+1,ed,num)
        

leetcode Question: Intersection of Two Linked Lists

Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

Consider the case that two list has equal length, the problem became so easy: only two pointers are needed.  Scan from the start of each list, check if the node are the same. Problem solved !

However, just like the example showed in the question, we need to handle the case when the two list are not equal in length.  What to do then?  Let's make them equal !
(1) Get the length of list A, say n_a.
(2) Get the length of list B, say n_b.
These two steps will take O(n) time. (n = n_a + n_b)
(3) Set two pointers. Make the pointer of longer list abs(n_a-n_b) steps forward.
(4) Scan the two list until find the intersection, or to the end of list.
This step will take O(n) time.

Totally, time complexity is O(n), space complexity is O(1).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int n1 = 0; //length of headA
        int n2 = 0; //length of headB
        ListNode * a1 = headA; 
        ListNode * a2 = headB;
        
        while (a1){
            n1++;
            a1 = a1->next;
        }
        while (a2){
            n2++;
            a2 = a2->next;
        }
        
        a1 = headA;
        a2 = headB;
        
        while (n1>0 && n2>0){
            if (n1>n2){
                n1--;
                a1 = a1->next;
            }
            if (n2>n1){
                n2--;
                a2 = a2->next;
            }
            if (n2 == n1){
                if (a1 == a2){
                    return a1;
                }else{
                    a1 = a1->next;
                    a2 = a2->next;
                    n1--;
                    n2--;
                }
            }
        }
        return NULL;
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        a = headA
        b = headB
        n1 = 0
        n2 = 0
        
        while a is not None:
            a  = a.next
            n1 += 1
        while b is not None:
            b  = b.next
            n2 += 1
            
        a = headA
        b = headB
        
        while n1 > 0 and n2 > 0:
            if n1 > n2:
                a = a.next
                n1 -= 1
            if n2 > n1:
                b = b.next
                n2 -= 1
            if n1 == n2:
                if a == b:
                    return a
                else:
                    a = a.next
                    b = b.next
                    n1 -= 1
                    n2 -= 1
        return None
        

leetcode Question: Min Stack

Min Stack:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Analysis:

There are several ways to solve this problem.
(1) Use an extra stack to store the minimum value. The space is O(n), time O(1)
(2) Use a variable to store the minimum value. The time is O(n), space O(1)

Note that, in the python code, a little modification is needed to pass the OJ test.
Just using two stacks is not satisfied with the memory requirement.
So, the min stack stores [min_val, count] instead of each min_val.
e.g.,
Push into Stack:
st     min_st
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
3    
0      [0,1]
2      [2,1]

st     min_st
0
3    
0      [0,2]
2      [2,1]

Pop:
st     min_st
3    
0      [0,1]
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
2      [2,1]

Code(C++):

class MinStack {
    deque<int> st;
    int minVal;
public:
    void push(int x) {
        if (st.empty() || x<minVal){
            minVal = x;
        }
        st.push_front(x);
    }

    void pop() {
        if (st.front() == minVal){
            st.pop_front();
            minVal=INT_MAX;
            for (deque<int>::iterator it = st.begin();it!=st.end();it++){
                minVal = min(minVal,*it);
            }
        }else{
            st.pop_front();
        }
        
    }

    int top() {
        return st.front();
    }

    int getMin() {
        return minVal;
    }
};

Code(Python):

class MinStack:
    # @param x, an integer
    # @return an integer
    def __init__(self):
        self.l_num = []
        self.minval = []
    
    def push(self, x):
        if len(self.l_num) == 0 or len(self.minval) == 0:
            self.minval.append([x,1])
        else:
            if x < self.getMin():
                self.minval.append([x,1])
            elif x == self.getMin():
                self.minval[-1][1] += 1
        self.l_num.append(x)
            
    # @return nothing
    def pop(self):
        if self.l_num[-1] == self.minval[-1][0]:
            self.l_num.pop(-1)
            if (self.minval[-1][1]>1):
                self.minval[-1][1] -= 1
            else:
                self.minval.pop(-1)
        else:
            self.l_num.pop(-1)
            
        
    # @return an integer
    def top(self):
        return self.l_num[-1]

    # @return an integer
    def getMin(self):
        return self.minval[-1][0]