Leetcode 16: 3Sum Closest

Problem: 

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 

For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Analysis:

This problem is similar to 3Sum, instead we have to track the minimum gap during the process. The process of doing 3sum is the same:

Step 1: Sort the given array from low to high. 

Step 2: Get the sum of three different elements each time by using three pointers

           P1: traverse the array from the first element to the end-2. For each P1, another pointer P2                     points to the next element of P1 while the third pointer P3  points to the last element. 

Step 3: For each summation, keep tracking the minimum gap between the summation and the target,             and update the 

You may wonder why the three pointer algorithm achieves the minimum running time. The reason is that the first step make sure the each time, P1 points to a different value so that the combination of P1, P2 and P3 (P1<P2<P3) will never be traversed twice. Also,  you can consider this problem as a problem selecting three different elements from an array and then return the combinations.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num==null || num.length<3){
            return -1;
        }
        int gap=Integer.MAX_VALUE;
        int temp=-1;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int j=i+1;
            int k=num.length-1;
            while(j<k){
                int sum=num[i]+num[j]+num[k];
                if(Math.abs(target-sum)<gap){
                    gap=Math.abs(target-sum);
                    temp=sum;
                }
                if(sum<target){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return temp;
    }
}

Leetcode 15: 3 sum

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)

Analysis:
The following solution is to first sort the array and then for each element, we continue to check the larger ones using two pointers and move them accordingly.

Also, as the array could contain duplicated elements, we need to find a way to filter out the same solution.

Code:

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> ret=new ArrayList<List<Integer>>();
        if(num==null||num.length<3){
            return ret;
        }
        Arrays.sort(num);
        Set<String> set=new HashSet<String>();
        for(int i=0;i<num.length;i++){
            int j=i+1;
            int k=num.length-1;
            while(j<k){
                if(num[i]+num[j]+num[k]==0){
                    set.add(tsort(num[i],num[j],num[k]));
                    j++;
                    k--;
                }else if(num[i]+num[j]+num[k]>0){
                    k--;
                }else{
                    j++;
                }
            }
        }
        for(String str:set){
            List<Integer> list=new ArrayList<Integer>();
            for(String val:str.split("_")){
                list.add(Integer.parseInt(val));
            }
            ret.add(list);
        }
        return ret;
    }
    private String tsort(int i,int j,int k){
        int min=Math.min(i,Math.min(j,k));
        int max=Math.max(i,Math.max(j,k));
        int mid=(i+j+k)-min-max;
        return min+"_"+mid+"_"+max;
    }
}

Leetcode 1: 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

Analysis:
If we add two different elements in the array together and then compare each sum with the target, we will get a O(n^2) algorithm. However, if we change the expression A[i]+A[j]=target to A[j]=target-A[i],  our problem becomes search whether target-A[i] also exists in the array.

Code:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if(numbers==null || numbers.length<2){
            return null;
        }
        Map<Integer,Integer> map=new HashMap<Integer,Integer>(numbers.length);
        int ret[]=new int[2];
        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) &&map.get(val)>i){
                ret[0]=i+1;
                ret[1]=map.get(val)+1;
                return ret;
            }
        }
        return null;
        
    }
}

Leetcode 128: Longest Consecutive Sequence

Problem:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Analysis:

 The idea is to select one element first and then search larger consecutive ones and smaller ones. In this process, we need a map to record whether an integer exists or not and skip elements we have visited before.

Code:

public class Solution {
    public int longestConsecutive(int[] num) {
        Map<Integer,Boolean> map=new HashMap<Integer,Boolean>();
        for(int i=0;i<num.length;i++){
            map.put(num[i],true);
        }
        int maxLen=Integer.MIN_VALUE;
        for(int i=0;i<num.length;i++){
            if(map.get(num[i])){//not visited
                int val=num[i];
                int len=1;
                while(map.containsKey(--val)){
                    len++;
                    map.put(val,false);
                }
                val=num[i];
                while(map.containsKey(++val)){
                    len++;
                    map.put(val,false);
                }
                if(len>maxLen){
                    maxLen=len;
                }
            }
        }
        return maxLen;
    }
}

Leetcode 154: Find Minimum in Rotated Sorted Array II

Problem:

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.

Analysis:

Based on the previous analysis of Leetcode 154, we just need to specify the action if mid equals
to the left.
Leetcode 154: Find Minimum in Rotated Sorted Array

Code:

public class Solution {

   public int findMin(int[] num) {
       int left=0;
       int right=num.length-1;
       int min=Integer.MAX_VALUE;
       while(left<=right){
           int mid=(left+right)/2;
           min=Math.min(min,num[mid]);
           if(num[left]<num[mid]){ //A[left..mid] is sorted
               min=Math.min(min,num[left]);
               left=mid+1;
           }else if(num[left]>num[mid]){ //A[mid..right] is sorted
               right=mid-1;
           }else{
               left++;
           }
       }
       return min;
   }
}

Leetcode 153: Find Minimum in Rotated Sorted Array

