Leetcode: Search a 2D Matrix

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

Leetcode: Plus One

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.

Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

One pass version:

```public class Solution {
public void sortColors(int[] A) {
int red = 0;
int blue = A.length-1;
int runner = 0;
while(runner<=blue){
switch(A[runner]){
case 0:
swap(A, red, runner);
red++;
runner++;
break;
case 1:
runner++;
break;
case 2:
swap(A, blue, runner);
blue--;
break;
}
}
}

public void swap(int[] A, int a, int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
}```

Leetcode: Merge Sorted Array

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 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];
}
}
}
}```

Leetcode: Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

```public int[] twoSum(int[] numbers, int target) {
//use hashmap to store <val,index> pairs of all the numbers
//in this algorithm, we assume all the numbers are different
//and we need to add one to the index as the final output as requried by this question
int[] output = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<numbers.length;i++){
map.put(numbers[i],i);
}
for(int i=0;i<numbers.length;i++){
int val = target-numbers[i];
if(map.containsKey(val)){
int index = map.get(val);
if(index!=i){
if(i<index){
output[0] = i+1;
output[1] = index+1;
}else{
output[0] = index+1;
output[1] = i+1;
}
return output;
}
}
}
return output;
}```

The time complexity is O(N). Since we only need constant time for each HashMap search operation.

Leetcode: Set Matrix Zeroes

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

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;
}
}
}```

Leetcode: Remove Element

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;
}```

Leetcode: Merge Sorted Array

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];
}
}
}```

Leetcode: Anagrams

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)){
}else{
ArrayList<String> newPattern = new ArrayList<String>();