Monday, August 31, 2015

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.
A max-heap solution:
First of all, put all elements into the heap. Then poll the top k elements from the max heap then we get the result. The time complexity for max heap is  O(n) + O(k * logn). The space complexity is O(n).

Code (Java):
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(nums.length, Collections.reverseOrder());
        
        for (int num : nums) {
            maxHeap.offer(num);
        }
        
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
        
        return result;
    }
}

A min-heap solution:
 -- Step 1: put the first k elements into the heap. Time complexity is O(k). 
 -- Step 2: Start from elements k + 1 to n, compare each one with heap.peek(). If greater than the peek, replace with the element. The time complexity is O((n - k) logk).
  -- Step 3: After we iterate the array, the heap stores the top k elements, and the kth largest element is the minimum element of the heap, which is peek.

The space complexity is O(k). 

Code (Java):
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else {
                if (num > maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer(num);
                }
            }
        }
        
        return maxHeap.peek();
    }
}


A quick-selection algorithm:
The quick selection algorithm is very similar to quick sort. Instead of sorting, it only needs the partition step, where it finds the pivot and compare the pivot with k. 

There is post for the quick sort. 
http://buttercola.blogspot.com/2014/12/data-structure-algorithms-sorting.html

Code (Java):
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int findKthLargestHelper(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return nums[lo];
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return nums[k];
        }
        
        if (pivot > k) {
            return findKthLargestHelper(nums, lo, pivot - 1, k);
        } else {
            return findKthLargestHelper(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


Since it only uses the partition algorithm, the average time complexity is O(n). However, the worst case complexity is O(n^2). 

In which case the quick selection has time complexity of O(n^2)?
Let's say you have a sorted array, 1 2 3 4 5, and k = 1, means we select the largest element which is 5. For each element in the array, we need to run the partition algorithm and discard the pivot only, which has the time complexity of O(n). For the n elements in the array, the overall time complexity is O(n^2). Therefore, for either quick sort and quick select algorithm, we usually need to well suffle the array for the reason each time the pivot is chosen in the half.

Leetcode: Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.

Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Understand the problem:
A very classic back tracking problem.

Code (Java):
public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (k <= 0 || n <= 0) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        combinationSum3Helper(1, n, 0, k, 0, curr, result);
        
        return result;
    }
    
    private void combinationSum3Helper(int start, int n, int count, int k, int curSum, List<Integer> curr, 
                                       List<List<Integer>> result) {
        if (count > k) {
            return;
        }
        
        if (curSum == n && count == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (curSum + i > n) {
                break;
            }
            curr.add(i);
            combinationSum3Helper(i + 1, n, count + 1, k, curSum + i, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}

Leetcode: Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Code (Java):
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return false;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                int preIndex = map.get(nums[i]);
                if (i - preIndex <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);
                }
            } else {
                map.put(nums[i], i);
            }
        }
        
        return false;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> hashSet = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return true;
            }
            
            hashSet.add(nums[i]);
            
            if (hashSet.size() > k) {
                hashSet.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

Leetcode: Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Understand the problem:
Use a hash set.

Code (Java):
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }
        
        return false;
    }
}

Leetcode: Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Understand the problem:
Use Trie + DFS

Code (Java):
public class WordDictionary {
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.leaf = false;
            this.children = new TrieNode[26];
        }
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
    
    private TrieNode root = new TrieNode();
    private TrieNode dummyRoot = root;
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        int offset = 'a';
        int i = 0;
        for (i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            if (curr.children[character - offset] == null) {
                curr.children[character - offset] = 
                    new TrieNode(character, i == word.length() - 1 ? true : false);
            } else {
                if (i == word.length() - 1) {
                    curr.children[character - offset].leaf = true;
                }
            }
            
            curr = curr.children[character - offset];
        }
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        
        TrieNode curr = root;
        int offset = 'a';
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            if (character != '.') {
                if (curr.children[character - offset] == null) {
                    return false;
                }
                curr = curr.children[character - offset];
            } else {
                // DFS
                for (int j = 0; j < 26; j++) {
                    if (curr.children[j] != null) {
                        if (i == word.length() - 1 && curr.children[j].leaf) {
                            root = dummyRoot;
                            return true;
                        }
                        
                        root = curr.children[j];
                        if (search(word.substring(i + 1))) {
                            root = dummyRoot;
                            return true;
                        }
                    }
                }
                root = dummyRoot;
                return false;
            }
        }
        
        if (curr != null && curr.leaf == false) {
            return false;
        }
        
        return true;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");


