Find the Median of Two Sorted Arrays - Leet Code Solution
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
September 13, 2019
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.
A simple brute force algorithm is what you can start with.
public int maxArea(int[] height) {
int max = 0;
int l = height.length;
for (int i=0; i<l; i++) {
for (int j=i+1; j<l; j++) {
int area = (j-i) * Math.min(height[i], height[j]);
if (area > max) {
max = area;
}
}
}
return max;
}
Lets think of optimizing this computation. What if we start with max range, and move either left or right. Since, lower height determines the area. And, we can move greedily towards point with high height. And, compare the area.
We can start with left and right pointer, calculate area. Then we can move towards point with higher height. i.e. the side which is having less height, we should move that pointer. Example: If left pointer value is less, move it right. Similarly, if right pointer value is less than right, move it left.
public int maxArea(int[] height) {
int l = height.length;
int result = 0;
int i=0;
int j = l-1;
while (i < j) {
int area = (j-i) * Math.min(height[i], height[j]);
if (result < area) {
result = area;
}
if (height[i] < height[j]) {
i++;
}
else j--;
}
return result;
}
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
Problem Statement Given a non-empty array of integers, every element appears…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Given a sorted array nums, remove the duplicates in-place such…
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
This problem is a simple mathematical calculation. Lets start deriving some…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…