Showing posts with label Array. Show all posts
Showing posts with label Array. Show all posts

Tuesday, January 27, 2015

Simple Best Time Stock

Question: Given an array, find the maximum difference between two array elements given the second element comes after the first.

Idea: Use a variable to remember the minimum showed up before.

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

Code:
 public class maxSub {  
      public maxSub()  
      {  
           int[] input1={1,2,3,4};  
           int[] input2={-5,1,6,17};  
           int[] input3={90,12,4,-11};  
           System.out.println(maxSubInArray(input1));  
           System.out.println(maxSubInArray(input2));  
           System.out.println(maxSubInArray(input3));  
      }  
      public int maxSubInArray(int[] A)  
      {  
           if(A.length<=1)  
                return 0;  
           int minNow=A[0];  
           int maxSubNow=Integer.MIN_VALUE;  
           for(int i=1;i<A.length;i++)  
           {  
                maxSubNow=Math.max(A[i]-minNow, maxSubNow);  
                minNow=Math.min(minNow,A[i]);  
           }  
           return maxSubNow;  
      }  
 }  

Closest Number Below (Binary Search)

Question: 
Given: array/list/whatever arr of integers, sorted (“people’s guesses”) target integer x (“actual price”)
Find the largest arr[i] <= x.

Idea: Binary Search.

Time: O(lgn) Space: O(1)

Code:
 public class ClosestNumber {  
      public ClosestNumber()  
      {  
           int[] input1={1};  
           int target1=6;  
           int[] input2={1,4};  
           int target2=2;  
           int[] input3={1,4,12};  
           int target3=8;  
           int[] input4={1, 13, 101,Integer.MAX_VALUE};  
           int target4=100;  
           System.out.println(binarySearch(input1,target1));  
           System.out.println(binarySearch(input2,target2));  
           System.out.println(binarySearch(input3,target3));  
           System.out.println(binarySearch(input4,target4));       
      }  
      //assume A!=empty  
      public int binarySearch(int[] A, int target)  
      {  
           int left=0;  
           int right=A.length-1;  
           while(left<=right)  
           {  
                int mid=(left+right)/2;  
                if(A[mid]==target)  
                     return target;  
                if(A[mid]<target)  
                     left=mid+1;  
                else  
                     right=mid-1;  
           }  
           return A[right];  
      }  
 }  

Sunday, January 25, 2015

Page Number

Question: A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurrences 'k' of certain digit 'd' in this string.
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occurs five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurrences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages

Idea: Brute force. Start from 1, accumulate the number of d's appearance. At the first accumulated appearance==k, update the lower bound; at the last appearance==k, update the upper bound.

Time: O(k) Space: O(1)

Code:
 public class PageNumber {  
      public PageNumber()  
      {  
           int[] test1=pageNumber(4,1);  
           printArray(test1);  
           int[] test2=pageNumber(4,0);  
           printArray(test2);  
      }  
      public void printArray(int[] array)  
      {  
           for(int i:array)  
           {  
                System.out.print(i);  
                System.out.print(' ');  
           }  
           System.out.println("\n");  
      }  
      public int[] pageNumber(int d,int k)  
      {  
           int[] result={Integer.MIN_VALUE,Integer.MIN_VALUE};  
           int i=1;  
           char target=(char)(d+'0');  
           int counter=0;  
           while(counter<=k)  
           {  
                String s=Integer.toString(i);  
                for(char c:s.toCharArray())  
                {  
                     if(c==target)  
                          counter+=1;  
                }  
                if(result[0]==Integer.MIN_VALUE&&counter==k)  
                     result[0]=i;  
                if(counter==k)  
                     result[1]=i;  
                i++;  
           }  
           return result;  
      }  
 }  

Monday, January 19, 2015

Gas Station (LeetCode Greedy)

Question: There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Idea: If the sum of the gas[] is larger than the sum of the cost[], the roundtrip can be fulfilled. However, the start point can not be anywhere, since partial of the trajectory may be quite "tough" (partial sum of cost> partial sum of gas). As said in Shelley's "Ode to the west wind", "If Winter comes, can Spring be far behind? ", we need to locate the end of the winter.