Update on 10/19/15:
Updated neat version without saving the value for a TrieNode. 
There are mainly two tricks in the problem:
  -- The first trick is, in the DFS, we need to change the root of the Trie, and don't forget to change it back. 
  -- The second trick is, when we tried all 26 possibilities without getting an answer, we must return false instead. 

public class WordDictionary {
    private Trie trie = new Trie();
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        trie.add(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return trie.search(word);
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        private TrieNode rootCopy = root;
        
        // Add a word
        void add(String word) {
            TrieNode p = root;
            
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (p.children[c- 'a'] != null) {
                    p = p.children[c - 'a'];
                } else {
                    p.children[c - 'a'] = new TrieNode();
                    p = p.children[c - 'a'];
                }
                
                if (i == word.length() - 1) {
                    p.leaf = true;
                }
            }
        }
        
        boolean search(String word) {
            TrieNode p = root;
            
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                
                if (c == '.') {
                    for (int j = 0; j < 26; j++) {
                        if (p.children[j] != null) {
                            // Change the root pointer
                            root = p.children[j];
                            
                            if (search(word.substring(i + 1))) {
                                root = rootCopy;
                                return true;
                            }
                            
                            // Change back the root pointer
                            root = rootCopy;
                        }
                    }
                    // If none of them get true, return false;                   
                    return false;
                } else {
                    if (p.children[c - 'a'] == null) {
                        return false;
                    }
                    p = p.children[c - 'a'];
                }
            }
            
            if (!p.leaf) {
                return false;
            }
            
            return true;
        }
    }
    
    class TrieNode {
        TrieNode[] children;
        boolean leaf;
        
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Leetcode: Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Understand the problem:
Since the array elements are all positive numbers, we could use a sliding window approach. W first move the front pointer until the sum of the subarray is greater or equal to the target value s, then we calculate the size of the window. Then we try to move the rear pointer and recalculate the window size, until the sum of the window is less than the target s. 

Code (Java):
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (s <= 0 || nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        
        while (hi < nums.length) {
            // Moves the hi pointer
            while (hi < nums.length && sum < s) {
                sum += nums[hi];
                hi++;
            }
            
            // Move the lo pointer
            while (lo <= hi && sum >= s) {
                minLen = Math.min(minLen, hi - lo);
                sum -= nums[lo];
                lo++;
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            return 0;
        } else {
            return minLen;
        }
    }
}

Leetcode: Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
Hints:
  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.


Understand the problem:
This problem is equivalent to finding the topological order in a directed graph. According to wiki, the topological  sorting is defined as " In the field of computer science, a topological sort (sometimes abbreviated toposort[1]) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex vu comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time."

Code (Java):
public class Solution {
    private int label;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }
        this.label = numCourses - 1;
        
        int[] result = new int[numCourses];
        
        // No prerequisites
        if (prerequisites == null || prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            
            return result;
        }
        
        // Convert the edge list to adj. list
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : prerequisites) {
            if (adjList.containsKey(edge[1])) {
                List<Integer> neighbors = adjList.get(edge[1]);
                neighbors.add(edge[0]);
                adjList.put(edge[1], neighbors);
            } else {
                List<Integer> neighbors = new ArrayList<Integer>();
                neighbors.add(edge[0]);
                adjList.put(edge[1], neighbors);
            }
        }
        
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (toplogicalSorting(i, visited, adjList, result) == false) {
                return new int[0];
            }
        }
        
        return result;
    }
    
    private boolean toplogicalSorting(int vertexId, int[] visited, 
            Map<Integer, List<Integer>> adjList,
                                   int[] result) {
        // Has been visited
        if (visited[vertexId] == -1) {
            return false;
        }
        
        // Has been added into the list
        if (visited[vertexId] == 1) {
            return true;
        }
        
        visited[vertexId] = -1;
        
        List<Integer> neighbors = adjList.get(vertexId);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (toplogicalSorting(neighbor, visited, 
                    adjList, result) == false) {
                    return false;
                }
            }
        }
        
        result[label--] = vertexId;
        visited[vertexId] = 1;
        
        return true;
                                       
    }
}

