Range Sum Query - Immutable -- Leetcode

Question:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Answer:

public class NumMatrix {
    int[][] dp;
    int m;
    int n;
   
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m==0)return;
        n = matrix[0].length;
        if(m == 0 || n==0)return;
        dp = new int[m+1][n+1];
       
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
               dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];    
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1<0 || col1<0)return -1;
        return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Range Sum Query 2D - Mutable -- Leetcode

Question:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

1. The matrix is only modifiable by the update function.
2. You may assume the number of calls to update and sumRegion function is distributed evenly.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Answer: 

Binary indexed tree solution: Time:  O(log m * log n), Space: O(m * n)

public class NumMatrix {
    //Space: O(m * n)
    int[][] tree, arr;
    int m;
    int n;
   
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m==0)return;
        n = matrix[0].length;
        if(m == 0 || n==0)return;
        tree = new int[m+1][n+1];
        arr = new int[m][n];
       
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
               update(i, j, matrix[i][j]);    
            }
        }
    }

    //Time: O(logm * logn)
    public void update(int row, int col, int val) {
        int dif = val - arr[row][col];
        //update new value in element array!
        arr[row][col] = val;
        //update dif in BIT accumulated sume array!
        for(int i = row + 1; i <= m; i += i & (-i)){
            for(int j = col + 1; j <=n; j += j & (-j)){
                tree[i][j] += dif;
            }
        }
        return;
    }

    //Time: 4 * O(logm * logn) = O(logm * logn)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1<0 || col1<0)return -1;
        return getSum(row2, col2) - getSum(row2, col1-1) - getSum(row1-1, col2) + getSum(row1-1, col1-1);
    }
   
    public int getSum(int row, int col){
        int sum = 0;
        for(int i = row + 1; i > 0; i -= i & (-i)){
            for(int j = col + 1; j > 0; j -= j & (-j)){
                sum += tree[i][j];
            }
        }
        return sum;
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.update(1, 1, 10);
// numMatrix.sumRegion(1, 2, 3, 4);

Count of smaller numbers after self -- Leetcode

Question:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Answer:
Using Binary Indexed Tree(BIT), time: O(N * log N), space: O(1 -- range) array.  Better than naive solution O(N*N). 

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
       
        Integer min = Integer.MAX_VALUE;
        Integer max = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;++i){
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int range = max - min + 1;
        int[] tree = new int[range+1];

        for(int i = nums.length - 1; i >= 0; --i){
            int count = getCount(nums[i]-min, tree);
            res.add(0, count);
            addToCount(nums[i]-min+1, tree);
        }
        return res;
    }
   
    public int getCount(int i, int[] tree){
        int count = 0;
        while(i >= 1){
            count += tree[i];
            i -= i & (-i);
        }
        return count;
    }
   
    public void addToCount(int i, int[] tree){
        while(i <= tree.length-1){
            tree[i]++;
            i += i & (-i);
        }
    }
}

First Bad Version -- Leetcode

Question:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Answer:

Binary Search, Time: O(log n), Space:O(1)

/* 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 start = 1, end = n;

        

        while(start + 1 < end){

            int mid = start + (end - start) / 2;

            if(isBadVersion(mid)){

                end = mid;

            }else{

                start = mid;

            }

        }

        if(isBadVersion(start)){

            return start;

        }

        if(isBadVersion(end)){

            return end;

        }

        return -1;

    }

}

Pascal's Triangle -- Leetcode

Question:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Answer:

public class Solution {

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(numRows <= 0) return res;
       
        List<Integer> subres = new ArrayList<Integer>();
        subres.add(1);
        res.add(new ArrayList<Integer>(subres));
       
        for(int i = 1; i < numRows; ++i){
            for(int j = i-2; j >= 0; --j){
                subres.set(j+1, subres.get(j) + subres.get(j+1));
            }
            subres.add(1);
            res.add(new ArrayList<Integer>(subres));
        }
       
        return res;
    }
}

Pascal's Triangle II -- Leetcode

Question:

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Answer:
public class Solution {

    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        if（rowIndex <= 0) return res;

        res.add(1);

        for(int i = 1; i <= rowIndex; ++i){
            for(int j = i-2; j >= 0; --j){
                res.set(j+1, res.get(j) + res.get(j+1));
            }
            res.add(1);
        }
        return res;
    }
}

Anagram -- Leetcode

1. Valid Anagram:

Question:
https://leetcode.com/problems/valid-anagram/

Solution:

    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
       
        int[] charArr = new int[26];
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        for(int i=0; i<s.length(); ++i){
            charArr[chars[i]-'a']++;
        }
        for(int i=0; i<t.length(); ++i){
            if(--charArr[chart[i]-'a'] < 0){
                return false;
            }
        }
        return true;
    }


2. Group Anagram

Question:
https://leetcode.com/problems/anagrams/

Solution:
Method 1:
key = String (sorted)
value = List<String>
Group : HashMap< String, List<String> >

Time: O(n * mlog m)

    public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        //Time : n * logn
        Arrays.sort(strs);
        //Time : n * mlogm, Space : hmap : O(n)
        for(String s : strs){
            //sort s to get key, nlogn
            char[] charArr = s.toCharArray();
            Arrays.sort(charArr);
            String sortedStr = String.valueOf(charArr);
           
            if(!hmap.containsKey(sortedStr)){
                hmap.put(sortedStr, new ArrayList<String>());
            }
            hmap.get(sortedStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }



Method 2:
key = HashMap<Character, Integer>
value = List<String>
Group : HashMap< HashMap<Character, Integer>, List<String> >

Time: O(n * (m + 26))

public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        Arrays.sort(strs);
        //O(n)
        for(String s : strs){
            int[] charArr = new int[26];
            char[] chars = s.toCharArray();
            //Time : O(m + 26), Space : O(26) + O(n)
            for(int i=0; i<s.length(); ++i){
                charArr[chars[i]-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;++i){
               sb.append("" + i + charArr[i]);
            }
            String setStr = sb.toString();
           
            if(!hmap.containsKey(setStr)){
                hmap.put(setStr, new ArrayList<String>());
            }
            hmap.get(setStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }