Posted on | In

Test cases

1
2
3
4
9
54494
9
171669

Solution 1: tle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String getPermutation(int n, int k) {
        if (n < 1 || k < 1) {
            return null;
        }
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        permuteHelper(result, sb, n, k);
        return result.get(k - 1).toString();
    }
    
    public void permuteHelper(List<String> result, 
                              StringBuilder sb, 
                              int n,
                              int k) {
        if (result.size() < k) {                       
          if (sb.length() == n) {
              result.add(sb.toString());
          } else {
              for (int i = 1; i <= n; i++) {
                  if (sb.indexOf(i + "") < 0) {
                      sb.append(i + "");
                      permuteHelper(result, sb, n);
                      sb.setLength(sb.length() - 1);
                  }
              }
          }
        }
    }
}

Posted on | In

Solution 1: accepted 1ms

In case we need to allow k duplicates, we only change the maximum of show to k. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int removeDuplicates(int[] nums) {
    if (nums.length == 0)
        return 0;
    int show = 1;
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            if (show == 2) {  // change to k
                continue;
            } else {
                nums[count] = nums[i];
                show++;
                count++;
            }
        } else {
            nums[count] = nums[i];
            show = 1;
            count++;
        } 
    }
    return count;
}

Posted on | In

Solution 1: accepted 18ms 80%

DFS. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<List<Integer>> combinationSum(int[] nums, int target) {
  List<List<Integer>> result = new ArrayList<List<Integer>>();
  List<Integer> list = new ArrayList<>();
  Arrays.sort(nums);
  comboHelper(result, list, nums, target, 0);
  return result;
}
public void comboHelper(List<List<Integer>> result, 
                      List<Integer> list, 
                      int[] nums, 
                      int remain,
                      int start) {
  if (remain == 0) {
      result.add(new ArrayList<Integer>(list));
  } else {
      // i = start will ignore the digits before so it won't repeat a sequence in different order
      for (int i = start; i < nums.length; i++) {  
          if (remain - nums[i] >= 0) { // exit condition
              list.add(nums[i]);
              comboHelper(result, list, nums, remain - nums[i], i);
              list.remove(list.size() - 1);
          } else { // since the array is sorted, no need to check the following numbers
              break;
          }
      }
  }
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[1,3,1,1,1]
3
[1,1,3,1]
3
[1,1,1, 3,1]
3
[]
5
[1,1,1,1,1]
1
[1,1,1,2,2,2]
1
[1,1,1,2,2,2]
2

Solution 1: accepted 1ms

How to modularize the problem:
rotatedarray

Time: O(n) // worst case, when all elements are the same

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean search(int[] nums, int target) {
    if (nums.length == 0) return false;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target)
            return true;
        if (nums[mid] > nums[hi]) {
            if (target >= nums[lo] && target < nums[mid])
                hi = mid;
            else
                lo = mid;
        } else if (nums[mid] < nums[hi]) {
            if (target <= nums[hi] && target > nums[mid])
                lo = mid;
            else
                hi = mid;
        } else {
            hi--;
        }
    }
    if (nums[lo] == target || nums[hi] == target) 
        return true;
    return false;
}

Posted on | In

Solution 1: accepted 1ms

The most standard binary search. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int lo = 1;
        int hi = n;
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            System.out.println(mid);
            if (guess(mid) > 0) {
                lo = mid;
            } else if (guess(mid) < 0) {
                hi = mid;
            } else {
                return mid;
            }
        }
        
        if (guess(lo) == 0) {
            return lo;
        } else if (guess(hi) == 0) {
            return hi;
        } else {
            return 0;
        }
    }
}

Posted on | In

Solution 1: accepted 5ms

Time: O(n) 2*(m+n)
Space: O(n) m+n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        int[] result = new int[set.size()];
        int k = 0;
        for (Integer n : set) {
            result[k++] = n;
        }
        return result;
    }
}

Posted on | In

Solution 1: accepted 18ms

Brute force. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int strStr(String haystack, String needle) {    
    if (haystack == null || needle == null) {
        return -1;
    }
    if (needle.length() == 0) {
        return 0;
    }
    int j = 0;
    for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
        for (j = 0; j < needle.length(); j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                break;
            }
        }
        if (j == needle.length()) {
            return i;
        }
    }
    return -1;
}

Solution 2: accepted 58%

KMP. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int strStr(String haystack, String needle) {    
        int hayLen = haystack.length(); 
        int nedLen = needle.length();   
        
        if (nedLen == 0) {
            return 0;
        }
        
        for(int i = 0; i < hayLen - nedLen + 1; i++) {
            int hay = i;
            int ned = 0;
            while (haystack.charAt(hay) == needle.charAt(ned)) {
                hay++;
                ned++;
                if (ned == nedLen)
                    return i;
                continue;
            }          
        }
        return -1;
    }
}

Neat but slower (28%) KMP. 

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int strStr(String haystack, String needle) {          
        for(int i = 0;; i++) {
            for (int j = 0;; j++ ) {
                if (j == needle.length()) return i;
                if (i + j >= haystack.length()) return -1;
                if (haystack.charAt(i + j) != needle.charAt(j)) break;  
            }          
        }
    }
}

Posted on | In

Solution 1: accepted 2ms

Iterative method.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        if (root == null) {
            return res;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode next = stack.pop();
            res.add(next.val);
            if (next.right != null) {
                stack.push(next.right);
            } 
            if (next.left != null) {
                stack.push(next.left);
            }
        }
        
        return res;
    }
}

Solution 2: accepted 2ms

Divide and conquer recursive solution. Not good for this simple question, since the method consumes extra time, but it’s good for some more complicated questions.
Time complexity is O(n) as we visit each node only once.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            // Divide
            List<Integer> left = preorderTraversal(root.left); // thread safe            
            List<Integer> right = preorderTraversal(root.right);
            
            // Conquer
            result.add(root.val);
            result.addAll(left); // O(n) complexity       
            result.addAll(right);            
        }
        return result;
    }
}

Solution 3: accepted 2ms

Naive recursive solution, trivial.
Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(result, root);
        return result;
    }
    
    private void traverse(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        traverse(result, root.left); // thread unsafe
        traverse(result, root.right);
    }
}

Posted on | In

Solution 1: accepted 4ms

Two pointers. Since the value could be duplicated, binary search is not the best shot. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        List<Integer> list = new ArrayList<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] result = new int[list.size()];
        int k = 0;
        for(Integer n : list) {
            result[k++] = n;
        }
        return result;
    }
}

Posted on | In

Solution 1: accepted 0ms

Binary. Conversion needed to gain precious result. For instance, for number 5, mid will be 2, int 5/2 = 2, which is not what we expect.
Time: O(logn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isPerfectSquare(int num) {
    if (num == 0) 
        return false;
    int lo = 0;
    int hi = num;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if ((double)mid == num / (double)mid) {
            return true;
        } else if ((double)mid < num / (double)mid){
            lo = mid;
        } else {
            hi = mid;
        }
    }
    if (lo * lo == num || hi * hi == num)
        return true;
    return false;
}