Start from a round point of the trip, we may face a series of continuous "tough" roads. However, since we know the round trip can be fulfilled, that means starting from the end of last "tough" roads we encountered, we can accomplish the whole trip, otherwise the whole trip can not be finished. This can be proved easily by contradiction.

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

Code:
 public class Solution {  
   public int canCompleteCircuit(int[] gas, int[] cost) {  
     int sum=0;  
     int total=0;  
     int breakPoint=-1;  
     for(int i=0;i<gas.length;i++)  
     {  
       sum+=gas[i]-cost[i];  
       total+=gas[i]-cost[i];  
       if(sum<0)  
       {  
         breakPoint=i;  
         sum=0;  
       }  
     }  
     if(total>=0)  
       return breakPoint+1;  
     else  
       return -1;  
   }  
 }  

Candy (LeetCode Greedy)

Question: There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

Idea: Greedy. Without loss of generality, let us assume the minimum assignment to each child is 0 (we can easily add N at the end to fulfill the 1 candy restriction). Then from left to right, if the ratings are increasing monotonically, add 1 candy per index, otherwise start again from 0 candy. Now if we only look from the left to the right, the problem is solved. However, the assignment should also be valid from right to left. So we need to update the assignment from right to left to fulfill the right to left requirement. After the left-to-right assignment and the right-to-left adjustment, accumulate the number of candies and add N to the final result, since each child should have at least 1 candy.

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

Code:
 public class Solution {  
   public int candy(int[] ratings) {  
     int n=ratings.length;  
     int[] count=new int[n];  
     for(int i=1;i<n;i++)  
     {  
       if(ratings[i]>ratings[i-1])  
         count[i]=count[i-1]+1;  
     }  
     for(int i=n-2;i>=0;i--)  
     {  
       if(ratings[i]>ratings[i+1]&&count[i]<=count[i+1])  
         count[i]=count[i+1]+1;  
     }  
     int sum=0;  
     for(int i=0;i<n;i++)  
       sum+=count[i];  
     return sum+n;  
   }  
 }  

Tuesday, January 13, 2015

ZigZag Conversion (LeetCode String)

Question: The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Idea: Brute force. Use an array of stringbuilders to record the characters to be appended to each row. Then accumulate the substrings row by row. Please take care the initialization stringbuilder array is kind of special.

Time: O(n) Space: O(n) (can be easily reduced to O(1) if we append all the substrings to the first stringbuilder[0], but I used another variable for easier understanding).

Code:
 public class Solution {  
   public String convert(String s, int nRows) {  
     StringBuilder[] builder=new StringBuilder[nRows];  
     for(int i=0;i<nRows;i++)  
       builder[i]=new StringBuilder();  
     int index=0;  
     while(index<s.length())  
     {  
       for(int i=0;i<nRows&&index<s.length();i++)  
       {  
         builder[i].append(s.charAt(index));  
         index++;  
       }  
       for(int i=nRows-2;i>0&&index<s.length();i--)  
       {  
         builder[i].append(s.charAt(index));  
         index++;  
       }  
     }  
     StringBuilder result=new StringBuilder();  
     for(int i=0;i<nRows;i++)  
       result=result.append(builder[i]);  
     return result.toString();  
   }  
 }  

Saturday, January 10, 2015

Read N Characters Given Read4 (LeetCode String)

Question: The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.

Idea: With two simple examples, we can understand this problem easily.
Example 1:  read 15 characters from a buffer with only 11 characters.
Run 1: read 4 characters
Run 2: read 4
Run 3: can only read 3, since there are only 3 characters left in the original data.

Example 2: read 15 characters from a buffer with 20 characters.
Run 1: read 4
Run 2: read 4
Run 3: read 4
Run 4: read 4, but only assign the first 3 to the destination buf[], since we only need to read 3 characters in this run.

So the characters read at the each run = Math.min(original data length - read in former runs==read4(buf), n-read in former runs).

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

