Two Pointer & Binary Search

(1) Substring with Concatenation of All Words (leetcode 30 sliding window)
(2) Remove Duplicates from sorted Array (leetcode 80)
(3) Minimum Window Substring (leetcode 76 sliding window)
(4) Minimum size subarry sum (leetcode 209)
(5) Longest substring without repeating characters (leetcode 3)
(6) LinkedList cycle II (leetcode 142)
(7) Find Duplicate Number (leetcode 287) try both fast/slow pointer and binary search
(8) 3 sum smaller (leetcode 259)
(9) implement strstr (leetcode 28) try both KMP

(10) Search in rotated array (leetcode 33) II (leetcode 81)
(11) Search 2D matrix (leetcode 74) II (leetcode 240)
(12) Median of two sorted Array (leetcode 4)
(13) longest increasing subsequence (leetcode 300)
(14) H-index II (275)
(15) Find minimum in rotated array (leetcode 153) II (leetcode 154)
(16) Wood cut (lintcode 183)

Leetcode 283 Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Solution 1: two pointer, move ahead non-zero value from j to i, when j reach n, set 0 to all element from i to end.

 public class Solution {  
   public void moveZeroes(int[] nums) {  
     int n=nums.length;  
     int i=0, j=0;  
     while (j<n) {  
       if (nums[j]==0) j++;  
       else nums[i++]=nums[j++];  
     }  
     while (i<n) nums[i++]=0;  
   }  
 }  

Leetcode 278 First Bad Version

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.

Solution 1: binary search.

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

Leetcode 277 Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Solution 1: At most only one celebrity. Use two pointer to search. If i know j, i is not celebrity; if i is not know j then j is not celebrity. When they meet, check the meeting element to be real celebrity or not.

 public class Solution extends Relation {  
   public int findCelebrity(int n) {  
     int i=0;  
     for (int j=1; j<n; j++) {  
       if (knows(i,j)) i=j;  
     }  
     for (int j=0; j<n; j++) {  
       if (i!=j && (knows(i,j) || !knows(j,i))) return -1;  
     }  
     return i;  
   }  
 }  

Leetcode 259 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