Problem:
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.
You may assume no duplicate exists in the array.

Analysis:
Similarly, we can easily check which part of the array is sorted and we just compare the lowest
element. Then, we continue to search the other part.

Code:

public class Solution {
    public int findMin(int[] num) {//[1],[2,1], [3,1,2]
        int left=0;
        int right=num.length-1;
        int min=Integer.MAX_VALUE;
        while(left<=right){
            int mid=(left+right)/2;
            if(num[left]<=num[mid]){
                min=Math.min(min,num[left]);
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return min;
    }
}

Leetcode 81: Search in Rotated Sorted Array II

Problem:

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

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

Write a function to determine if a given target is in the array.

Analysis:

Based on the analysis of  "Search in Rotated Sorted Array", we are unable to make sure which part

is sorted only by comparing the mid with the left element. In this case, we need to increase the left

pointer until it is not equal to the mid.

Related questions:

Leetcode 33: Search in Rotated Sorted Array

Code:

public class Solution {
    public boolean search(int[] A, int target) {
        if(A==null || A.length==0 || A.length==1 && A[0]!=target){
            return false;
        }
        int left=0;
        int right=A.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(target==A[mid]){
                return true;
            }else if(A[left]<A[mid]){
                if(A[left]<=target && target<A[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else if(A[left]>A[mid]){
                if(A[mid]<target && target <=A[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else{
                left++;
            }
        }
        return false;
    }
}

Leetcode 33: Search in Rotated Sorted Array

Problem:

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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Analysis:

Two conditions should be paid attention. One is that before rotated, the array is sorted and the other

is there is no duplicate. We can modify binary search to search rotated array. 

Suppose A is the rotated array.

left=0, right=A.length-1, mid=(right+left)/2

Case 1: if A[mid] >A[left], A[left .. mid] is in order. 

Case 2: if A[mid] < A[left], A[mid] is also smaller than A[right], therefore A[mid .. right] is in order.

We can easily verify whether the target is in the sorted part or not. 

Code:

public class Solution {
    public int search(int[] A, int target) {
        if(A==null || A.length==0 || A.length==1 && A[0]!=target){
            return -1;
        }
        int left=0;
        int right=A.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(A[mid]==target){
                return mid;
            }else if(A[mid]>=A[left]){ // A[left..mid] is sorted.
                if(A[left]<=target && target<A[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{//A[mid..right] is sorted.
               if(target<=A[right] && target>A[mid]){
                   left=mid+1;
               }else{
                   right=mid-1;
               }
            }
        }
        return -1;
    }
}

Leetcode 80: 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]. 

Analysis:

As duplicates are allowed at most twice, the first thought is to compare the current element with the

previous two elements. However, we must remember that the array is a sorted array, which implies

that if current element equals to the second previous element, it must equal to the first previous one.

If not equal, current element can be added to the list.

Code:

public class Solution {
    public int removeDuplicates(int[] A) {
       if(A.length<=2){
           return A.length;
       }
       int tail=2;
       for(int i=2;i<A.length;i++){
           if(A[i]!=A[tail-2]){
               A[tail++]=A[i];
           }
       }
       return tail;
    }
}

Leetcode 26: Remove Duplicates from Sorted Array

Problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

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

Analysis:
As it is a sorted array, duplicated elements are neighboring with each other.
We can easily using two pointers to copy the first met element to the end of non-duplicated list.

Code:

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A==null){
            return -1;
        }else if(A.length<=1){
            return A.length;
        }
        int len=0;// the last element
        for(int i=1;i<A.length;i++){//i is another pointer
            if(A[i]!=A[len]){
                A[++len]=A[i];
            }
        }
        return len+1;
    }
}

Change the thought when cracking a special type of algorithm problem

Problem: (Gas station)

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.

Solutions:

The first thought of this problem is to check whether there exists an index that can meet the requirement and check each of them in serial until we find one. Well, you will get a O(n^2) algorithm if you do so.

My second thought is, this problem can use dynamic programming to record the path in order to minimize the computation. However, it is still a O(n^2) algorithm. 

After reading the solution of a guy from Leetcode.com, I realize that I went to the wrong way at the beginning. If we take a look at the problem, it is actually asking to "return ONE index that satisfy the requirement". Wow, I never notice that. So let's ask "What the most possible index?". If this index does not pass the constraints, there would no index left. As such, we only need to check the MOST POSSIBLE index and get a O(n) algorithm. 

http://discuss.leetcode.com/questions/3005/gas-station

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        if (gas.size() == 0)
            return -1;

        int sum = 0;
        int index = -1;
        bool last = true;
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            if (last && diff >= 0 && sum <= 0)
                index = i;
            last = (diff < 0);
            sum += diff;
        }

        if (index == -1)
            return index;

        for (int i = 0, sum = 0; i < gas.size(); i++) {
            sum += gas[(index + i) % gas.size()] - cost[(index + i) % gas.size()];
            if (sum < 0)
                return -1;
        }

        return index;
    }
};