When we need to find a pair of elements that satisfies some conditions, two pointer technique could effectively decrease the time.

Generally, there are two types of two pointer. The first one is the two pointers start from the first element and the last element respectively and move to the center. The other one is the two pointers both start from the first element but have the different step length to move.

This is just a idea that should be come up with when we meet specific problems. So it should be mastered from the following problems.

Problem

1. Container With Most Water

Description

LeetCode 11

Given n non-negative integers a1a2, …, a, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

 

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Analysis

This is a problem that need to find a pair of elements. So we can come up with two pointer technique first.

The result that is optimized depends on the distance of two lines and the minimum of the two lines’ heights. So when the two pointers start from the first element and the last element, the distance is the largest. Then when we move the two pointers to the center, the distance will decrease.

The minimum of two heights depends on the smaller one. So if the pointer that is moved is the larger one, this moving process has no possibility of increasing the result, which is not meaningful. Therefore, we can only move the pointer that has the smaller height. The two pointers must meet after the loop. So no possible cases will be left. We can just record the maximum value and return it.

The time is \(O(n)\) and the space is \(O(1)\).

Solution

class Solution {
    public int maxArea(int[] height) {
        if(height==null||height.length==0) return 0;
        int low=0,high=height.length-1;
        int res=Integer.MIN_VALUE;
        while(low<=high)
        {
            res=Math.max(res,Math.min(height[high],height[low])*(high-low));
            if(height[low]<height[high]) low++;
            else high--;
        }
        return res;
    }
}

2. Two/Three/Four Sum

Description

LeetCode 1

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

LeetCode 15

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

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

LeetCode 18

Given an array nums of n integers and an integer target, are there elements abc, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Analysis

The three problems are all based on two pointer technique. In fact, only “Two Sum” could be improved by two pointer technique. “Three Sum” and “Four Sum” can be seen as the extensions of “Two Sum”. The extended parts can only be implemented by brute force method.

First, for the three problems, we must use \(O(nlogn)\) time to sort the array. So we could use two pointer technique.

Then for “Two Sum” problem, we can set two pointers that start from the first element and the last position and move to the center. Because the array is sorted, if the sum now is smaller than the target, move the left pointer to the next position. And if the sum now is higher than the target, move the right pointer to the past position. The time of this process is \(O(n)\). If the array given is not sorted, the time of the problem is \(O(nlogn\).

And for “Three Sum” and “Four Sum” problems, just first determine one element or two elements, and implement “Two Sum”. The time are \(O(n^2)\) and \(O(n^3)\).

However, in “Three Sum” and “Four Sum” problems, we must consider about how to avoid duplicate results. The duplicate results come from two reasons. One reason is we may visit a same position more than once. The other reason is there are same elements in the array. For the first reason, we could make the range of determining other elements depending on the element that has been determined. For the second reason, we could skip the element when we find it is same as the past or next element because the array has been sorted.

Solution

//LeetCode 1
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] numsplus = new int[nums.length][2];
        for(int i=0;i<nums.length;i++)
        {
            numsplus[i][0]=nums[i];
            numsplus[i][1]=i;
        }
    	Arrays.sort(numsplus, new Comparator<int[]>() {
    		public int compare(int[] n1,int[] n2)
    		{
    			if(n1[0]>n2[0])
    			{
    			return 1;}
    			else if(n1[0]<n2[0])
    			{return -1;}
    			else return 0;
    		}
    	});
        int[] A=new int[2];
        int low=0,high=numsplus.length-1;
        A[0]=numsplus[low][1];
        A[1]=numsplus[high][1];
        while(low<high)
        {
            if(numsplus[low][0]+numsplus[high][0]==target)
            {
                A[0]=numsplus[low][1];
                A[1]=numsplus[high][1];
                return A;
            }
            else if(numsplus[low][0]+numsplus[high][0]<target)
            {
                low++;
            }
            else
            {
                high--;
            }
        }
        return A;
    }
}

//LeetCode 15
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++)
        {
            if(i==0||nums[i]!=nums[i-1])
            {
                int j=i+1,k=nums.length-1;
                while(j<k)
                {
                    if(nums[i]+nums[j]+nums[k]==0)
                    {
                        res.add(Arrays.asList(nums[i],nums[j],nums[k]));
                        while(j<k&&nums[j]==nums[j+1]) j++;
                        while(j<k&&nums[k]==nums[k-1]) k--;
                        j++;
                        k--;
                    }
                    else if(nums[i]+nums[j]+nums[k]<0) j++;
                    else k--;
                }
            }
        }
        return res;
    }
}
    
//LeetCode 18
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++)
        {
            if(i==0||nums[i]!=nums[i-1])
            {
                for(int j=i+1;j<nums.length-2;j++)
                {
                    if(j==i+1||nums[j]!=nums[j-1])
                    {
                        int low=j+1,high=nums.length-1;
                        while(low<high)
                        {
                            if(nums[i]+nums[j]+nums[low]+nums[high]==target)
                            {
                                res.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
                                while(low<high&&nums[low]==nums[low+1]) low++;
                                while(low<high&&nums[high]==nums[high-1]) high--;
                                low++;
                                high--;
                            }
                            else if(nums[i]+nums[j]+nums[low]+nums[high]<target) low++;
                            else high--;
                        }
                    }
                }
            }
        }
        return res;        
    }
}

3. Floyd’s Cycle-Finding Algorithm

The problem is to judge if there is a loop in a sequence. A direct way is using hash set. However, hash set needs linear space. We could use Floyd’s Cycle-Finding Algorithm to solve this problem with constant space.

It is based on two pointer technique. Set a slow pointer and a fast pointer. Move the slow pointer by one and the fast pointer by two in one step. If they are the same at one step, that means there is a loop.

Description

LeetCode 202

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Analysis

In the problem description, we know that there must be a loop in the recursive process. And it is not easy to find an obviously math method. So we just use Floyd’s Cycle-Finding Algorithm to judge if there is a loop. When a loop appears, we can judge if we can \(1\) at that time.

Solution

class Solution {
    public boolean isHappy(int n) {
        return helper((long) n);
    }
    public boolean helper(long n)
    {
        long slow=n,fast=n;
        while(true)
        {
            slow=squarenumber(slow);
            fast=squarenumber(squarenumber(fast));
            if(slow==fast) break;
        }
        return slow==1;        
    }
    public long squarenumber(long x)
    {
        long c=1;
        long s=0;
        while(true)
        {
            if(x/c==0) break;
            s=s+(x/c%10)*(x/c%10);
            c=c*10;
        }
        return s;
    }
}

Reference

[1] https://leetcode.com/problems/container-with-most-water/solution/

[2] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/ThreeSum.java

[3] https://www.geeksforgeeks.org/happy-number/

[4] https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/

Leave a Reply

Your email address will not be published. Required fields are marked *