Problem Statement: Given an array with n numbers representing the heights of vertical lines on an x-axis, find the maximum area that can be created with two lines from your array. (Difficulty: Medium)
Input:
An array of integers representing different heights.
Output:
A single integer: the max area.
Solution Approach:
Brute Force Approach:
I first considered testing the area for every pair of values using a shifting center algorithm but that would simply take too long. The time complexity seemed too close to On^2.
Two-Pointer Approach:
So, the strategy was changed to invlove to pointers which will gradually move towards the center of the array while the area is being tested to find the max at each loop iteration. I attempted to halve the number of loop iterations by moving both pointers in each iteration but I getting out of bounds errors. So, I had to reevaluate my solution's requirements.
Optimized Two-Pointer Approach:
I came to the realization that what the solution required was finding the longest lines which were farthest apart as soon as possible, so I decided that to move the pointers based on which value was higher at a loop iteration.
Time complexity: O(n)
Here is the Code in JAVA:
public int maxArea(int[] h) {
int n = h.length, i=0, max=Integer.MIN_VALUE, a=0,b=n-1;
if(n==1){
return h[0];
}
while(b>a){
if(h[a]<h[b]){
int aa = h[a]*(b-a);
if(max<aa) max=aa;
a++;
} else {
int aa=h[b]*(b-a);
if(max<aa) max=aa;
b--;
}
}
return max;
}