Generate Parentheses | Leetcode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

---

Solution: Maintain a running string and list of answers. Keep count of the number of open and close parentheses. If the number of open parentheses has not reached the target number n yet, then we can add an open parentheses. If the number of close parentheses is still less than the number of open parentheses, then we can add a close parentheses. When we reach the target (closeCount == n), then add the current string to the answer.

public class Solution {
    private StringBuilder sb = new StringBuilder();
    private List<String> answer = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        addParens(0, 0, n);
        return answer;
    }
    
    private void addParens(int openCount, int closeCount, int n) {
        if (closeCount == n) {
            answer.add(sb.toString());
            return;
        }
        if (openCount < n) {
            sb.append('(');
            addParens(openCount + 1, closeCount, n);
            sb.setLength(sb.length() - 1);
        }
        if (openCount > closeCount) {
            sb.append(')');
            addParens(openCount, closeCount + 1, n);
            sb.setLength(sb.length() - 1);
        }
    }
}

Merge Two Sorted Lists | Leetcode

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

---

Solution: First get the head node as we will return that at the end. Then go through the nodes in l1 and l2, always adding the smaller node first.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode head;
        if (l1.val < l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        
        ListNode curr = head;
        while (true) {
            if (l1 == null) {
                curr.next = l2;
                break;
            }
            if (l2 == null) {
                curr.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        return head;
    }
}

Valid Parentheses | Leetcode

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

---

Solution: Maintain a stack of brackets. When we see an opening bracket, push it to the stack. When we see a closing bracket, make sure the top of the stack has an opening bracket that matches that closing bracket.

public class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                continue;
            }
            
            char match;
            
            if (c == ')') {
                match = '(';
            } else if (c == '}') {
                match = '{';
            } else if (c == ']') {
                match = '[';
            } else {
                continue;
            }
            
            if (stack.isEmpty() || stack.pop() != match) {
                return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Remove Nth Node From End of List | Leetcode

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

---

Solution: Keep a node that skips n nodes first. Keep another node that starts from the head node. Advance both nodes at the same time until the first node reaches the end of the list. The second node will now point to the nth node. Remove the nth node and return the head of the list as the answer.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = head;
        
        for (int i = 0; i < n; i++) {
            node = node.next;
        }
        
        if (node == null) return head.next;

        node = node.next;        
        ListNode prev = head;
        
        while (node != null) {
            prev = prev.next;
            node = node.next;
        }
        
        prev.next = prev.next.next;
        return head;
    }
}

4Sum | Leetcode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

---

Solution: This is almost the same problem as 3Sum. For each element i, merge the answer with the 3Sum of elements i+1 to the end of the array.

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 3; i++) {
            // Avoid duplicates.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            List<List<Integer>> threeSums = threeSum(nums, i + 1, target - nums[i]);
            if (threeSums.isEmpty()) continue;
            
            for (List<Integer> list: threeSums) {
                List<Integer> tempList = new ArrayList<>();
                tempList.add(nums[i]);
                tempList.addAll(list);
                answer.add(tempList);
            }
        }
        
        return answer;
    }
    
    public List<List<Integer>> threeSum(int[] nums, int startIndex, int target) {
        List<List<Integer>> answer = new ArrayList<>();
        
        for (int i = startIndex; i < nums.length - 2; i++) {
            // Avoid duplicates.
            if (i > startIndex && nums[i] == nums[i - 1]) continue;
            
            int curTarget = target - nums[i];
            int first = i + 1;
            int last = nums.length - 1;
            
            while (first < last) {
                int sum = nums[first] + nums[last];
                
                if (sum == curTarget) {
                    answer.add(Arrays.asList(nums[i], nums[first], nums[last]));
                    first++;
                    last--;
                    
                    // Avoid duplicates.
                    while (first < last && nums[first] == nums[first - 1]) first++;
                    while (first < last && nums[last] == nums[last + 1]) last--;
                } else if (sum > curTarget) {
                    last--;
                } else {
                    first++;
                }
            }
        }
        
        return answer;
    }
}

Letter Combinations of a Phone Number | Leetcode

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

---

Solution: For each letter, take its list of corresponding characters, and append to each sub-list of strings in a double for-loop. Watch out for boundary conditions where the subList is empty or where the list of corresponding characters is empty.

public class Solution {
    private static final Map<Character, List<Character>> digitToLettersMap = new HashMap<>();
    
    static {
        digitToLettersMap.put('0', Collections.emptyList());
        digitToLettersMap.put('1', Collections.emptyList());
        digitToLettersMap.put('2', Arrays.asList('a', 'b', 'c'));
        digitToLettersMap.put('3', Arrays.asList('d', 'e', 'f'));
        digitToLettersMap.put('4', Arrays.asList('g', 'h', 'i'));
        digitToLettersMap.put('5', Arrays.asList('j', 'k', 'l'));
        digitToLettersMap.put('6', Arrays.asList('m', 'n', 'o'));
        digitToLettersMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
        digitToLettersMap.put('8', Arrays.asList('t', 'u', 'v'));
        digitToLettersMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
    }
    
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return Collections.emptyList();
        
        // Recurse on next substring.
        List<String> subList = letterCombinations(digits.substring(1));
        
        // Get the list of characters corresponding to the current digit.
        List<Character> chars = digitToLettersMap.get(digits.charAt(0));
        
        // If current list is empty, skip and return subList.
        if (chars.isEmpty()) return subList;
        
        List<String> answer = new ArrayList<>();
        
        if (subList.isEmpty()) {
            // If the subList is empty, just ignore it and return current
            // list of characters as a list of strings.
            for (char c: chars) {
                answer.add(Character.toString(c));
            }
        } else {
            StringBuilder sb = new StringBuilder();
        
            for (char c: chars) {
                sb.append(c);
                for (String s: subList) {
                    answer.add(sb.append(s).toString());
                    sb.setLength(1);
                }
                sb.setLength(0);
            }
        }
        
        return answer;
    }
}

3Sum Closest | Leetcode

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

---

Solution: Sort the input array. Iterate through the array. Keep track of the closest sum found so far. For each element i, go through elements i+1 to the last element in such a way that we try to get closer to target by advancing either the left or right pointer.

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // If you want to preserve the input, simply clone the array first before sorting.
        Arrays.sort(nums);
        
        int closestSum = nums[0] + nums[1] + nums[2];
        int closestDiff = Math.abs(closestSum - target);
        
        for (int i = 0; i < nums.length - 2; i++) {
            int n = nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = n + nums[left] + nums[right];
                if (sum == target) return sum;
                
                int diff = Math.abs(target - sum);
                if (diff < closestDiff) {
                    closestSum = sum;
                    closestDiff = diff;
                }
                
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closestSum;
    }
}