cangoal

// https://leetcode.com/problems/letter-combinations-of-a-phone-number/

// Solution 1 : Iterative
public List<String> letterCombinations(String digits) {
        String[] maps = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ArrayList<String> ret = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return ret;
        }
        ret.add("");

cangoal

// Using String
public List<String> generateParenthesis(int n) {
        ArrayList<String> ret = new ArrayList<String>();
        if(n<1) return ret;
        String str = "";
        helper(n,n,ret, str);
        return ret;
    }
    
    private void helper(int left, int right, ArrayList<String> ret, String str){

cangoal

//
public int removeDuplicates(int[] nums) {
        if(nums == null) return 0;
        if(nums.length < 2) return nums.length;
        int k = 0, p = 1;
        while(p < nums.length){
            if(nums[k] != nums[p]){
                nums[++k] = nums[p];
            }
            p++;

cangoal

public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0) return 0;
        int k = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] != val){
                nums[k++] = nums[i];
            }
        }
        return k;
    }

cangoal

// Solution 1: 3 binary searches
public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return ret;
        int left = 0, right = nums.length - 1;
        int mid = (left + right) / 2;
        while(left < right){
            if(nums[mid] == target){
                ret[0] = mid;
                ret[1] = mid;

cangoal

//
public boolean canJump(int[] nums) {
    if(nums.length == 0) return false;
    int i=-1, reach = 0;
    while(i < reach){
        if(reach >= nums.length-1) return true;
        i++;
        reach = Math.max(reach, i+nums[i]);
    }
    return false;

cangoal

public int jump(int[] A) {
        // write your code here
        int reach = 0, step = 0, max = 0;
        for(int i=0; i<=reach; i++){
            if(reach >= A.length-1) return step;
            max = Math.max(max, A[i]+i);
            if(i == reach){
                reach = max;
                step++;
            }

cangoal

public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length==0) return 1;
        for(int i=0; i<nums.length; i++){
            while(nums[i]>0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]){
                int temp = nums[nums[i] -1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        

cangoal

// Solution 1 : recursive

public ArrayList<ArrayList<Integer>> permute(int[] num) {
        if(num==null || num.length==0) return null;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        helper(num, new boolean[num.length], new ArrayList<Integer>(), ret);
        return ret;
    }
    
    private void helper(int[] num, boolean[] used, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> ret){

cangoal

// Original solution -- recursive
public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.length == 0) return ret;
        Arrays.sort(nums);
        boolean[] flags = new boolean[nums.length];
        helper(ret, flags, nums, new ArrayList<Integer>(), 0);
        return ret;
    }