[LeetCode] -*** Two pointers / KMP / Rolling hash – Implement strStr()

Problem:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Knowledge Preparation:

1. strStr function. (Search String for Substring)  the strStr function searches within the string pointed to by s1 for the string pointed to by s2. It returns a pointer to the first occurrence in s1 of s2.

2.To make it easier, this problem is asking us to search the String ‘needle’ in the String ‘haystack’, and return the first occurrence of needle.

3. About corner case: strStr(Any String.””)  return 0;

Method 1: Brute Force

Use two pointers. If every character matches, then return the index, or continue to compare.

Several details:

1. Check the remaining length before comparison. It could significantly reduce the time.

2. First check if exceeding the length, then get the character. If the sequence is reversed, running time error (Out of boundary exception) may occur.

3. Do not forget corner case. strStr(Any String.””)  return 0;

Code for method 1:

public class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0 && haystack.length() == 0) return 0;
        if (needle == null  && haystack == null) return 0;
        if (needle == null || needle.length() == 0) return 0;

        if (haystack == null || haystack.length() == 0) return -1;

        int idx0 = 0; // record the starting index in haystack
        int idx1 = 0; // move through the haystack
        int idx2 = 0; // move throught the needle

        while (idx0 <= haystack.length()-needle.length()){
            // judging the length is very important! Or it won't pass
            idx1 = idx0;
            idx2 = 0;
            while (idx2 < needle.length() && idx1 < haystack.length() &&haystack.charAt(idx1) == needle.charAt(idx2)  ){
                idx1++;
                idx2++;
            }

            if (idx2 == needle.length()){
               return idx0;
            }else{
                idx0 ++;
            }
        }
        return -1;
    }
}

Another code for method 1:

The above code is not clear. To avoid dealing with edge cases separately, we could do the following:

public class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0;; i++){
            for (int j = 0;; j++){
                if (j == needle.length()) return i;
                if (i + j == haystack.length()) return -1;
                if (needle.charAt(j) != haystack.charAt(j+i)) break;
            }
        }
    }
}

Method 2: KMP method

KMP method is known to solve the problem of checking if one string is a substring of another one.

// This is the KMP solution
public class Solution {
    public int strStr(String haystack, String needle) {

        int i = 0;
        int hlength = haystack.length();
        int nlength = needle.length();

        if (nlength == 0) {
            return 0;
        } else {
            //get the prefix values for string: needle.
            int[] form = KMPform(needle);

            while (i <= hlength - nlength) {
                int j = 0;
                while (j < nlength) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        if (j == 0) {
                            i++;
                        } else {
                            i = i + j - form[j - 1] - 1;
                        }
                        break;
                    } else if (j == nlength - 1) {
                        return i;
                    }
                    j++;
                }
            }

            return -1;
        }
    }

    public int[] KMPform(String str) {
        int[] form = new int[str.length()];
        form[0] = -1;
        for (int i = 1; i < form.length; i++) {
            int index = form[i - 1];
            while (index >= 0 && str.charAt(i) != str.charAt(index + 1))
            {
                index = form[index];
            }
            if (str.charAt(i) == str.charAt(index + 1))
            {
                form[i] = index + 1;
            }
            else
            {
                form[i] = -1;
            }
        }
        return form;
    }

}

[LeetCode Java Solution] – sort/ two pointers/ merge- Merge k Sorted Lists

Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Method 1:

MergeSort. This is a very typical implementation for MergeSort by using array.

Code for method 1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return helper(lists, 0, lists.length-1);
    }
    
    public ListNode helper (ListNode[] lists, int l, int h){
        if (l < h){
             int mid = (l + h)/2;
             return merge(helper(lists, l, mid), helper(lists, mid+1, h));
        }
        return lists[l];
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }else{
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if (l1 != null){
            temp.next = l1;
        }
        if (l2 != null){
            temp.next = l2;
        }
        return dummy.next;
    }
}

Analysis for time complexity:

Suppose there are k lists, and there are n elements inside each list. The time complexity is O(nklogk).

Method 2:

Use heap. Suppose we have k lists, and for each list, there are at most n elements.

Maintain a list of k elements. And always remove the first element from the list. After removing an element, add the element after it to the heap.

