April 2019 – programmingpuzzles

Posted on April 30, 2019 by seeker

LeetCode – 238 : Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4] 
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)


class Solution {
    public int[] productExceptSelf(int[] nums) {
        
    }
}

Idea - 1

We precompute cumulative products from left to right in l2r and cumulative products from right to left in r2l. Then result[i] = l2r[i-1]*r2l[i+1]. Here i-1 and i+1 can go out of range, if that case we use 1. Time complexity is $O(n)$ and space complexity is $O(n)$ .


class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        if(n<2)
        {
            return nums;
        }
        
        int[] l2r = new int[n];
        l2r[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            l2r[i] = l2r[i-1]*nums[i];
        }
        
        int[] r2l = new int[n];
        r2l[n-1] = nums[n-1];
        for(int i = n-2; i >= 0; --i)
        {
            r2l[i] = nums[i]*r2l[i+1];
        }
        
        int[] result = new int[n];
        for(int i = 0; i < n; ++i)
        {
            int left = (i-1 >= 0) ? l2r[i-1] : 1;
            int right = (i+1 < n) ? r2l[i+1] : 1;
            
            result[i] = left*right;
        }
        
        return result;
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 42.6 MB, less than 69.83% of Java online submissions for Product of Array Except Self.

Idea - 2

We could use the output array to precompute l2r. Then from right to left we shall be computing the final value for result[i], but to keep track of product in [i+1...n-1] we use another variable. Time $O(n)$ and space $O(1)$ .


class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        if(n<2)
        {
            return nums;
        }
        
        int[] result = new int[n];
        result[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            result[i] = result[i-1]*nums[i];
        }
        
        int right = 1;
        for(int i = n-1; i >= 0; --i)
        {
            int left = (i-1) >= 0 ? result[i-1] : 1;
            result[i] = left*right;
            right *= nums[i];
        }
        
        return result;
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 42.2 MB, less than 70.06% of Java online submissions for Product of Array Except Self.

Posted on April 29, 2019 by seeker

LeetCode – 121 : Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4] 
Output: 5 
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1] 
Output: 0 
Explanation: In this case, no transaction is done, i.e. max profit = 0.


class Solution {
    public int maxProfit(int[] prices) {
        
    }
}

Idea - 1

We try each of the possible $O(n^2)$ pairs (one for buy and one for sell) and track the max profit. Time complexity $O(n^2)$ and space $O(1)$ .


class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2)
        {
            return 0;
        }
        
        int maxprofit = 0;
        for(int i = 0; i < n-1; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                maxprofit = Math.max(maxprofit, prices[j]-prices[i]);
            }
        }
        
        return maxprofit;
    }
}


Runtime: 175 ms, faster than 7.70% of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 39.6 MB, less than 28.63% of Java online submissions for Best Time to Buy and Sell Stock.

Idea - 2

Say we have the min price in $[0\ldots i-1]$ and it is $\mu$ . Now consider i-th day to be the sell day, then the max profit we can make selling on i-th day is prices[i]- $\mu$ . We need to find best of such max profits. Also, for the days that come after i, prices[i] can act like the best selling price (min) so we need to see if we can update $\mu$ with prices[i]. The time complexity is $O(n)$ and space $O(1)$ .


class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2)
        {
            return 0;
        }
        
        int maxprofit = 0;
        int minsofar = prices[0];
        for(int i = 1; i < n; ++i)
        {
            maxprofit = Math.max(maxprofit, prices[i]-minsofar);
            minsofar = Math.min(minsofar, prices[i]);
        }
        
        return maxprofit;
    }
}


Runtime: 1 ms, faster than 81.15% of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 38.7 MB, less than 53.71% of Java online submissions for Best Time to Buy and Sell Stock.

Posted on April 28, 2019April 28, 2019 by seeker

LeetCode – 175 : Combine Two Tables

SQL Schema

Table: Person

+-------------+---------+ 
| Column Name | Type    | 
+-------------+---------+ 
| PersonId    | int     | 
| FirstName   | varchar | 
| LastName    | varchar | 
+-------------+---------+ 
PersonId is the primary key column for this table.

Table: Address

+-------------+---------+ 
| Column Name | Type    | 
+-------------+---------+ 
| AddressId   | int     | 
| PersonId    | int     | 
| City        | varchar | 
| State       | varchar | 
+-------------+---------+ 
AddressId is the primary key column for this table.

Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:

FirstName, LastName, City, State

Idea – 1

We need to join Person and Address tables. Inner Join gives results when both tables have matching PersonId. We need to return result even if a person does not have address information. So, we use Left Join – if a person does not have address information we only get first and last names.


SELECT Person.FirstName, Person.LastName, Address.City, Address.State
FROM Person LEFT JOIN Address 
ON Person.PersonId=Address.PersonId;


Runtime: 203 ms, faster than 95.92% of MySQL online submissions for Combine Two Tables.

Posted on April 27, 2019 by seeker

LeetCode – 7 : Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123 
Output: 321

Example 2:

Input: -123 
Output: -321

Example 3:

Input: 120 
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹− 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Idea – 1

We would remember the sign and then work with the absolute value. Need to be careful, absolute value can be too large for an integer. And during the reversing for each next digit we would check if it will cause an overflow or an underflow. The time complexity is $O(\lg{n})$ and space is $O(1)$ .


class Solution {
    
    private static final int TENTH = Integer.MAX_VALUE/10;
    
    public int reverse(int x) {
        if(x==Integer.MIN_VALUE)
        {
            return 0;
        }
        
        boolean negative = x < 0;
        x = Math.abs(x);
        
        int y = 0;
        while(x > 0)
        {
            int d = x%10;
            if(toobig(y, d, negative))
            {
                return 0;
            }
            
            y = 10*y + d;
            
            x /= 10;
        }
        
        return negative ? -y : y;
    }
    
    private boolean toobig(int y, int d, boolean negative)
    {
        if(y < TENTH)
        {
            return false;
        }
        else if(y > TENTH)
        {
            return true;
        }
        else
        {
            return (negative && d == 9) || (!negative && d > 7);
        }
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Reverse Integer.
Memory Usage: 32.5 MB, less than 100.00% of Java online submissions for Reverse Integer.

Posted on April 26, 2019 by seeker

LeetCode – 206 : Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL 
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
    }
}

Idea - 1

If we process the list left to right, then for a node c and next node n, if we recursively reverse the part right of c then c must go as the next of n. So, we need to save reference to n while processing node c. The algorithm takes time $O(n)$ and space $O(n)$ .


class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseFrom(head);
    }
    
    private ListNode reverseFrom(ListNode c)
    {
        if(c==null || c.next == null)
        {
            return c;
        }
        
        ListNode n = c.next;
        c.next = null;

        ListNode restReversed = reverseFrom(n);
        
        n.next = c;
        
        return restReversed;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 14.19% of Java online submissions for Reverse Linked List.

Idea - 2

We could insert each node at the front of a new list. Time $O(n)$ and space $O(1)$ .


class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        ListNode q = dummy;
        
        while(p != null)
        {
            ListNode pnext = p.next;
            p.next = q.next;
            q.next = p;
            
            p = pnext;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 9.02% of Java online submissions for Reverse Linked List.

Posted on April 25, 2019April 25, 2019 by seeker

LeetCode – 253 : Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]] 
Output: 2

Example 2:

Input: [[7,10],[2,4]] 
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.


class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
    }
}

Problem Clarification

In the first example, [5, 10] and [15, 20] do not overlap, so we can accommodate those two in a single room. However [0, 30] overlaps with other two, so we need 1 room for [0, 30], thus in total 2 rooms are needed. Lets assume, if we have [a, b] and [b, c] where a < b, we can accommodate them in a single room, though the second meeting folks would be entering when first meeting folks are exiting.

Idea - 1