Update on 4/22/19: Topological sort using BFS
public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // write your code here
        int[] ans = new int[numCourses];
        int ansIdx = numCourses - 1;
        
        if (prerequisites == null || prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) {
                ans[i] = i;
            }
            
            return ans;
        }
        
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        Map<Integer, Integer> nodeToIndegreeMap = new HashMap<>();
        
        for (int i = 0; i < numCourses; i++) {
            adjList.put(i, new ArrayList<>());
            nodeToIndegreeMap.put(i, 0);
        }
        
        for (int[] prerequisite : prerequisites) {
            List<Integer> neighbors = adjList.get(prerequisite[0]);
            neighbors.add(prerequisite[1]);
            
            int indegree = nodeToIndegreeMap.get(prerequisite[1]);
            indegree += 1;
            nodeToIndegreeMap.put(prerequisite[1], indegree);
        }
        
        // get all nodes with 0 indegree
        //
        Queue<Integer> queue = new LinkedList<>();
        for (Integer node : nodeToIndegreeMap.keySet()) {
            if (nodeToIndegreeMap.get(node) == 0) {
                queue.offer(node);
            }
        }
        
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            ans[ansIdx--] = curNode;
            
            for (int neighbor : adjList.get(curNode)) {
                int indegree = nodeToIndegreeMap.get(neighbor);
                indegree -= 1;
                nodeToIndegreeMap.put(neighbor, indegree);
                
                if (indegree == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        if (ansIdx > 0) {
            return new int[0];
        }
        
        return ans;
    }
}

Leetcode: Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
Hints:
  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
Understand the problem:
The problem is equivalent to finding if a directed graph contains a circle. Thus we could use a DFS or BFS solution.

DFS Solution:
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited. 
visited = -1, means this node has been visited. 
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.

Code (Java):
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return true;
        }
        
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        
        // First transform the edge list to adj. list
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : prerequisites) {
            if (adjList.containsKey(edge[0])) {
                List<Integer> neighbors = adjList.get(edge[0]);
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            } else {
                List<Integer> neighbors = new ArrayList<Integer>();
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            }
        }
        
        int[] visited = new int[numCourses];
        // Check if the graph contains a circle, if yes, return false.
        for (int i = 0; i < numCourses; i++) {
            if (hasCircles(i, visited, adjList)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean hasCircles(int vertexId, int[] visited, Map<Integer, List<Integer>> adjList) {
        if (visited[vertexId] == -1) {
            return true;
        }
        
        if (visited[vertexId] == 1) {
            return false;
        }
        
        visited[vertexId] = -1;
        
        List<Integer> neighbors = adjList.get(vertexId);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (hasCircles(neighbor, visited, adjList)) {
                    return true;
                }
            }
        }
        
        visited[vertexId] = 1;
        
        return false;
    }
}

