Friday, July 24, 2015

Linked List Cycle | Leetcode

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

---

Solution: Maintain two pointers, slow and fast. Advance slow by one node at a time. Advance fast by two nodes at a time. If slow and fast ever points to the same node, then there is a cycle. If we reach the end of the linked list, then there is no cycle.
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Thursday, July 23, 2015

Word Break II | Leetcode

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

---

Solution: Maintain a list of dictionary words for each position in the string (breakWords[0 .. s.length()]). Iterate the string from first to last position. For each position i, find the list of dictionary words that could be formed and then add it to breakWords[i + word.length()]. This algorithm is similar to the Word Break algorithm, except that in Word Break, we use an array of booleans instead of an array of list of strings.

After we find the array of list of words, gather all the results by maintaining a current list of words going from end to start in the string s and then add each result as we traverse to the beginning of the string.
public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String>[] breakWords = new List[s.length() + 1];
        breakWords[s.length()] = new ArrayList<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && breakWords[i] == null) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (!word.equals(s.substring(i, endIndex))) continue;
                
                if (breakWords[endIndex] == null) {
                    breakWords[endIndex] = new ArrayList<>();
                }
                breakWords[endIndex].add(word);
            }
        }
        
        return getResults(new ArrayList<>(), breakWords, s.length(), new ArrayList<>());
    }
    
    private List<String> getResults(List<String> results, List<String>[] breakWords,
            int endIndex, List<String> list) {
        if (endIndex == 0 && list.size() > 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(list.size() - 1));
            for (int i = list.size() - 2; i >= 0; i--) {
                sb.append(' ').append(list.get(i));
            }
            results.add(sb.toString());
        } else if (breakWords[endIndex] != null) {
            for (String word: breakWords[endIndex]) {
                list.add(word);
                getResults(results, breakWords, endIndex - word.length(), list);
                list.remove(list.size() - 1);
            }
        }
        return results;
    }
}

Word Break | Leetcode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

---

Solution: Maintain an array of booleans (canBreak) to mark whether the particular position can be broken up into dictionary words. For example, "canBreak[i] = true" means that the string from characters 0 to (i - 1) can break into dictionary words.

Iterate through the string from first to last position. For each position i, go through all the dictionary words to check whether the word can contribute to the break. Let word be the dictionary word, and endIndex = i + word.length(). Check if "canBreak[i] = true" and "word.equals(s.substring(i, endIndex)) == true". If both conditions were true, then set canBreak[endIndex] = true. If endIndex == s.length(), then we know the whole word can be broken into dictionary words, so return true.
public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] canBreak = new boolean[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && !canBreak[i]) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (endIndex < s.length() && canBreak[endIndex]) continue;
                
                if (s.substring(i, endIndex).equals(word)) {
                    if (endIndex == s.length()) return true;
                    canBreak[endIndex] = true;
                }
            }
        }
        
        return false;
    }
}

Wednesday, July 22, 2015

Copy List with Random Pointer | Leetcode

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.

---

Solution: Iterate through the list from beginning to end, creating a clone node for each node in the list. Put all these clone nodes in a hashmap.

Iterate through the list again, this time linking up the next and random pointers of all the clone nodes.

Return the clone node of the head node as the answer.
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        Map<Integer, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        do {
            map.put(cur.label, new RandomListNode(cur.label));
            cur = cur.next;
        } while (cur != null);
        
        cur = head;
        do {
            RandomListNode node = map.get(cur.label);
            if (cur.next != null) {
                node.next = map.get(cur.next.label);
            }
            if (cur.random != null) {
                node.random = map.get(cur.random.label);
            }
            cur = cur.next;
        } while (cur != null);
        
        return map.get(head.label);
    }
}

Single Number II | Leetcode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

---

Solution: Count the number of one bits in the i-th bit position among all the numbers in the array (where i=0..31). If the count is not a multiple of 3, then set the i-th bit of the answer number as 1. When we have iterated from i=0 to i=31, then we would have obtained the complete answer number, so just return it.

Algorithm 1: Easy to Understand
public class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (1 << i);
            int bitCount = 0;
            for (int n: nums) {
                if ((n & bit) != 0) bitCount++;
            }
            if ((bitCount % 3) != 0) answer |= bit;
        }
        return answer;
    }
}

Algorithm 2: Probably No Need to Memorize (https://leetcode.com/discuss/43377/the-simplest-solution-ever-with-clear-explanation)
public class Solution {
    public int singleNumber(int[] nums) {
        int n0 = 0;
        int n1 = 0;
        for (int n: nums) {
            n0 = (n0 ^ n) & (~n1);
            n1 = (n1 ^ n) & (~n0);
        }
        return n0;
    }
}

Single Number | Leetcode

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

---

Solution: This is a trick question. Use XOR through all the numbers to get the answer.
public class Solution {
    public int singleNumber(int[] nums) {
        int n = nums[0];
        for (int i = 1; i < nums.length; i++) {
            n ^= nums[i];
        }
        return n;
    }
}

Tuesday, July 21, 2015

Candy | Leetcode

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:
  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

---

Solution: Create an array of all ones, indicating the number of candies we will give to each child.

Go from left to right. If the right neighbor (at index i) has a higher rating than the left neighbor (at index i - 1), then give the right neighbor one more candy than the left neighbor.

Go from right to left. If the left neighbor (at index i - 1) has a higher rating than the right neighbor (at index i), then give the left neighbor one more candy than the right neighbor. But also make sure that the left neighbor has at least as many candies as what we previously decided to give to this child so that we continue to satisfy the condition for going from left to right as well.

Sum up the number of candies for each child as the answer.
public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i - 1] < ratings[i]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        for (int i = ratings.length - 1; i >= 1; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candies[i - 1] = Math.max(candies[i - 1], candies[i] + 1);
            }
        }
        
        return IntStream.of(candies).sum();
    }
}