If we want to place the meeting, it helps to arrange them in increasing order of start time - if one meeting starts in the morning and one starts in the evening, naturally the morning one needs to be accommodated first. Say we scheduled the meeting that starts earliest in a room. Now the meeting that starts next, if it starts no earlier than when the first meeting ends, we can reuse the room, otherwise we need another room. So, to find out if an earlier room can be reused, it helps to know which of the earlier rooms become empty first, i.e. which of the earlier room's end time comes first (we use a minheap with comparison on end times). If we cannot reuse that room for the current meeting, no other of the earlier rooms can be reused, we need a new room. Because current meeting starts later than every other previously seen meeting. Sorting takes $O(n\lg{n})$ time and the minheap operations take $O(n\lg{n})$ time. So overall time $O(n\lg{n})$ and space $O(n)$ .


class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        if(n < 2)
        {
            return n;
        }
        
        Arrays.sort( intervals, new Comparator<int[]>()
                    {
                        public int compare(int[] a, int[] b)
                        {
                            return a[0]-b[0];
                        }
                    });
        
        PriorityQueue<int[]> minq = new PriorityQueue<int[]>(new Comparator<int[]>()
                                                             {
                                                                 public int compare(int[] a, int[] b)
                                                                 {
                                                                     return a[1]-b[1];
                                                                 }
                                                             });
        
        minq.offer(intervals[0]);
        for(int i = 1; i < n; ++i)
        {
            int[] curr = intervals[i];
            int[] earliestFree = minq.poll();
            
            if(curr[0] >= earliestFree[1]) // reuse
            {
                // update how long it will be occupied
                earliestFree[1] = Math.max(earliestFree[1], curr[1]);
            }
            else // needs a separate room
            {
                minq.offer(curr);
            }
            
            minq.offer(earliestFree);
        }
        
        return minq.size();
    }
}


Runtime: 8 ms, faster than 53.61% of Java online submissions for Meeting Rooms II.
Memory Usage: 37.9 MB, less than 74.91% of Java online submissions for Meeting Rooms II.

Posted on April 24, 2019 by seeker

LeetCode – 301 : Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()" 
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()" 
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")(" 
Output: [""]

Idea – 1

If we have n open/close parentheses, we could try each of $O(2^n)$ possibilities and group the valid ones by length. Then the valid group with the longest length would be our solution. Time complexity $O(n\cdot 2^n)$ and space complexity $O(2^n)$ .


class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashMap<Integer, HashSet<String>> map = new HashMap<>();
        collect(s, 0, "", map);
        
        int max = 0;
        for(int k : map.keySet())
        {
            max = Math.max(max, k);
        }
        
        return new ArrayList<String>(map.get(max));
    }
    
    private void collect(String s, int i, String curr, HashMap<Integer, HashSet<String>> ans)
    {
        if(i >= s.length())
        {
            if(valid(curr))
            {
                HashSet<String> grp = ans.getOrDefault(curr.length(), new HashSet<>());
                grp.add(curr);
                ans.put(curr.length(), grp);
            }
            
            return;
        }
        
        char c = s.charAt(i);
        
        if(Character.isLetter(c))
        {
            collect(s, i+1, curr+c, ans);
        }
        else
        {
            collect(s, i+1, curr, ans);
            collect(s, i+1, curr+c, ans);
        }
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 246 ms, faster than 5.01% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 44.5 MB, less than 17.57% of Java online submissions for Remove Invalid Parentheses.

Idea - 2

Since we need to delete min number of parentheses to make it valid, we can consider the output of deleting a parenthesis as a neighbor of current string and thus a BFS would give us the result, actually all valids in an entire level of BFS. Say the input has n characters in it, then it would produce n neighbors each having length n-1, each of these neighbors would produce n-1 neighbors having length n-2, etc. So the time complexity is $O(n\cdot n!)$ and space would be $O(2^n)$ .


class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashSet<String> set = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        
        Deque<String> q = new ArrayDeque<>();
        q.addLast(s);
        visited.add(s);
        
        boolean found = false;
        while(!q.isEmpty())
        {
            int n = q.size();
            while(n-- > 0)
            {
                String front = q.removeFirst();
                if(valid(front))
                {
                    set.add(front);
                    found = true;
                }
                
                if(!found)
                {
                    for(int i = 0; i < front.length(); ++i)
                    {
                        if(Character.isLetter(front.charAt(i)))
                        {
                            continue;
                        }
                        
                        String nei = front.substring(0, i) + front.substring(i+1);
                        if(!visited.contains(nei))
                        {
                            visited.add(nei);
                            q.addLast(nei);
                        }
                    }
                }
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 52 ms, faster than 36.58% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 41.6 MB, less than 36.73% of Java online submissions for Remove Invalid Parentheses.

Posted on April 23, 2019April 23, 2019 by seeker

LeetCode – 138 : Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} 
Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

You must return the copy of the given head as a reference to the cloned list.


/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        
    }
}

Idea - 1

If we had a singly linked list, we could keep copying each node as we go along. However the random pointer makes it a little complicated. While making copy of a node we might end up making at most 3 copies: one for the node, one for its next, and the third for its random. Now both next (a previous random pointed to the next) and random (random is pointing to an earlier node) of a node could already have been copied. To retrieve such a copy we keep a map from a node to its copy. The algorithm has time complexity $O(n)$ and space complexity $O(n)$ .


class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        Node copyHead = new Node(head.val);
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, copyHead);
        
        Node p = head;
        Node q = copyHead;
        
        while(p != null)
        {
            // invariant: p has already been copied into q
            // we will fix q's next and random here
            
            if(p.next != null)
            {
                Node qnext = map.getOrDefault(p.next, new Node(p.next.val));
                q.next = qnext;
                map.put(p.next, qnext);
            }
            
            if(p.random != null)
            {
                Node qrandom = map.getOrDefault(p.random, new Node(p.random.val));
                q.random = qrandom;
                map.put(p.random, qrandom);
            }
            
            p = p.next;
            q = q.next;
        }
        
        return copyHead;
    }
}


Runtime: 1 ms, faster than 83.25% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 36.8 MB, less than 99.59% of Java online submissions for Copy List with Random Pointer.

Idea - 2

We are using the map to find out where the copy of a given node is. If instead we keep the copy just beside the original node, we do not need the map. We do it in three passes: (1) Make a list of size 2*n where each original node's next will point to its copy and that copy's next will point to the next original node in the original list. (2) We fix random pointer for each copy which is each because the original and copy are adjacent (3) We break the 2*n list into original and copy lists. Time is $O(n)$ and space is $O(1)$ . Note, we are not counting the size of the out put in space complexity since a deep copy will always require that.


class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        // create 2*n list
        Node p = head;
        while(p != null)
        {
            Node p2 = new Node(p.val);
            Node pnext = p.next;
            p.next = p2;
            p2.next = pnext;
            
            p = pnext;
        }
        
        // fix random pointer of copy
        p = head;
        while(p != null)
        {
            if(p.random != null)
            {
                p.next.random = p.random.next;
            }
            
            p = p.next.next;
        }
        
        Node dummy = new Node(-1);
        Node t = dummy;
        
        // break into two n-size lists
        p = head;
        while(p != null)
        {
            t.next = p.next;
            p.next = p.next.next;
            t = t.next;
            p = p.next;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Copy List with Random Pointer.

Posted on April 22, 2019 by seeker

LeetCode – 23 : Merge k Sorted Lists

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

Example:

Input: [   1->4->5,   1->3->4,   2->6 ] 
Output: 1->1->2->3->4->4->5->6


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
    }
}

Problem Clarification

We are allowed to modify the given lists to produce the resultant merged list.

Idea - 1

We know how to merge two sorted lists. So, we apply the same idea k-1 times. Merge first and second lists. Merge the result with the third list and so on. Say each list has n nodes. There are then k-1 merges requiring time $2n,\ 3n,\ \ldots,\ kn$ . The overall time complexity is $O(n\cdot k^2)$ and space $O(1)$ .


class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k==0)
        {
            return null;
        }
        
        ListNode result = lists[0];
        for(int i = 1; i < k; ++i)
        {
            result = merge2(result, lists[i]);
        }
        
        return result;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 169 ms, faster than 12.22% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 51.3 MB, less than 5.05% of Java online submissions for Merge k Sorted Lists.