Code for method 2:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10, new Comparator<ListNode>(){
            public int compare (ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
        
        for (int i = 0; i < lists.length; i++){
            ListNode temp = lists[i];
            if (temp != null){
                heap.offer(temp);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (heap.size() != 0){
            ListNode n = heap.poll();
            cur.next = n;
            cur = cur.next;
            if (n.next != null){
                heap.offer(n.next);
            }
        }
        return dummy.next;
    }
}

Analysis for time complexity:

We have to insert at most k*n nodes, and for each node to be in order in the heap, we need log(k) time (“Bottom Up Insertion”). So total time complexity is also knlog(k).

[LeetCode Java Solution] – Two Pointers / Math – Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Method:

1. How to add binary number?

From the right to left. If two digits add up to 1 or 0, just put it as 1 or 0. If the two digits add up to 2, make the digit 0, and carry 1. If the two digits add up to 3, make the digit 1, and carry 1.

2. Please pay attention to the while condition.

3. Don’t forget to check carry at last.

Code:

public class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1 ;
        int j = b.length() - 1 ;
        int c = 0;//
        String s = "";
        
        while (i >= 0 || j >= 0){
            int digit = 0;
            if (i >= 0){
                digit += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0){
                digit += b.charAt(j) - '0';
                j--;
            }
            if (c != 0){
                digit += c;
            }
            
            if (digit == 0){
                s = "0" + s;
                c = 0;
            }else if (digit == 1 ){
                s = 1 + s;
                c = 0;
            }else if (digit == 2){
                s = "0" + s;
                c = 1;
            }else if (digit == 3){
                s = "1" + s;
                c = 1;
            }
        }
        
        if (c != 0){
            s = "1" + s;
        }
        
        return s;
    }
}

Method 2:

We could also use the StringBuilder to store the result. The related methods are the following:

1.

StringBuilder

append(char c) Appends the string representation of the char argument to this sequence.

2.

StringBuilder

insert(int offset, char c) Inserts the string representation of the char argument into this sequence.

3.

StringBuilder

reverse() Causes this character sequence to be replaced by the reverse of the sequence.

[LeetCode Java Solution] – Array/ Two Pointers – Remove Element

Problem:

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.

Method 1: 

Swap the element with given value with the last element in the array. Keep track of the last element in the array.

Code for method 1:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0 ) return 0;
        
        int length = nums.length;// the index where to put the extra element
        int curIdx = 0; // the current index in the array
        
        
        while (curIdx < length ){
            if (nums[curIdx] == val ){
                nums[curIdx] = nums[length-1];
                length--;
            }else{
                curIdx ++;
            }
        }
        return length;
    }
}

Method 2:

Updating the array from left to right use two pointers. Only remain non-val elements.

Code for method 2:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int i = 0;// old array
        int j = 0;// new array
        
        while (i < nums.length){
            if (nums[i] != val){
                nums[j] = nums[i];
                j++;
            }
            i++;
        }
        return j;
    }
}

[LeetCode] -Two Pointers – Valid Palindrome

Problem:

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.

Method:

• Use two pointers, one at the head, one at the tail. Check equality towards the center.
• Remember ‘s.toLowerCase()’ has a return value (‘String’)
• We have to consider ’empty String’ : think it is a palindrome.
• Check if it alphanumeric.

Code:

public class Solution {
    public boolean isPalindrome(String s) {
       
        if (s == null ) return false;
        if (s.length() == 0) return true;
        
        s = s.toLowerCase(); // change all to lower case; remember 'toLowerCase()' has a return value
        int i = 0;
        int j = s.length() - 1;
        
        while (i < j){
            if (!(  (s.charAt(i) >= 'a' && s.charAt(i) <='z') || (s.charAt(i) >='0' && s.charAt(i) <= '9') )){
                i++;
                continue;
            }
            
            if (!(( s.charAt(j) >= 'a' && s.charAt(j) <='z') || (s.charAt(j) >='0' && s.charAt(j) <= '9'))){
                j--;
                continue;
            }
            
            if (s.charAt(i) == s.charAt(j)){
                i++;
                j--;
                continue;
            }
            
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

 

[LeetCode] – Two pointers / Merge- Merge Sorted Array

Problem:

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.

Method:

Similar as the problem : ‘Merge sorted list’. However, the difference is: we start from the end, and work backwards to compare elements.

Code:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n -1;

        while (i >= 0 && j >= 0){
            if (nums1[i] > nums2[j]){
                nums1[k] = nums1[i];
                i--;
                k--;
            }else{
                nums1[k] = nums2[j];
                j--;
                k--;
            }
        }
        
        while(i >= 0){
            nums1[k] = nums1[i];
            i--;
            k--;
        }
        while(j >= 0){
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

To make use of the property that this will be an in-place operation for nums1, we can simplify the code to be:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        
        while (k >= 0){
            if (j < 0 || (i >= 0 && nums1[i] > nums2[j])){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
    }
}

[LeetCode] – Sort/ Two pointers/Merge – Merge Two Sorted List

Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Method 1:

1. Use two pointers to move through the two lists. Compare and link the smaller one to the result list.

2. Use a dummy node to avoid choosing head for the new list.

3. To save space, do not have to create new node.

Code for method 1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
   
        ListNode dummy = new ListNode(1);
        ListNode temp0 = dummy;
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        
        while (temp1 != null && temp2 != null){
            if (temp1.val <= temp2.val){
              //  ListNode item = new ListNode(temp1.val);
              // to save space, do not have to create new object
                temp0.next = temp1;
                temp1 = temp1.next;
                temp0 = temp0.next;
            }else{
            //    ListNode item = new ListNode(temp2.val);
                temp0.next = temp2;
                temp2 = temp2.next;
                temp0 = temp0.next;
            }
        }
        if (temp1 != null){
            temp0.next = temp1;
        }
        if (temp2 != null){
            temp0.next = temp2;
        }
        return dummy.next;
    }
}

[LeetCode] – Two pointers – 3Sum

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Method:

If using hash table, its hard to deal with the duplicates, so we sort first and use the two pointers method.

The focus of this problem is reduce duplicates. Similar as the method we used in the problem “Two Sum”.

Note: 3 points to avoid duplicates (see the code below).

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length < 3) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++){
            if (i == 0 || nums[i] > nums[i-1]){ // avoid duplicate
                int j = i+1;
                int k = nums.length-1;
                while (j < k){
                    if (nums[i] + nums[j] + nums[k] == 0){
                        ArrayList<Integer> item = new ArrayList<Integer>();
                        item.add(nums[i]);
                        item.add(nums[j]);
                        item.add(nums[k]);
                        res.add(item);

                        while (j < k && nums[k-1] == nums[k])  k--; // avoid duplicate
                        while (j < k && nums[j+1] == nums[j])  j++; // avoid duplicate

                        j++;
                        k--;

                    }else if (nums[i] + nums[j] + nums[k] > 0){
                        k--;

                    }else {
                        j++;
                    }
                }
            }
        }
        return res;
    }
}

