Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int midVal = matrix[mid / n][mid % n];
            if (midVal == target) {
                return true;
            } else if (midVal > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

Note: O(log(m*n))

Share

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

public class Solution {
    public int[] plusOne(int[] digits) {
        if(digits==null||digits.length==0){
            return digits;
        }
        int index = digits.length-1;
        int carry = 1;
        int sum;
        while(index>=0 && carry==1){
            sum = digits[index]+carry;
            digits[index] = sum%10;
            carry = sum/10;
            index--;
        }
        if(carry==1){
            int[] newDigits = new int[digits.length+1];
            newDigits[0]=carry;
            for(int i=0;i<digits.length;i++){
                newDigits[i+1] = digits[i];
            }
            return newDigits;
        }
        return digits;
        
    }
}

Note: use a while loop here so that we don’t need to go through the entire array if it’s not necessary. It starts from the last index of the array and go backwards. If carry==1, then it will keep going, otherwise it will stop. After the traversing is done, it checks if the first digit==0 and handle that case.

Share

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

public class Solution {
 public void merge(int A[], int m, int B[], int n) {
   int index = m+n-1;
   while(index>=0 && m>0 && n>0){
     if(A[m-1]>=B[n-1]){
       A[index]=A[m-1];
       m--;
     }else{
       A[index]=B[n-1];
       n--;
     }
     index--;
   }
   if(n>0){
     for(int i=0;i<n;i++){
       A[i]=B[i];
     }
   }
 }
}

Share

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

public void setZeroes(int[][] matrix) {
        //to achieve constant space, we need to use the space of the first row and first col
        //to store information
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return;
        }
        
        //1. determine if the first row needs to be set zero because of itself
        //which means are there any zeros in the first row
        boolean zeroFirstRow = false;
        for(int i=0;i<matrix[0].length;i++){
            if(matrix[0][i]==0){
                zeroFirstRow=true;
                break;
            }
        }
        //2. determine if the first col needs to be set zero because of itself
        //which means are there any zeros in the first col
        boolean zeroFirstCol = false;
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][0]==0){
                zeroFirstCol=true;
                break;
            }
        }
        //3. then we can use the first row and first col to store the information of 
        //the rest elements
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //4. set the matrix to zero according to the information stored in the first row and first col
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[0][j]==0||matrix[i][0]==0){
                    matrix[i][j]=0;
                }    
            }
        }
        //set the first row
        if(zeroFirstRow){
            for(int i=0;i<matrix[0].length;i++){
                matrix[0][i]=0;
            }
        }
        //set the first col
        if(zeroFirstCol){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0]=0;
            }
        }
    }

Share

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

public int removeElement(int[] A, int elem) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A==null||A.length==0){
            return 0;
        }
        int end = A.length-1;
        int index = 0;
        while(index<=end){
            if(A[index]==elem){
                swap(A, index, end);
                end--;
            }else{
                index++;
            }            
        }
        return end+1;
    }
    
    public void swap(int[] A, int i, int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

Share

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

public void merge(int A[], int m, int B[], int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int runnerA = m-1;
        int runnerB = n-1;
        int runner = m+n-1;
        while(runnerA>=0 && runnerB>=0){
            A[runner] = Math.max(A[runnerA],B[runnerB]);
            runner--;
            if(A[runnerA]>=B[runnerB]){
                runnerA--;
            }else{
                runnerB--;
            }
        }   
        
        if(runnerB>=0){
            for(int i=0;i<=runnerB;i++){
                A[i]=B[i];
            }
        }
    }

Share

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

public ArrayList<String> anagrams(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> output = new ArrayList<String>();
        HashMap<String,ArrayList<String>> patterns = new HashMap<String,ArrayList<String>>();

        for(int i=0;i<strs.length;i++){
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sorted = new String(charArr);

            if(patterns.containsKey(sorted)){
                patterns.get(sorted).add(strs[i]);
            }else{
                ArrayList<String> newPattern = new ArrayList<String>();
                newPattern.add(strs[i]);
                patterns.put(sorted,newPattern);
            }
        }

        for(String str :patterns.keySet()){
            if(patterns.get(str).size()>1){
                output.addAll(patterns.get(str));
            }
        }
        return output;
    }

Analysis: Time complexity: O(n*mlgm)  (n is # of strings, m is the average length of each string) Space Complexity: O(n*m)

Share