Posted on | In

Solution 1: accepted 3ms

DP.
Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                max = Math.max(max, prices[i] - prices[i-1]);
                prices[i] = prices[i-1];
            }   
        }
        return max;
    }
}

Posted on | In

Test cases

1
2
3
[[-10]]
[[1],[3,4],[2,3,4]]
[ [2], [3,4], [6,5,7], [4,1,8,3]]

Solution 1: accepted 11ms

DP
Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
    for(int i = 1; i < triangle.size(); i++) {
        ArrayList<Integer> row = (ArrayList)triangle.get(i);            
        ArrayList<Integer> lastRow = (ArrayList)triangle.get(i-1);
        for(int j = 0; j < row.size(); j++) {
            if (j == 0) {
                row.set(j, row.get(j) + lastRow.get(0));
            } else if (j == row.size() - 1) {
                row.set(j, row.get(j) + lastRow.get(lastRow.size()-1));
            } else {
                row.set(j, row.get(j) + Math.min(lastRow.get(j-1), lastRow.get(j)));
            }
        }
    }
    int minimum = Integer.MAX_VALUE;
    for(int i: triangle.get(triangle.size()-1)) {
        minimum = Math.min(minimum, i);
    }
    return minimum;
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
[1]
0
[1]
1
[]
5
[1,3]
3

Solution 1: 14ms

Binary solution.
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
20
21
22
23
24
25
26
27
28
29
public int search(int[] nums, int target) {
    if(nums.length == 1) return target == nums[0]? 0 : -1;      
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) { // "=" for case nums.length == 1
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        // if the left side is sorted
        if (nums[start] <= nums[mid]) { // "=" for case nums.length == 1 or 2
            // if the target is also on the left side
            if (target < nums[mid] && target >= nums[start]) 
                end = mid - 1;
            // if the target is on the right side
            else 
                start = mid + 1;
        // if the right side is sorted
        } else if (nums[mid] <= nums[end]) {
            // if the target is also on the right side
            if (target > nums[mid] && target <= nums[end]) 
                start = mid + 1;
            // if the target is on the left side
            else 
                end = mid - 1;
        } else // problems with the given array
            return -1;
    }
    return -1;
}
Alternative
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
public int search(int[] nums, int target) {
    if (nums.length == 0) return -1;
    if (nums.length == 1) 
        return target == nums[0]? 0 : -1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) 
            return mid;
        if (nums[mid] > nums[lo]) {
            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 {
            return -1;
        }
    }
    if (nums[lo] == target) return lo;
    if (nums[hi] == target) return hi;
    return -1;
}

Posted on | In

Solution 1: accepted 237ms

Super slow! too much operations!

Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    List<Integer> dic = new ArrayList<>();
    for (int i : nums) {
        if (!dic.contains(i))
            dic.add(i);
        else 
            dic.remove(Integer.valueOf(i));
    }
    return dic.get(0);
}

Solution 2: accepted 17ms

Though hashSet is more efficient, we can do better.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    HashSet<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (!set.contains(i))
            set.add(i);
        else 
            set.remove(Integer.valueOf(i));
    }
    int result = 0;
    for (int j: set) {
        result += j;
    }
    return result;
}

Solution 3: accepted 1ms

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

1
2
3
4
5
6
7
8
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    int result = 0;
    for (int i : nums) {
        result = result ^ i;
    }
    return result;
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
"0P"
"ab"
",."
",a,"
",aa."
""
"a"
"bab"
"baab"
"babb"

Solution 1: accepted 10ms

Two pointers. 

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
public boolean isPalindrome(String s) {
    s = s.toLowerCase();
    int l = 0;
    int r = s.length() - 1;
    while (l < r) {
        char lc = s.charAt(l);
        char rc = s.charAt(r);
        if (lc < 48 || (57 < lc && lc < 97) || lc > 122) {
            l++;
            continue;
        }
        if (rc < 48 || (57 < rc && rc < 97) || rc > 122) {
            r--;
            continue;
        }
        if (lc != rc) {
            System.out.println(lc + " " + rc);
            return false;
        } else {
            l++;
            r--;
        } 
    }
    if(l < r && s.charAt(l) != s.charAt(r)) // two left in the middle
        return false;
    return true;
}