Solution 1: i iterate through the array, j, k is the typical two sum > or < target issue. O(n^2) solution.

 public class Solution {  
   public int threeSumSmaller(int[] nums, int target) {  
     int n=nums.length;  
     if (n<3) return 0;  
     Arrays.sort(nums);  
     int res=0;  
     for (int i=0; i<n; i++) {  
       int j=i+1, k=n-1;  
       while (j<k) {  
         int sum=nums[i]+nums[j]+nums[k];  
         if (sum<target) {  
           res+=k-j;  
           j++;  
         }  
         else k--;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 234 Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution 1: split by half, reverse 2nd half, can use two pointer to iterate, if find any difference return false.

 public class Solution {  
   public boolean isPalindrome(ListNode head) {  
     if (head==null) return true;  
     ListNode p=head;  
     int n=0;  
     while (p!=null) {  
       p=p.next;  
       n++;  
     }  
     p=head;  
     for (int i=0; i<(n-1)/2; i++) p=p.next;  
     ListNode t=p.next;  
     p.next=null;  
     ListNode r=null;  
     while (t!=null) {  
       ListNode temp=t.next;  
       t.next=r;  
       r=t;  
       t=temp;  
     }  
     p=head;  
     while (p!=null && r!=null) {  
       if (p.val!=r.val) return false;  
       p=p.next;  
       r=r.next;  
     }  
     return true;  
   }  
 }  

Leetcode 220 Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
Solution 1: compare to II, use Tree Map instead of Hashmap could solve it.

 public class Solution {  
   public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {  
     int n=nums.length, i=0;  
     if (t<0) return false;  
     TreeSet<Integer> set=new TreeSet<>();  
     for (int j=0; j<n; j++) {  
       if (j-i>k) set.remove(nums[i++]);  
       int lo=(nums[j]<Integer.MIN_VALUE+t)?Integer.MIN_VALUE:nums[j]-t;  
       int hi=(nums[j]>Integer.MAX_VALUE-t)?Integer.MAX_VALUE:nums[j]+t;  
       if (set.ceiling(lo)!=null && set.ceiling(lo)<=hi) return true;  
       set.add(nums[j]);  
     }  
     return false;  
   }  
 }  

Leetcode 219 Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.
Solution 1:  Use hash table and slide window

 public class Solution {  
   public boolean containsNearbyDuplicate(int[] nums, int k) {  
     Set<Integer> set=new HashSet<>();  
     int i=0;  
     for (int j=0; j<nums.length; j++) {  
       if (j-i>k) set.remove(nums[i++]);  
       if (set.contains(nums[j])) return true;  
       set.add(nums[j]);  
     }  
     return false;  
   }  
 }  

Leetcode 218 The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Solution 1: Use divide and conquer. Each time combine to sub skyline. When the sub skyline is just one building, it is just top left and bottom right point. The difficult part is how to combine the two sky line list.

 public class Solution {  
   public List<int[]> getSkyline(int[][] buildings) {  
     int n=buildings.length;  
     return getSkyline(buildings,0,n-1);  
   }  
   private List<int[]> getSkyline(int[][] buildings, int lo, int hi) {  
     List<int[]> res=new ArrayList<>();  
     if (lo>hi) return res;  
     else if (lo==hi) {  
       int[] p1=new int[]{buildings[lo][0],buildings[lo][2]};  
       int[] p2=new int[]{buildings[lo][1],0};  
       res.add(p1);  
       res.add(p2);  
     }  
     else {  
       int mid=lo+(hi-lo)/2;  
       List<int[]> l1=getSkyline(buildings,lo,mid);  
       List<int[]> l2=getSkyline(buildings,mid+1,hi);  
       int i=0, j=0;  
       int m=l1.size(), n=l2.size();  
       while (i<m || j<n) {  
         if (i>=m) res.add(l2.get(j++));  
         else if (j>=n) res.add(l1.get(i++));  
         else {  
           int x=0;  
           if (l1.get(i)[0]<l2.get(j)[0]) x=l1.get(i++)[0];  
           else if (l1.get(i)[0]>l2.get(j)[0]) x=l2.get(j++)[0];  
           else {  
             x=l1.get(i)[0];  
             i++;j++;  
           }  
           int y=getHight(l1,l2,i-1,j-1);  
           int size=res.size();  
           if (size==0 || y!=res.get(size-1)[1]) res.add(new int[]{x,y});  
         }  
       }  
     }  
     return res;  
   }  
   private int getHight(List<int[]> l1, List<int[]> l2, int i, int j) {  
     if (i<0) return l2.get(j)[1];  
     else if (j<0) return l1.get(i)[1];  
     else return Math.max(l1.get(i)[1],l2.get(j)[1]);  
   }  
 }  

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Solution 1: slide window.

 public class Solution {  
   public int minSubArrayLen(int s, int[] nums) {  
     int i=0, sum=0, n=nums.length;  
     int res=Integer.MAX_VALUE;  
     for (int j=0; j<n; j++) {  
       sum+=nums[j];  
       while (sum>=s) {  
         res=Math.min(res,j-i+1);  
         sum-=nums[i++];  
       }  
     }  
     if (res==Integer.MAX_VALUE) return 0;  
     return res;  
   }  
 }  

Leetcode 167 Two Sum II - Input array is sorted

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

Solution 1: simple two pointers.

 public class Solution {  
   public int[] twoSum(int[] numbers, int target) {  
     int i=0, j=numbers.length-1;  
     while (i<j) {  
       int sum=numbers[i]+numbers[j];  
       if (sum<target) i++;  
       else if (sum>target) j--;  
       else return new int[]{i+1,j+1};  
     }  
     return new int[]{0,0};  
   }  
 }  

Leetcode 165 Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Solution 1: Two pointers for s and t. compare the numbers before it reach '.' or end of string. If one pointer go beyond the end of string, use default value of 0.

 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     int i=0, j=0;  
     int m=version1.length(), n=version2.length();  
     while (i<m || j<n) {  
       int p1=i;  
       while (p1<m && version1.charAt(p1)!='.') p1++;  
       int num1=(p1>i)?Integer.valueOf(version1.substring(i,p1)):0;  
       int p2=j;  
       while (p2<n && version2.charAt(p2)!='.') p2++;  
       int num2=(p2>j)?Integer.valueOf(version2.substring(j,p2)):0;  
       if (num1>num2) return 1;  
       if (num1<num2) return -1;  
       i=++p1;  
       j=++p2;  
     }  
     return 0;  
   }  
 }  

Solution 2: Similar

 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     String[] v1=version1.split("\\.");  
     String[] v2=version2.split("\\.");  
     for (int i=0; i<v1.length || i<v2.length; i++) {  
       int num1=i<v1.length?Integer.valueOf(v1[i]):0;  
       int num2=i<v2.length?Integer.valueOf(v2[i]):0;  
       if (num1>num2) return 1;  
       else if (num1<num2) return -1;  
     }  
     return 0;  
   }  
 }  

Leetcode 161 One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.
Solution 1:  Move p1,p2 from start and q1,q2 from end. if related character is same between s and t. keep moving forward p1/p2 and moving back q1/q2. Details as below:

 public class Solution {  
   public boolean isOneEditDistance(String s, String t) {  
     int m=s.length(), n=t.length();  
     if (Math.abs(m-n)>1) return false;  
     int p1=0, p2=0;  
     while (p1<m && p2<n && s.charAt(p1)==t.charAt(p2)) {  
       p1++;   
       p2++;  
     }  
     p1--;   
     p2--;  
     int q1=m-1, q2=n-1;  
     while (q1>=0 && q2>=0 && s.charAt(q1)==t.charAt(q2)) {  
       q1--;   
       q2--;  
     }  
     q1++;   
     q2++;  
     if (q1-p1==2 && q2-p2==2) return true;  
     if (q1-p1==1 && q2-p2==2) return true;  
     if (q1-p1==2 && q2-p2==1) return true;  
     return false;  
   }  
 }  