[LeetCode] – Sort / Two pointer – Two sum

Problem:

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

Method 1:

Use two for loops. Time complexity is O(n^2). Bad and slow.

Code for method 1:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int id1 = 0;
        int id2 = 0;
        
        for (id1 = 0; id1 < nums.length; id1++){
            for (id2 = id1 + 1; id2< nums.length; id2++){
                if (nums[id1] + nums[id2] == target){
                    res[0] = id1+1;
                    res[1] = id2+1;
                    return res;
                }
            }
        }
        
        return res;
    }
}

Method 2: by Hash Table

This is a very cool method!!!

Key: the numbers in the array

Value: index

When we encounter a value nums[i], we want to know if we already encountered (target-nums[i]). Hash table helps to quick look it up.

Time complexity: O(n)

Code for method 2: 

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 2 ) return res;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(target - nums[i])){
                map.put(nums[i],i);
            }else{
                res[0] = map.get(target - nums[i]) + 1 ;
                res[1] = ++i;
                break;
            }
        }
        return res;
    }
}

Method 3:

By using two pointers.

• Copy the array to a new array and sort it . Details: System.arraycopy(nums,0, sorted, 0,nums.length);  Arrays.sort(sorted)
• Have two points, one at the beginning, one at the end. And then move then towards the center of the array.
• Once find the two numbers adding up to target, go on to find their index in the original array.
• Sort the result array.

Time complexity:

O(nlogn)

Code for method 3:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // copy and sort the original array;
        int[] sorted = new int[nums.length];
        System.arraycopy(nums, 0, sorted, 0, nums.length);
        Arrays.sort(sorted);
        
        int first = 0;
        int second = nums.length-1;
        
        while (first < second){
            if (sorted[first] + sorted[second] < target){
                first ++;
                continue;  
            }else if (sorted[first] + sorted[second] > target){
                second --;
                continue;
            }else{
                break;
            }
        }
        // find the indexs for sorted[first] and sorted[second]
        int index1 = -1;// so that we knwo whether it has to be copyed or not
        int index2 = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == sorted[first] || nums[i] == sorted[second]){
                if (index1 == -1){
                    index1 = i+1;
                }else{
                    index2 = i+1;
                }
            }
        }
        // remeber to sort the result. 
        int[] res = {index1, index2};
        Arrays.sort(res);
        return res;
    }
}

[LeetCode] – Two Pointers – Remove Duplicates from Sorted Array II

Problem:

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Method:

The same as “Remove duplicates from sorted array”. We need two pointers as well as one counter to count how many elements already there. If counter > 2, we don’t add the element; if counter <= 2, we add it.

Code:

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length == 0 || A.length == 1) return A.length;
        
        int index = 0;  // indicating the real data
        int i;
        int num = 1;
        
        for (i = 1; i < A.length; i++){
            if (A[i] == A[index] && num < 2){
                index ++;
                A[index] = A[i];
                num ++;
            }else if (A[i] != A[index]){
                index ++;
                A[index] = A[i];
                num = 1;
            }else{
                num++;
            }
        }
        return index + 1;
    }
}