Improved to 8ms using Character functions.

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 boolean isPalindrome(String s) {
    int l = 0;
    int r = s.length() - 1;
    while (l < r) {
        char lc = s.charAt(l);
        char rc = s.charAt(r);
        if (!Character.isLetterOrDigit(lc)) {
            l++;
            continue;
        }
        if (!Character.isLetterOrDigit(rc)) {
            r--;
            continue;
        }
        if (Character.toLowerCase(lc) != Character.toLowerCase(rc)) {
            return false;
        } else {
            l++;
            r--;
        } 
    }
    if(l < r && s.charAt(l) != s.charAt(r)) // two left in the middle
        return false;
    return true;
}

Posted on | In

Test cases

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

Solution 1: accepted 7ms

Binary search with wildcard while (lo + 1 < hi) plus final conditions.

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
public int[] searchRange(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    if (hi < 0) return new int[] {-1, -1};
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) {
            hi = mid;
        } else if (nums[mid] < target) {
            lo = mid;
        } else {
            if (nums[lo] != target) {
                lo++;
            } else if (nums[hi] != target) {
                hi--;
            } else {
                return new int[] {lo, hi};
            }
        }
    }
    if (nums[lo] == target && nums[hi] == target)
        return new int[] {lo, hi};
    if (nums[lo] == target)
        return new int[] {lo, lo};
    else if (nums[hi] == target)
        return new int[] {hi, hi};
    else
        return new int[] {-1, -1};
}

Alternative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] searchRange(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) {
            hi = mid - 1;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            if (nums[lo] != target) {
                lo++;
            } else if (nums[hi] != target) {
                hi--;
            } else {
                return new int[] {lo, hi};
            }
        }
    }
    return new int[] {-1, -1};
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
"hello"
[]
"leetcode"
["leet","code"]
"cars"
["car", "ca", "rs"]
"aaaaaaa"
["aaaa", "aaa"]
"y"
["ye"]

Solution 1: accepted 13ms

DP. Still need to look back.
Time: O(n^3), two for loop and s.substring()
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean wordBreak(String s, List<String> wordDict) {
  int len = s.length();
  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;
  for(int i = 1; i <= len; i++) {
    for(int j = 0; j < i; j++) {
      if (dp[j] && wordDict.contains(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[len];
}

Solution 2

Based on the list. We could use this one if the list is very long, since solution 1 needs to iterate the entire list all the time.

Time: O(n^2)
Space: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean wordBreak(String s, List<String> wordDict) {
    int len = s.length();
    boolean[] dp = new boolean[s.length()+1];
    dp[0] = true;
    for (int i = 1; i <= len; i++){
        for (String str : wordDict){
            if (str.length() <= i){ // so that str could be a possible solution
                if (dp[i - str.length()]){ // the head has to be true
                    if (s.substring(i-str.length(), i).equals(str)){ // verify whether the tail is equal to str
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
    }
    return dp[len];
}

Posted on | In

Solution 1: accepted 7ms

Normal iteration.
Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
public int searchInsert(int[] nums, int target) {
    int prev = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target)
            return i;
        else if (target > prev && target < nums[i])
            return i; 
    }
    return nums.length;
}

Solution 2: accepted 7ms

Binary search.
Time: O(logn)
Space: O(1)

Posted on | In

We only need to make sure that the board is valid. The worst case is O(n^2) and we will surely come up with a better solution.

Solution 1: accepted

Space for speed. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.add(board[j][i]))
                return false;
            int RowIndex = 3*(i/3);
            int ColIndex = 3*(i%3);
            if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                return false;
        }
    }
    return true;
}

Posted on | In

Solution 1: accepted

This is a hard one. 

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 class Solution {
    public String countAndSay(int n) {
	    	StringBuilder curr=new StringBuilder("1");
	    	StringBuilder prev;
	    	int count;
	    	char say;
	        for (int i=1;i<n;i++){
	        	prev=curr;
	 	        curr=new StringBuilder();       
	 	        count=1;
	 	        say=prev.charAt(0);
	 	        
	 	        for (int j=1,len=prev.length();j<len;j++){
	 	        	if (prev.charAt(j)!=say){
	 	        		curr.append(count).append(say);
	 	        		count=1;
	 	        		say=prev.charAt(j);
	 	        	}
	 	        	else count++;
	 	        }
	 	        curr.append(count).append(say);
	        }	       	        
	        return curr.toString();
        
    }
}