Leetcode 160 Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Solution 1: calculate the length of A and B first. Move the pointer to be same length from end. keep moving the two pointer until they meet up. Return the node.

 public class Solution {  
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
     int c1=0, c2=0;  
     ListNode p=headA;  
     while (p!=null) {  
       p=p.next;  
       c1++;  
     }  
     p=headB;  
     while (p!=null) {  
       p=p.next;  
       c2++;  
     }  
     ListNode p1=headA, p2=headB;  
     while (c1>c2) {  
       p1=p1.next;  
       c1--;  
     }  
     while (c2>c1) {  
       p2=p2.next;  
       c2--;  
     }  
     while (p1!=null && p1!=p2) {  
       p1=p1.next;  
       p2=p2.next;  
     }  
     return p1;  
   }  
 }  

Leetcode 159 Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution 1: Use slid window. Maintain count number<2 and keep updating the result.

 public class Solution {  
   public int lengthOfLongestSubstringTwoDistinct(String s) {  
     int n=s.length();  
     int[] c=new int[256];  
     int i=0, count=0, res=0;  
     for (int j=0; j<n; j++) {  
       if (c[s.charAt(j)]++==0) count++;  
       if (count>2) {  
         while (--c[s.charAt(i++)]>0) continue;  
         count--;  
       }  
       res=Math.max(res,j-i+1);  
     }  
     return res;  
   }  
 }  

Leetcode 154 Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution 1: added corner case to deal with if nums[mid]==nums[hi], we can not reduce by half but only one. Also pay attention, it maybe not rotate any more by operation of lo++, in this case we simply return nums[lo].

 public class Solution {  
   public int findMin(int[] nums) {  
     int n=nums.length;  
     int lo=0, hi=n-1;  
     while (lo<hi) {  
       if (nums[lo]<nums[hi]) return nums[lo];//not rotated anymore  
       int mid=lo+(hi-lo)/2;  
       if (nums[mid]<nums[hi]) hi=mid;  
       else if (nums[mid]>nums[hi]) lo=mid+1;  
       else lo++;  
     }  
     return nums[lo];  
   }  
 }  

Leetcode 143 Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution 1: find 2nd half, reverse it then combine with 1st half.

 public class Solution {  
   public void reorderList(ListNode head) {  
     ListNode p1=head;  
     int n=0;  
     while (p1!=null) {p1=p1.next; n++;}  
     if (n<=2) return;  
     //cut to two half  
     p1=head;  
     for (int i=0; i<(n-1)/2; i++) p1=p1.next;  
     ListNode p2=p1.next;  
     p1.next=null;  
     //reverse 2nd half  
     p1=null;  
     while (p2!=null) {  
       ListNode temp=p2.next;  
       p2.next=p1;  
       p1=p2;  
       p2=temp;  
     }  
     //combine together  
     p2=head;  
     ListNode dummy=new ListNode(0);  
     ListNode p3=dummy;  
     while (p2!=null) {  
       p3.next=p2;  
       p3=p3.next;  
       p2=p2.next;  
       if (p1!=null) {  
         p3.next=p1;  
         p3=p3.next;  
         p1=p1.next;  
       }  
     }  
     dummy.next=null;  
   }  
 }  

Leetcode 142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Solution 1: use fast/slow pointers.

 public class Solution {  
   public ListNode detectCycle(ListNode head) {  
     ListNode fast=head, slow=head;  
     while (fast!=null && fast.next!=null) {  
       fast=fast.next.next;  
       slow=slow.next;  
       if (fast==slow) break;  
     }  
     if (fast==null || fast.next==null) return null;  
     ListNode p=head;  
     while (p!=slow) {  
       slow=slow.next;  
       p=p.next;  
     }  
     return p;  
   }  
 }  

Leetcode 141 Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Solution 1: use fast/slow pointers. If they meet, means there is cycle.

 public class Solution {  
   public boolean hasCycle(ListNode head) {  
     ListNode fast=head, slow=head;  
     while (fast!=null && fast.next!=null) {  
       fast=fast.next.next;  
       slow=slow.next;  
       if (fast==slow) return true;  
     }  
     return false;  
   }  
 }  

Leetcode 125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Solution 1: two pointer move from head and tail to compare. time complexity is O(n).

 public class Solution {  
   public boolean isPalindrome(String s) {  
     int n=s.length();  
     int i=0, j=n-1;  
     while (i<j) {  
       while (!Character.isLetterOrDigit(s.charAt(i)) && i<j) i++;  
       while (!Character.isLetterOrDigit(s.charAt(j)) && i<j) j--;  
       if (s.charAt(i)!=s.charAt(j) && Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j))) return false;  
       i++;  
       j--;  
     }  
     return true;  
   }  
 }