Saturday, June 20, 2015

Remove Duplicates from Sorted List | Leetcode

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

---

Solution: Iterate through the list. While the current node has the same value as the next node, remove the next node.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

Friday, June 19, 2015

Remove Duplicates from Sorted List II | Leetcode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

---

Solution: One tricky bit about this question is that when the head element is a duplicate, we have to take care to return the correct value of head, which is not the same one we get from the argument. A convenient way to do this is to create a node "pre" coming before head, so that we will return pre.next no matter whether we remove head or not.

To know whether the elements are duplicates or not, we have to take the next two elements. But you cannot make an element remove itself. The only way to remove an element is to have a reference to the previous element. Hence we use the condition "cur.next.val == cur.next.next.val" instead of "cur.val == cur.next.val" to perform this check.

When there are duplicates, do not advance the current pointer. Otherwise, just advance to the next element.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        
        ListNode cur = pre;
        while (cur.next != null && cur.next.next != null) {
            // If the next two nodes have the same value,
            // then remove them all with the same value.
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                cur.next = cur.next.next.next;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        
        return pre.next;
    }
}

Search in Rotated Sorted Array II | Leetcode

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

---

Solution: Use a modified form of binary search. The key is that we cannot say for sure whether a portion of the array is sorted or not if the first number is equal to the last number, i.e. nums[lo] == nums[hi]. Therefore, we have to say that the first number must be less than the last number (i.e. nums[lo] < nums[hi]) before we are sure that it is sorted. When we are not sure the portion is sorted, just reuse binary search on each half of the array portion from lo to hi.
public class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }
    
    public boolean search(int[] nums, int target, int lo, int hi) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int m = nums[mid];
            if (m == target) return true;
            
            if (nums[lo] < nums[hi]) {
                if (nums[lo] <= target && target < m) {
                    hi = mid - 1;
                } else if (m < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    return false;
                }
            } else {
                return search(nums, target, lo, mid - 1) || search(nums, target, mid + 1, hi);
            }
        }
        return false;
    }
}

Remove Duplicates from Sorted Array II | Leetcode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

---

Solution: Keep an index of the last element that you want to keep as part of the de-duplicated array. Keep the last seen character and also the count of the number of times the same character has been seen. Traverse through the array, moving valid numbers to the index of the last valid element. When done iterating, the current index is the length of the new sub-array.
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int lastNum = nums[0];
        int lastIndex = 1;
        for (int i = 1, count = 1; i < nums.length; i++) {
            if (nums[i] == lastNum) {
                if (++count > 2) continue;
            } else {
                count = 1;
                lastNum = nums[i];
            }
            nums[lastIndex++] = lastNum;
        }
        return lastIndex;
    }
}

Word Search | Leetcode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED" -> returns true
word = "SEE" -> returns true
word = "ABCB" -> returns false

---

Solution: Create a boolean matrix "seen" to mark whether each cell has been seen or not. A recursive function will then check for each character, checking the boolean matrix to avoid double-using each cell, and then self-recurse. When we reach the end of the word successfully, then we have found a match.

To reuse the board to mark seen is not a good idea because we do not have to restrict the possible range of input characters, unless this has otherwise been explicitly called out. Though you probably can reuse the board to pass the leetcode judge.

public class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] seen = new boolean[board.length][board[0].length];

        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                if (exists(board, seen, word, 0, y, x)) return true;
            }
        }
        return false;
    }
    
    private boolean exists(char[][] board, boolean[][] seen, String word, int start, int y, int x) {
        if (word.charAt(start) != board[y][x] || seen[y][x]) {
            return false;
        }
        
        if (start == word.length() - 1) return true;
        
        seen[y][x] = true;

        if (y > 0 && exists(board, seen, word, start + 1, y - 1, x)) {
            return true;
        }
        if (y < board.length - 1 && exists(board, seen, word, start + 1, y + 1, x)) {
            return true;
        }
        if (x > 0 && exists(board, seen, word, start + 1, y, x - 1)) {
            return true;
        }
        if (x < board[0].length - 1 && exists(board, seen, word, start + 1, y, x + 1)) {
            return true;
        }
        
        seen[y][x] = false;
        
        return false;
    }
}

Subsets | Leetcode

Given a set of distinct integers, nums, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
---

Solution: Sort the input array first. Initialize answer list. Then recurse starting from starting index 0. In each recursion, add given list as answer. Then loop through the input array starting from given index till the end. Collect each unique answer as you encounter them.

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();
        subsets(answer, new ArrayList<Integer>(nums.length), 0, nums);
        return answer;
    }
    
    private void subsets(List<List<Integer>> answer, List<Integer> list, int start, int[] nums) {
        answer.add(new ArrayList<Integer>(list));
        if (start >= nums.length) return;
        
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsets(answer, list, i + 1, nums);
            list.remove(list.size() - 1);
        }
    }
}

Thursday, June 18, 2015

Combinations | Leetcode

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
---

Solution: First initialize the answer list before calling the recursive function. In the recursive function, put the termination condition first. When we have the list size == k, then we know this result is ripe for reaping. Save this result and then return. Otherwise, loop from the given starting index of this recursive call. In each loop, add the first character at the given starting index, call itself recursively, and then remove the added character. Doing so will let you collect all the C(n,k) combinations. But unfortunately it is a bit hard to explain why!
public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> answer = new ArrayList<>();
        combine(answer, new ArrayList<Integer>(k), 1, n, k);
        return answer;
    }
    
    public void combine(List<List<Integer>> answer, List<Integer> list, int start, int n, int k) {
        if (list.size() == k) {
            answer.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = start; i <= n; i++) {
            list.add(i);
            combine(answer, list, i + 1, n, k);
            list.remove(list.size() - 1);
        }
    }
}