Code:
 /* The read4 API is defined in the parent class Reader4.  
    int read4(char[] buf); */  
 public class Solution extends Reader4 {  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
   public int read(char[] buf, int n) {  
     int readBytes=0;  
     boolean eof=false;  
     while(readBytes<n&&eof==false)  
     {  
       char[] buffer=new char[4];  
       int read4Result=read4(buffer);  
       if(read4Result<4)  
         eof=true;  
       int actuallyRead=Math.min(n-readBytes,read4Result);  
       for(int i=0;i<actuallyRead;i++)  
         buf[readBytes+i]=buffer[i];  
       readBytes+=actuallyRead;  
     }  
     return readBytes;  
   }  
 }  

Sunday, January 4, 2015

Word Search (LeetCode Array)

Question: Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea: Depth-first search with backtracking. For each block, start to match the string one character by one character. Whenever a character board[i][j] is matched, mark it as board[i][j]='#' (representing it has been used) then go forward to board[i+1][j], board[i-1][j], board[i][j+1] and board[i][j-1]. If board[i][j] is out of boundary or board[next] does not match with string[next], return false. When all the characters of the string is matched, return true. When we roll back to the point board[i][j], do not forget to set it back to the original character, otherwise when we initial another search from the next point, e.g. board[i][j-1], the path can not go left, since it is '#'.

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

Code:
 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     if(board.length==0||board[0].length==0||board.length*board[0].length<word.length())  
       return false;  
     boolean result=false;  
     for(int i=0;i<board.length;i++)  
     {  
       for(int j=0;j<board[0].length;j++)  
       {  
         result=result||dfs(board,word,i,j,0);      
       }  
     }  
     return result;  
   }  
   public boolean dfs(char[][] board,String word,int startX,int startY,int curC)  
   {  
     if(curC==word.length())  
       return true;  
     if(startX>=board.length||startX<0)  
       return false;  
     if(startY>=board[0].length||startY<0)  
       return false;  
     if(board[startX][startY]!=word.charAt(curC))  
       return false;  
     char tmp=board[startX][startY];  
     board[startX][startY]='#';  
     boolean result=dfs(board,word,startX+1,startY,curC+1)||  
     dfs(board,word,startX-1,startY,curC+1)||  
     dfs(board,word,startX,startY+1,curC+1)||  
     dfs(board,word,startX,startY-1,curC+1);  
     board[startX][startY]=tmp;  
     return result;  
   }  
 }  


Unique Paths II (LeetCode Array)

Question: Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.

Idea: Dynamic programming. The number of uniques paths from point (i,j) to (m-1, n-1) is path[i][j]= (obs[i][j]==1)? 0 : path[i+1][j]+path[i][j+1]. We can not go right (go down) from the last column (the last row). So the last column is path[i][n-1]=(obs[i][n-1]==1)? 0: path[i+1][n-1]. The same for last row.

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

Code:
 public class Solution {  
   public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
     if(obstacleGrid.length==0||obstacleGrid[0].length==0)  
       return 0;  
     int[][] obs=obstacleGrid;  
     int m=obs.length;  
     int n=obs[0].length;  
     int[][] path=new int[m][n];  
     path[m-1][n-1]=(obs[m-1][n-1]==1)?0:1;  
     for(int j=n-2;j>=0;j--)  
       path[m-1][j]=(obs[m-1][j]==1)?0:path[m-1][j+1];  
     for(int i=m-2;i>=0;i--)  
       path[i][n-1]=(obs[i][n-1]==1)?0:path[i+1][n-1];  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
       {  
         path[i][j]=(obs[i][j]==1)?0:path[i+1][j]+path[i][j+1];  
       }  
     }  
     return path[0][0];  
   }  
 }  

Unique Paths (LeetCode Array)

Question: A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Idea: Dynamic programming. Since the robot can only go right or down, path[i][j]=path[i+1][j]+path[i][j+1]. For the last column(the last row), the robot has no choice but go down (go right), so the path[i][n-1] = 1( path[m-1][j]=1 ). The result is path[0][0].

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

Code:
 public class Solution {  
   public int uniquePaths(int m, int n) {  
     if(m==0||n==0)  
       return 0;  
     int[][] path=new int[m][n];  
     for(int j=n-1;j>=0;j--)  
       path[m-1][j]=1;  
     for(int i=m-1;i>=0;i--)  
       path[i][n-1]=1;  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
         path[i][j]=path[i+1][j]+path[i][j+1];  
     }  
     return path[0][0];  
   }  
 }  

