Leetcode(Java)

1. Two Sum

class Solution {
  public int[] twoSum(int[] nums, int target) {
    
    for (int i = 0; i < num.length; i++) {
      for (int j = 0; j < num.length; j++) {
        int complement = target - nums[i];
        
        if (nums[j] == complement) {
          return new int[] { i, j };
        }
      }
    }
    
    throw new IllegalArgumentException("no match found");
  }
}

Complexity Analysis

Time complexity: O(n^2) we have a nested loop
Space complexity: O(1) we do not allocate any additional memory

```java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length;i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] {map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution"); 
    }
}

Complexity Analysis

* Time complexity:   O(n)		each lookup in the hash table only requires O(1) time
* Space complexity:  O(n)		we require additional space for the hash table which stores at most n

## [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/)

```java
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0; i<nums.length; i++) {
            int start = i+1, end = nums.length -1;
            while (start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if (Math.abs(target-sum)< Math.abs(target-ans))
                    ans = sum;
                if(sum>target)
                    end--;
                else if (sum<target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }
}

53. Maximum Subarray

// Brute Force
public int maxSubArray(int[] nums) {
  int n = nums.length;
  int res = Integer.MIN_VALUE;

  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      int sum = 0;
      for (int k = i; k < j; k++) {
        sum += nums[k];
      }
      res = Math.max(res, sum);
    }
  }
  return res;
}

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            res = Math.max(res, sum);
        }
    }
    return res;
}

//DP-1, T = O(n), S = O(n)
public int maxSubArray(int[] nums) {
  int N = num.length;
  int [] dp = new int[N+1];
  dp[0] = 0;
  int  res = Integer.MIN_VALUE;
  for (int k = 1; k <= N; k++) {
    dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
    res = Math.max(res, dp[k])
  }
  return res;
}

// DP-2, T = O(n), S = O(1)
public int maxSubArray(int[] nums) {
  int dp = 0;
  int res = Integer.MIN_VALUE;
  for (int k = 1; k <= nums.length; k++) {
    dp = Math.max(dp, 0) + nums[k-1];
    res = Math.max(res, dp);
  }
  return res;
}

// For each
public int maxSubArray(int[] nums) {
  int dp = 0;
  int res = Integer.MIN_VALUE;
  for (int n: nums) {
    dp = Math.max(dp, 0) + nums[k-1];
    res = Math.max(res, dp);
  }
  return res;
}

// Greedy Algorithm
public int maxSubArray(int[] nums) {
  int sum = 0;
  int res = Integer.MIN_VALUE;
  for (int n: nums) {
    if (sum < 0) {
      sum = 0;
    }
    sum += n;
    res = Math.max(res, sum);
  }
  return res;
}

35. Search Insert Position

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target){
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return l;
    }
}

[56. Merge Intervals] (https://leetcode.com/problems/merge-intervals/)

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

136. Single Number

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int i:nums){
            result ^= i;
        }
        
        return result;
    }
}

278. First Bad Version

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

165. Compare Version Numbers

 public static int compareVersion2(String version1, String version2) {
        String[] ver1 = version1.split("\\.");
        String[] ver2 = version2.split("\\.");

        int length1 = ver1.length;
        int length2 = ver2.length;
        int maxLen = Math.max(length1, length2);

        for (int i = 0; i < maxLen; i++) {
            int temp1 = 0, temp2 = 0;
            if (i < length1) {
                temp1 = Integer.parseInt(ver1[i]);
            }
            if (i < length2) {
                temp2 = Integer.parseInt(ver2[i]);
            }
            if (temp1 > temp2) {
                return 1;
            } else if (temp1 < temp2) {
                return -1;
            }
        }
        return 0;
    }

 public static int compareVersion3(String version1, String version2) {
        int temp1;
        int temp2;

        int i = 0;
        int j = 0;

        while (i < version1.length() || j < version2.length()) {
            temp1 = 0;
            temp2 = 0;
            //
            while (i < version1.length() && '.' != version1.charAt(i)) {
                temp1 = temp1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            i++;
            //
            while (j < version2.length() && '.' != version2.charAt(j)) {
                temp2 = temp2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            j++;
            //
            if (temp1 > temp2) {
                return 1;
            }
            if (temp1 < temp2) {
                return -1;
            }
        }
        return 0;
    }

374. Guess Number Higher or Lower

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 0;
        int right = n;
        
        while (left<=right) {
            int mid = left + (right - left) / 2;
            int res = guess(mid);
            if (res == 0) {
                return mid;
            } else if (res < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

392. Is Subsequence

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        
        for (int i = 0, j = 0; i<t.length(); i++) {
            if (t.charAt(i) == s.charAt(j)) j++;
            if (j == s.length()) return true;
        }
        return false;
    }
}

441. Arranging Coins

class Solution {
    public int arrangeCoins(int n) {
        long left = 0;
        long right = n;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long cur = mid * (mid + 1) / 2;
            if (cur == n ) {
                return (int) mid;
            }
            if (n < cur) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (int) right;
    }
}

704. Binary Search

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left<=right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid -1;
        }
        return -1;
    }
}

724. Find Pivot Index

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0, leftsum = 0;
        for (int x: nums) sum += x;
        for (int i = 0; i < nums.length; i++){
            if (leftsum == sum - leftsum - nums[i]) return i;
            leftsum += nums[i];
        } 
        return -1;
    }
}