Java two pointer


  • 7
    R
    public class Solution {
        public int maxArea(int[] height) {
        int result = 0;
        for(int i=0,j=height.length-1;i<j;){
            // get current area
            int area = Math.min(height[i],height[j])*(j-i);
            result = Math.max(area,result);
            //move the pointers
            if(height[i]<height[j]){
                i++;
            }
            else {
                j--;
            }
        }
        return result;
        }
    }

  • 6
    R
    public int maxArea(int[] height) {
    	int index1 = 0;
    	int index2 = height.length - 1;
    	int maxArea = 0;
    
    	while (index1 < index2) {
    		int minHeight = Math.min(height[index1], height[index2]);
    		maxArea = Math.max(maxArea, (index2 - index1) * minHeight);
    
    		// Shift smaller one
    		while (minHeight >= height[index1] && index1 < index2) index1++;
    		while (minHeight >= height[index2] && index2 > index1) index2--;
    	}
    
    	return maxArea;
    } // Complexity : O(n)
    

    This was my final code. My initial code was very similar to the code above. Most of these codes basically uses the same overall idea but some micro-optimization really increases the run-time. For instance using Math.max() is much faster than an if statement.
    maxArea = Math.max(maxArea, area); runs faster than doing if (area > maxArea) maxArea = area;. Also declaring and assigning variables takes time it seems. so instead of assigning area = (index2 - index1) * minHeight using it directly improves the runtime since you wont be using it again. I found that making these minor improvements significantly moved my answers through the run-time spectrum.

    Of course these micro-optimizations are usually negligible in real life and are only good for fun exercises like these.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.