[2018-Interview] Longest Substring Without Repeating Characters

Original question: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

My answer:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int globalMaxLength = 1;
        int localMaxLength = 1;
        Map<Character, Integer> charIndex = new HashMap<Character, Integer>();
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() < 2) {
            return 1;
        }
        int l = 0;
        int r = 0;
        while (r < s.length()) {
            if (charIndex.containsKey(s.charAt(r)) && l <= charIndex.get(s.charAt(r))) {
                // l <= charIndex.get(s.charAt(r)), 

                // the opposite of l > charIndex.get(s.charAt(r)), 

                // which is good way to ignore the repeating char existed before
                globalMaxLength = Math.max(r - l, globalMaxLength);
                l = charIndex.get(s.charAt(r)) + 1;
            }
            charIndex.put(s.charAt(r), r);
            r ++;
        }
        globalMaxLength = Math.max(r - l, globalMaxLength);
        return globalMaxLength;
    }
}

[2018-Interview] Group Anagrams

Original question: https://leetcode.com/problems/group-anagrams/description/

My answer:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, List<String>> stringAnagramMap = new HashMap<String, List<String>>();

        for (int i = 0; i < strs.length; i ++) {
            
            char[] charsOfStr = strs[i].toCharArray();
            Arrays.sort(charsOfStr);
            String sortedChar = String.valueOf(charsOfStr);
            
            if (!stringAnagramMap.containsKey(sortedChar)) {
                List<String> singleResult = new ArrayList<String>();
                stringAnagramMap.put(sortedChar, singleResult);
            }
            stringAnagramMap.get(sortedChar).add(strs[i]);
        }
        for (List<String> value : stringAnagramMap.values()) {
            result.add(value);
        }
        return result;
    }
}

[2018-Interview] Set Matrix Zeroes

Original question: https://leetcode.com/problems/set-matrix-zeroes/description/

My answer:

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean originColumn = false; // if true, zero out the 0th column, used to avoid case where [i][0] is 0, while [0][0] is not
        boolean originRow = false; // if true, zero out the 0th row, used to avoid case where [0][j] is 0, while [0][0] is not
        if (matrix[0][0] == 0) {
            originColumn = true;
            originRow = true;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                // mark the index for 0s at row 0, and column 0
                if (matrix[i][j] == 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                        if (i == 0) {
                            originRow = true;
                        }
                        if (j == 0) {
                            originColumn = true;
                        }
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < matrix[0].length; j ++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < matrix[0].length; j ++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < matrix.length; i ++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (matrix[0][0] == 0) {
                if (originRow) {
                    for (int j = 1; j < matrix[0].length; j ++) {
                        matrix[0][j] = 0;
                    }                    
                }
                if (originColumn) {
                    for (int i = 1; i < matrix.length; i ++) {
                        matrix[i][0] = 0;
                    }                    
                }

        }
    }
}

[2018-Interview] 3Sum

Original question: https://leetcode.com/problems/3sum/description/

My answer:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Set<List<Integer>> resultSet = new HashSet<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 3; i ++) {
            List<List<Integer>> twoSum = twoSum(nums, i);
            if (twoSum.isEmpty()) {
                continue;
            }
            for (List<Integer> twoSumSingleResult : twoSum) {
                twoSumSingleResult.add(0, nums[i]);
                Collections.sort(twoSumSingleResult);
                resultSet.add(twoSumSingleResult);
            }
        }
        result.addAll(resultSet);
        return result;
    }
    
    private List<List<Integer>> twoSum(int[] nums, int startIndex) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int nextIndex = startIndex + 1;
        int target = -1 * nums[startIndex];
        // HashMap<Integer, Integer> numCount = new HashMap<Integer, Integer>();
        // for (int i = nextIndex; i < nums.length ; i ++) {
        //     Integer count = numCount.getOrDefault(nums[i], 0);
        //     count += 1;
        //     numCount.put(nums[i], count);
        // }
        // for (int i = nextIndex; i < nums.length ; i ++) {
        //     if (numCount.containsKey(target - nums[i]) && numCount.get(target - nums[i]) > 0) {
        //         if (numCount.get(target - nums[i]) == 1 && (target - nums[i]) == nums[i]) {
        //             // avoid the case where sum of itself can be matched to target
        //             continue;
        //         }
        //         Integer count = numCount.get(target - nums[i]);
        //         ArrayList<Integer> singleResult = new ArrayList<Integer>();
        //         singleResult.add(nums[i]);
        //         singleResult.add(target - nums[i]);
        //         result.add(singleResult);
        //         count --;
        //     }
        // }
        int l = nextIndex;
        int r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] == target) {
                ArrayList<Integer> singleResult = new ArrayList<Integer>();
                singleResult.add(nums[l]);
                singleResult.add(nums[r]);
                result.add(singleResult);
                l ++;
                r --;
                // important: skip the same element
                while(l<r&&nums[l]==nums[l-1])  
                    l++; 
                while(l<r&&nums[r]==nums[r+1])  
                    r--;
            } else if (nums[l] + nums[r] < target) {
                l ++;
            } else if (nums[l] + nums[r] > target) {
                r --;
            }
        }
        return result;
    }
}

[2018-Interview] Missing Number

Original question: https://leetcode.com/problems/missing-number/description/

My answer:

class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int i = 0; i < n; i++) {
            actualSum += nums[i];
        }
        return expectedSum - actualSum;
    }
}

Interesting solution: XOR. Do XOR for each value of array with 0....n, i.e. array index + nums.length.
The result number is the missing one.

Solution is from the article of this question: https://leetcode.com/articles/missing-number/

Because we know that nums contains $n$ numbers and that it is missing exactly one number on the range $[0..n-1]$, we know that $n$ definitely replaces the missing number in nums. Therefore, if we initialize an integer to $n$ and XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):

Index	0	1	2	3
Value	0	1	3	4

missing=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2=0∧0∧0∧0∧2=2$$\begin{array}{rl}missing& =4\wedge (0\wedge 0)\wedge (1\wedge 1)\wedge (2\wedge 3)\wedge (3\wedge 4)\\ & =(4\wedge 4)\wedge (0\wedge 0)\wedge (1\wedge 1)\wedge (3\wedge 3)\wedge 2\\ & =0\wedge 0\wedge 0\wedge 0\wedge 2\\ & =2\end{array}$$

class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

[2018-Interview] Pascal's Triangle

Original question: https://leetcode.com/problems/pascals-triangle/description/

My answer:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>(numRows);
        if (numRows < 1) {
            return result;
        }
        List<Integer> firstRow = new ArrayList<Integer>();
        firstRow.add(1);
        result.add(firstRow);
        List<Integer> lastRow = new ArrayList<Integer>();
        lastRow.addAll(firstRow);
        for (int i = 2; i <= numRows; i ++) {
            List<Integer> nextRow = helper(lastRow);
            result.add(nextRow);
            lastRow.clear();
            lastRow.addAll(nextRow);
        }
        return result;
    }
    
    private List<Integer> helper(List<Integer> lastRow) {
        List<Integer> nextRow = new ArrayList<Integer>(lastRow.size() + 1);
        nextRow.add(1);
        for (int i = 0; i < lastRow.size() - 1; i ++) {
            int nextValue = lastRow.get(i) + lastRow.get(i + 1);
            nextRow.add(nextValue);
        }
        nextRow.add(1);
        return nextRow;
    }
}