Update on 4/22/19: Using topological sorting
public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // write your code here
        if (numCourses <= 0 || prerequisites == null || prerequisites.length == 0) {
            return true;
        }

        // step 1: create adjlist and in-=degree map
        //
        Map<Integer, Integer> nodeToIndegreeMap = new HashMap<>();
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        
        for (int i = 0; i < numCourses; i++) {
            nodeToIndegreeMap.put(i, 0);
            adjList.put(i, new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            int inDegree = nodeToIndegreeMap.get(prerequisite[1]);
            inDegree += 1;
            nodeToIndegreeMap.put(prerequisite[1], inDegree);
        }

        for (int[] prerequisite : prerequisites) {
            List<Integer> neighbors = adjList.get(prerequisite[0]);
            neighbors.add(prerequisite[1]);
            adjList.put(prerequisite[0], neighbors);
        }

        // step 2: get all nodes with indegree 0 and put into the queuue
        //
        Queue<Integer> queue = new LinkedList<>();
        int numNodes = 0;
        for (Integer key : nodeToIndegreeMap.keySet()) {
            int indegree = nodeToIndegreeMap.get(key);
            if (indegree == 0) {
                queue.offer(key);
                numNodes += 1;
            }
        }

        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            for (int neighbor : adjList.get(curNode)) {
                int indegree = nodeToIndegreeMap.get(neighbor);
                indegree -= 1;
                nodeToIndegreeMap.put(neighbor, indegree);

                if (indegree == 0) {
                    queue.offer(neighbor);
                    numNodes += 1;
                }
            }
        }

        return numNodes == numCourses;
    }
}

Sunday, August 30, 2015

Leetcode: Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg""add", return true.
Given "foo""bar", return false.
Given "paper""title", return true.
Note:
You may assume both s and t have the same length.
Understand the problem:
The problem is a little bit hard to understand. The essence of the problem is given two strings s and t. We replace the characters in t and is able to get back the string s. Note that the mapping relationship must be 1:1 matching. e.g. 
"foo, bar" => false, because o->a and o->r, which is one to many mapping.
"bar", "foo" => false, because a->o and r->o, which is many to one mapping. 

The idea is to maintain two hash maps. One store the normal mapping between s=>t, and the other map maintains the inverse mapping from t => s. For each character, we check both maps contains the s or t. 

Code (Java):
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || s.length() == 0) {
            return t == null || t.length() == 0;
        }
        
        if (t == null || t.length() == 0) {
            return s == null || s.length() == 0;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> map = new HashMap<Character, Character>();
        Map<Character, Character> inverseMap = new HashMap<Character, Character>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            if (map.containsKey(sChar) && (tChar != map.get(sChar))) {
                return false;
            }
            
            if (inverseMap.containsKey(tChar) && (sChar != inverseMap.get(tChar))) {
                return false;
            }
            
            map.put(sChar, tChar);
            inverseMap.put(tChar, sChar);
        }
        
        return true;
    }
}

Update on 1/28/16:
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) {
            return true;
        }
        
        if ((s == null || s.length() == 0) || (t == null || t.length() == 0)) {
            return false;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> forwardMap = new HashMap<>();
        Map<Character, Character> backwardMap = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            // Must not contain both
            if (!forwardMap.containsKey(sChar) && !backwardMap.containsKey(tChar)) {
                forwardMap.put(sChar, tChar);
                backwardMap.put(tChar, sChar);
            }
            
            // Only one contains
            if (!forwardMap.containsKey(sChar) || !backwardMap.containsKey(tChar)) {
                return false;
            }
            
            if (forwardMap.get(sChar) != tChar || backwardMap.get(tChar) != sChar) {
                return false;
            }
        }
        
        return true;
    }
}

Leetcode: Reverse Linked List

Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Iterative solution:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        
        while (curr != null) {
            curr.next = prev;
            prev = curr;
            curr = next;
            
            if (next != null) {
                next = next.next;
            }
        }
        
        return prev;
    }
}


Recursive solution:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode next = head.next;
        ListNode newHead = reverseList(next);
        
        next.next = head;
        head.next = null;
        
        return newHead;
    }
}

Update on 11/6/15:
Recursive solution using two pointers:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        return reverseListHelper(null, head);
    }
    
    private ListNode reverseListHelper(ListNode prev, ListNode curr) {
        if (curr == null) {
            return prev;
        }
        
        ListNode newHead = reverseListHelper(curr, curr.next);
        
        curr.next = prev;
        
        return newHead;
    }
}

Leetcode: Count Primes

Description:
Count the number of prime numbers less than a non-negative number, n.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hint:
  1. Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrimefunction would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
  2. As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?
  3. Let's write down all of 12's factors:
    2 × 6 = 12
    3 × 4 = 12
    4 × 3 = 12
    6 × 2 = 12
    
    As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then np × q and since p ≤ q, we could derive that p ≤ √n.
    Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?
    public int countPrimes(int n) {
       int count = 0;
       for (int i = 1; i < n; i++) {
          if (isPrime(i)) count++;
       }
       return count;
    }
    
    private boolean isPrime(int num) {
       if (num <= 1) return false;
       // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
       // to avoid repeatedly calling an expensive function sqrt().
       for (int i = 2; i * i <= num; i++) {
          if (num % i == 0) return false;
       }
       return true;
    }
    
  4. The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple.

    Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
    We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
  5. 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
  6. In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of pp2 + pp2 + 2p, ... Now what should be the terminating loop condition?
  7. It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?
  8. Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.
    The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.
    public int countPrimes(int n) {
       boolean[] isPrime = new boolean[n];
       for (int i = 2; i < n; i++) {
          isPrime[i] = true;
       }
       // Loop's ending condition is i * i < n instead of i < sqrt(n)
       // to avoid repeatedly calling an expensive function sqrt().
       for (int i = 2; i * i < n; i++) {
          if (!isPrime[i]) continue;
          for (int j = i * i; j < n; j += i) {
             isPrime[j] = false;
          }
       }
       int count = 0;
       for (int i = 2; i < n; i++) {
          if (isPrime[i]) count++;
       }
       return count;
    }

Summary:
The optimization tricks for determining if a number is Prime:
1. Check all n's factors from 2 to n - 1
2. Check until n/2, because n must not be divisible by the number greater than n/2
3. Check until sqrt(n). Because if n is dividible by some number p, then n = p * q, since p <= q, so p is up to sqrt(n). 

So the time complexity is O(sqrt(n)) to determine if a number is prime. 


The optimization tricks for count the number of primes less than n
1. If the current number is p, we only need to start from p^2, because 2*p, 3*p, 4*p, ..., has already been marked off. So we start from p^2, and p^2 + p, p^2 + 2p, ...
2. we terminate the loop condition at sqrt(n), because all non-primes >= sqrt(n) must have already been marked off. 

Friday, August 28, 2015

Leetcode: Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
Understand the problem:
The solution should handle the under cases:
1. If the val is the head, we need a dummy node.
2. If the val to be removed has multiple in consecutive. e.g.
dummy -> 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> null, and val = 1
So we need to iterate over all the elements to be removed until the next non-removed one.
3. If the val to be removed is at the tail. 

Code (Java):
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        
        ListNode p = dummy;
        
        while (p != null) {
            if (p.next != null && p.next.val == val) {
                ListNode q = p.next;
                while (q != null && q.val == val) {
                    q = q.next;
                }
                p.next = q;
            }
            p = p.next;
        }
        
        return dummy.next;
    }
}

Leetcode: Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Understand the problem:
We could reference this post:
http://blog.csdn.net/linhuanmars/article/details/23236995

Define two dp arrays, 
global[n.length][k + 1] and local[n.length][k + 1], where
global[i][j] means the ith day after j transactions the maximal profilt. 
local[i][j] means the transaction j must happen on today. and the maximal profits. 

Transit function:
global[i][j] = Math.max(local[i][j], global[i - 1][j]); // Today has transaction vs. today no transaction
local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);
where diff = prices[i] - prices[i - 1]. 

Return global[len - 1][k].

Code (Java):
public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[][] local = new int[prices.length][k + 1];
        int[][] global = new int[prices.length][k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(0, diff), local[i - 1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }
        
        return global[prices.length - 1][k];
    }
} 

O(k) space solution:
Since dp[i] only relies on dp[i - 1], we can reuse the dp array. 

Code (Java):
public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[] local = new int[k + 1];
        int[] global = new int[k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j > 0; j--) {
                local[j] = Math.max(global[j - 1] + Math.max(0, diff), local[j] + diff);
                global[j] = Math.max(local[j], global[j]);
            }
        }
        
        return global[k];
    }
}