Two Sum II - Input array is sorted (LeetCode Array)

Question: Given an array of integers that is already sorted in ascending order, 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

Idea: Since this array is sorted, we can use two pointers (left, right) to point to the start and the end of the array. If the sum is bigger than target, make the sum smaller by decrease the right pointer, otherwise increase the left pointer to make the sum bigger. The loop ends when the sum is equal to the target. Take care the output index is the original index+1.

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

Code:
 public class Solution {  
   public int[] twoSum(int[] numbers, int target) {  
     int left=0;  
     int right=numbers.length-1;  
     int[] result=new int[2];  
     while(left<right)  
     {  
       int sum=numbers[left]+numbers[right];  
       if(sum==target)  
       {  
         result[0]=left+1;  
         result[1]=right+1;  
         return result;  
       }  
       if(sum<target)  
         left++;  
       else  
         right--;  
     }  
     return result;  
   }  
 }  

Triangle (LeetCode Array)

Question: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Idea: Dynamic programming. We have the distance from (i,j) to the bottom is dis(i,j)=Math.min(dis(i+1, j),dis(i+1, j+1))+valueAt(i, j). So we can fill the table from bottom to up, but adding an empty (all 0's) row at the bottom. Each row i has i+1 numbers. This algorithm will cost O(n^2) space.
However, we need an O(n) space algorithm. We can observe that to fill the block dis(i, j), we need the results from dis(i+1, j) and dis(i+1, j+1); to fill the block dis(i, j+1), we only need the result of dis(i+1, j+1) and dis(i+1, j+2), where dis(i+1,j) is no longer needed. So we can reuse the space at dis(i+1, j) by store the result of dis(i, j) at the same place of dis(i+1, j). Then we just need an one-dimension array to cache the results.

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

Code:
 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     if(triangle.size()==0)  
       return 0;  
     int n=triangle.size();  
     int[] dis=new int[n+1];  
     for(int i=n-1;i>=0;i--)  
       for(int j=0;j<i+1;j++)  
         dis[j]=Math.min(dis[j],dis[j+1])+triangle.get(i).get(j);  
     return dis[0];  
   }  
 }  


Trapping Rain Water (LeetCode Array)

Question: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Idea: The water trapped at column i is Math.min(maxOnLeft, maxOnRight) - height[i]. So we only need to get the maxOnLeft and the maxOnRight of each column, then accumulate all the water levels. The column 0 and the column last can not trap any water.

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

Code:
 public class Solution {  
   public int trap(int[] A) {  
     if(A.length<=2)  
       return 0;  
     int[] left=new int[A.length];  
     int[] right=new int[A.length];  
     left[0]=0;  
     for(int i=1;i<A.length;i++)  
     {  
       left[i]=Math.max(left[i-1],A[i-1]);  
     }  
     right[A.length-1]=0;  
     for(int i=A.length-2;i>=0;i--)  
     {  
       right[i]=Math.max(right[i+1],A[i+1]);  
     }  
     int result=0;  
     for(int i=0;i<A.length;i++)  
       result+=Math.max(0,Math.min(left[i],right[i])-A[i]);  
     return result;  
   }  
 }  

Subsets II (LeetCode Array)

Question: Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Idea: Brute force. The only thing is to skip the adjacent duplicates.

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

Iterative Code:
 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     result.add(new ArrayList<Integer>());  
     Arrays.sort(num);  
     int preSize=0;  
     for(int i=0;i<num.length;i++)  
     {  
       int curSize=result.size();  
       for(int j=0;j<curSize;j++)  
       {  
         if(i==0||num[i]!=num[i-1]||j>=preSize)  
         {  
           List<Integer> oneRow=new ArrayList<Integer>(result.get(j));  
           oneRow.add(num[i]);  
           result.add(oneRow);  
         }  
       }  
       preSize=curSize;  
     }  
     return result;  
   }  
 }  