Idea - 2

Actually the first node in the result list must be the one among the heads of the k lists that has minimal value. Thus if we repeatedly pick the min from the k heads we have the merged list. To efficiently pick the min we use a minheap. Time $O(\lg{k} \cdot kn)$ and space $O(\lg{k})$ .


class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> mq = new PriorityQueue<>(new Comparator<ListNode>()
                                                         {
                                                             public int compare(ListNode a, ListNode b)
                                                             {
                                                                 return a.val - b.val;
                                                             }
                                                         });
        
        for(ListNode head : lists)
        {
            if(head != null)
            {
                mq.offer(head);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(!mq.isEmpty())
        {
            ListNode min = mq.poll();
            t.next = min;
            t = t.next;
            
            if(min.next != null)
            {
                min = min.next;
                mq.offer(min);
            }
        }
        
        return dummy.next;
    }
}


Runtime: 5 ms, faster than 91.84% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 40.6 MB, less than 22.83% of Java online submissions for Merge k Sorted Lists.

Idea - 3

We can merger each pair of the given k lists as a result we have k/2 lists. We keep doing the same until we end up with a single list. Time complexity is $\frac{k}{2}\cdot 2n\ +\ \frac{k}{4}\cdot 4n\ +\ \ldots\ +\ \frac{k}{2^{\lg{k}}}\cdot 2^{\lg{k}}n\ =\ O(\lg{k}\cdot kn)$ . Space complexity is $O(1)$ .


class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        
        if(k==0)
        {
            return null;
        }
        
        while(k > 1)
        {
            k = mergePairs(lists, k);
        }
        
        return lists[0];
    }
    
    private int mergePairs(ListNode[] lists, int n)
    {
        int i = 0;
        int j = 0;
        while(i < n-1)
        {
            lists[j++] = merge2(lists[i], lists[i+1]);
            i += 2;
        }
        
        if(i < n)
        {
            lists[j++] = lists[i];
        }
        
        return j;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 2 ms, faster than 99.90% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.5 MB, less than 12.95% of Java online submissions for Merge k Sorted Lists.

Posted on April 21, 2019April 21, 2019 by seeker

LeetCode – 273 : Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123 
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345 
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567 
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891 
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Idea – 1

We can recursively process each named power of tens starting from the highest one going towards lowest, like process billions, then millions, then thousands, etc. Subhundreds have more variation in names like teens, twenties, thirties, etc. Since the input is an integer, basically this is a $O(1)$ algorithm. However devil’s in details! For each named power of tens we have a quotient and a remainder. What if there is no remainder?


class Solution {
    private static final int[] units = {1000000000, 1000000, 1000, 100};
    private static final String[] names = {"Billion", "Million", "Thousand", "Hundred"};
    private static final String[] ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    
    private static final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    private static final String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    
    public String numberToWords(int num) {
        StringBuilder sb = new StringBuilder();
        if(num==0)
        {
            return "Zero";
        }        
        
        n2e(num, sb);
        
        return sb.toString().trim();
    }
    
    private void n2e(int num, StringBuilder sb)
    {
        for(int i = 0; i < units.length; ++i)
        {
            int unit = units[i];
            if(num >= unit)
            {
                n2e(num/unit, sb);
                sb.append(String.format(" %s", names[i]));
                
                num %= unit;
            }
        }
        
        if(num > 0)
        {
            int t = num/10;
            if(t == 0)
            {
                sb.append(String.format(" %s", ones[num]));
            }
            else if(t == 1)
            {
                sb.append(String.format(" %s", teens[num%10]));
            }
            else
            {
                sb.append(String.format(" %s", tens[t]));
                if(num%10 > 0)
                {
                    sb.append(String.format(" %s", ones[num%10]));    
                }
            }    
        }
    }
}


Runtime: 13 ms, faster than 6.23% of Java online submissions for Integer to English Words.
Memory Usage: 38.2 MB, less than 5.18% of Java online submissions for Integer to English Words.