Saturday, October 12, 2013

Integer to Roman

Problem:
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution:

public String intToRoman(int num) {
    int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder res = new StringBuilder();
    int i=0;
    while (num>0) {
        int times = num / nums[i];
        num -= nums[i]*times;
        for (; times>0; times--) {
            res.append(symbols[i]);
        }
        ++i;
    }
    return res.toString();
}


Complexity:
time - O(1)
space - O(1)
Links and credits:
http://discuss.leetcode.com/questions/194/integer-to-roman

Wednesday, October 2, 2013

Reverse Nodes in k-Group

Problem:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:
It's easy to reverse the whole linked list (i.e. consider k === list length). Now, the definition of the "whole list" is only a matter of how we define its head and tail. We should just traverse the original list and treat each k-group as a separate list and reverse it one by one until we reach a group of size less than k.

ListNode *reverseKGroup(ListNode *head, int k) {
    if (!head || k <= 1) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy;

    int i = 0;
    while (head) {
        i++;
        if (i % k == 0) {
            pre = reverse(pre, head->next);                
            head = pre->next;
        } else {
            head = head->next;   
        }
    }

    return dummy.next;
}

ListNode *reverse(ListNode *pre, ListNode *next) {
    ListNode *last = pre->next;
    ListNode *cur = last->next;
    while (cur != next) {
        last->next = cur->next;
        cur->next = pre->next;
        pre->next = cur;

        cur = last->next;
    }
    return last;
}


Complexity:
time - O(n)
space - O(1)
Links and credits:
http://discuss.leetcode.com/questions/206/reverse-nodes-in-k-group

Median of Two Sorted Arrays

Problem:
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution:

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if (0 == total % 2) {
        return (FindKth(A, m, B, n, total/2) + FindKth(A, m, B, n, total/2 + 1)) / 2;
    } else {
        return FindKth(A, m, B, n, total/2 + 1);
    }
}

double FindKth(int A[], int m, int B[], int n, int k) {
    if (m > n) return FindKth(B, n, A, m, k);
    if (0 == m) return B[k-1];
    if (0 == n) return A[k-1];
    if (1 == k) return min(A[0], B[0]);

    int aMid = min(k/2, m);
    int bMid = k - aMid;
    if (A[aMid-1] < B[bMid-1]) {
        return FindKth(A + aMid, m - aMid, B, n, k - aMid);
    } else {
        return FindKth(A, m, B + bMid, n - bMid, k - bMid);
    }
}


Complexity:
time - O(log n)
space - O(log n) (for recursion stack; could be optimized to O(1) using iterative approach)
Links and credits:
http://discuss.leetcode.com/questions/142/median-of-two-sorted-arrays

Find the k-th Smallest Element in the Union of Two Sorted Arrays

Problem:
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

Solution:

O(m + n): Merge the arrays and return the k-th element. Also requires O(m+n) memory.

O(k): Maintain two indexes for each array and perform the merge procedure w/o actually merging the arrays. I.e. just traverse them both and return the k-th element.

O(log m + log n): Given i and j as indexes in A and B respectively, the smallest of A[i] and B[j] is the element that we search for if  i+j = k-1 AND the element (say, A[i]) satisfies B[j-1] < A[i] < B[j] (or vice versa for B[j].) And since the arrays are sorted, we can perform "binary searches" on them, or rather divide them by half. See Links for the code.

O(log k): This is similar to the previous method, but is done by maintaining the "left" and "right" borders of the smallest subarray of size 2*k in an array that would have been the result of merging the arrays. We do not perform the actual merge operation, we only do binary searches on the bottom parts of the arrays:

int findKthInSortedArrays(int A[], int B[], int k) {
    if (A == null)  A = new int[0];
    if (B == null)  B = new int[0];
    int nA = A.length;
    int nB = B.length;
    if (nA == 0 && nB == 0) return Integer.MIN_VALUE;

    int l = k - Math.min(k, nB);
    int r = Math.min(k, nA);

    while(l <= r) {
        int i = l + (r - l) / 2;
        int j = k - i;

        int a_i = (i < nA) ? A[i] : Integer.MAX_VALUE;
        int a_i_prev = (i > 0) ? A[i-1] : Integer.MIN_VALUE;
        int b_j = (j < nB) ? B[j] : Integer.MAX_VALUE;
        int b_j_prev = (j > 0) ? B[j-1] : Integer.MIN_VALUE;

        if (a_i >= b_j_prev && b_j >= a_i_prev) {
            return Math.max(a_i_prev, b_j_prev);
        }

        if (a_i < b_j_prev) {
            l = i + 1;
        } else {
            r = i - 1;
        }
    }

    return Integer.MIN_VALUE;
}


Complexity:
time - O(log n)
space - O(1)
Links and credits:
http://discuss.leetcode.com/questions/136/find-the-k-th-smallest-element-in-the-union-of-two-sorted-arrays