Recursive Code:
 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     Arrays.sort(num);  
     dfs(result,path,num,0);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result,List<Integer> path,int[] num,int start)  
   {  
     result.add(new ArrayList<Integer>(path));  
     for(int i=start;i<num.length;i++)  
     {  
       if(i!=start&&num[i]==num[i-1])  
         continue;  
       path.add(num[i]);  
       dfs(result,path,num,i+1);  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Saturday, January 3, 2015

Subsets (LeetCode Array)

Question: Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Idea: Brute force. There are many ways to list all the combinations. I only write the recursion method and the iterative method as following.

Time: O(2^n) Space: O(n) for recursive, O(1) for iterative.

Recursive Code:
 public class Solution {  
   public List<List<Integer>> subsets(int[] S) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(S==null||S.length==0)  
       return result;  
     Arrays.sort(S);  
     List<Integer> path=new ArrayList<Integer>();  
     dfs(result,path,S,0);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result, List<Integer> path, int[] S, int start)  
   {  
     result.add(new ArrayList<Integer>(path));  
     for(int i=start;i<S.length;i++)  
     {  
       path.add(S[i]);  
       dfs(result,path,S,i+1);  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Iterative Code:
 public class Solution {  
   public List<List<Integer>> subsets(int[] S) {  
     Arrays.sort(S);  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     result.add(new ArrayList<Integer>());  
     for(int i=0;i<S.length;i++)  
     {  
       int curSize=result.size();  
       for(int j=0;j<curSize;j++)  
       {  
         List<Integer> cur=new ArrayList<Integer>(result.get(j));  
         cur.add(S[i]);  
         result.add(cur);  
       }  
     }  
     return result;  
   }  
 }  

Spiral Matrix II (LeetCode Array)

Question: Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Idea: First initialize the n*n matrix. Then fill each of the spirals with a self-increasing counter (counter++). The top left corner of the i'th spiral is (0+i, 0+i), the bottom right corner of the i'th spiral is (n-1-i, n-1-i), where i starts from 0. There is a special case that the last spiral may be just one row or one column that the pointer should not come back.

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

Code:
 public class Solution {  
   public int[][] generateMatrix(int n) {  
     int[][] matrix=new int[n][n];  
     int counter=1;  
     int startI=0;  
     int startJ=0;  
     int endI=n-1;  
     int endJ=n-1;  
     while(startI<=endI&&startJ<=endJ)  
     {  
       if(startI==endI)  
       {  
         for(int j=startJ;j<=endJ;j++)  
           matrix[startI][j]=counter++;  
         break;  
       }  
       if(startJ==endJ)  
       {  
         for(int i=startI;i<=endI;i++)  
           matrix[i][startJ]=counter++;  
         break;  
       }  
       for(int j=startJ;j<endJ;j++)  
         matrix[startI][j]=counter++;  
       for(int i=startI;i<endI;i++)  
         matrix[i][endJ]=counter++;  
       for(int j=endJ;j>startJ;j--)  
         matrix[endI][j]=counter++;  
       for(int i=endI;i>startI;i--)  
         matrix[i][startJ]=counter++;  
       startI++;  
       startJ++;  
       endI--;  
       endJ--;  
     }  
     return matrix;  
   }  
 }  

Spiral Matrix (LeetCode Array)

Question: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

Idea: Brute force. The left up corner and the bottom right corner of the i'th spiral is (0+i, 0+i) and (m-1-i, n-1-i), where i starts from 0.
The only special case is when there is only one row or only one column, the spiral will not goes back to the start point.

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

Code:
 public class Solution {  
   public List<Integer> spiralOrder(int[][] matrix) {  
     List<Integer> result=new ArrayList<Integer>();  
     if(matrix.length==0||matrix[0].length==0)  
       return result;  
     int startI=0;  
     int startJ=0;  
     int endI=matrix.length-1;  
     int endJ=matrix[0].length-1;  
     while(startI<=endI&&startJ<=endJ)  
     {  
       if(startI==endI)  
       {  
         for(int j=startJ;j<=endJ;j++)  
           result.add(matrix[startI][j]);  
         break;  
       }  
       if(startJ==endJ)  
       {  
         for(int i=startI;i<=endI;i++)  
           result.add(matrix[i][startJ]);  
         break;  
       }  
       for(int j=startJ;j<=endJ;j++)  
         result.add(matrix[startI][j]);  
       for(int i=startI+1;i<=endI;i++)  
         result.add(matrix[i][endJ]);  
       for(int j=endJ-1;j>=startJ;j--)  
         result.add(matrix[endI][j]);  
       for(int i=endI-1;i>startI;i--)  
         result.add(matrix[i][startJ]);  
       startI++;  
       startJ++;  
       endI--;  
       endJ--;  
     }  
     return result;  
   }  
 }  

Sort Colors (LeetCode Array)

Question: 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.


Idea: Another way of thinking this problem is to move all the 0’s to the front of the array and move all the 2’s to the end of the array. So we use scan the array from left to right and use two pointers to remember the positions to move 0’s and 2’s to. Once we find a 0, move it to p0, p0++; once we find a 2, move it to p2, p2--; if it is 1, just go forward.
Since both p0 and the scanner, e.g. i, start from 0, they need to skip the 0’s in the front together. So when A[i]==0, both p0 and i increase 1.
Since the end of the original array may be 2, so the swap may swap two 2’s. Therefore i can not go forward in handling 2’s.

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

Code:
 <pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;;background-image:URL(https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_4ttYwMl_uJzWpFN_i6Br26Ka-UAuQurT862HR7CPovBTgDYQCBanMOLWbaQOGbH0WYA43qWxXoN4PqliLI_FkbKJCx7qwClhykGbIBdArsNfC-u2A40ptxiu2kvmgHmI8MShLaH4fbtl/s320/codebg.gif);padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> public class Solution {   
   public void sortColors(int[] A) {   
     int p0=0;   
     int p2=A.length-1;   
     int i=0;   
     while(i&lt;=p2)   
     {   
      switch(A[i])   
      {   
       case 0:    
        swap(A,i,p0);   
        p0++;   
        i++;   
        break;   
       case 1:    
        i++;   
        break;   
       case 2:   
        swap(A,i,p2);   
        p2--;   
        break;   
      }   
     }   
   }   
    public void swap(int[] A, int i, int j)   
    {   
       int tmp=A[i];   
       A[i]=A[j];   
       A[j]=tmp;   
    }   
  }   
 </code></pre>  

Set Matrix Zeroes (LeetCode Array)

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

Idea: First check whether the first row and the first column has zeros. Then use the first row and the first column as the buffer. If the matrix[i][j]==0 (i>=1, j>=1), set matrix[i][0] and matrix[0][j]=0. Then set each row i to zeros if matrix[i][0]==0, set each column j to zeros if matrix[0][j]==0. At last, set the first row and the first column to zeros according to the results of first step.

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

Code:
 public class Solution {  
   public void setZeroes(int[][] matrix) {  
     boolean rowHasZero=false;  
     boolean columnHasZero=false;  
     for(int i=0;i<matrix.length;i++)  
     {  
       if(matrix[i][0]==0)  
       {  
         columnHasZero=true;  
         break;  
       }  
     }  
     for(int j=0;j<matrix[0].length;j++)  
     {  
       if(matrix[0][j]==0)  
       {  
         rowHasZero=true;  
         break;  
       }  
     }  
     for(int i=1;i<matrix.length;i++)  
     {  
       for(int j=1;j<matrix[0].length;j++)  
       {  
         if(matrix[i][j]==0)  
         {  
           matrix[i][0]=0;  
           matrix[0][j]=0;  
         }  
       }  
     }  
     for(int i=1;i<matrix.length;i++)  
     {  
       for(int j=1;j<matrix[0].length;j++)  
       {  
         if(matrix[i][0]==0||matrix[0][j]==0)  
           matrix[i][j]=0;  
       }  
     }        
     if(rowHasZero)  
     {  
       for(int j=0;j<matrix[0].length;j++)  
         matrix[0][j]=0;  
     }  
     if(columnHasZero)  
     {  
       for(int i=0;i<matrix.length;i++)  
         matrix[i][0]=0;  
     }  
   }  
 }  

Search Insert Position (LeetCode Array)

Question: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Idea: Pure binary search. Since mid=floor((left+right)/2), the last element left in the binary array is where left is pointing at. Just insert it after the last left.

Time: O(lgn) Space: O(1)

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