• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

LeetCode: Container With Most Water

October 29, 2019 by Arshdeep Singh

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.

Example 1:

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

Constrains: 0 < sizeof(heightArray) <= 10^5

Question Link: Container With Most Water

Solution: 

The first brute force way to approach this problem is to start from each line i and check its capacity with all lines j such that i < j < n which is pretty simple.

Code:

Implemented in C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea=0; // Initializing maximum area as 0

        for(int i=0; i<height.size(); i++){
            for(int j=i+1; j<height.size();j++){
                // Going through all pairs (i,j) for maximum container area.
                maxArea = max(maxArea, min(height[i], height[j])*(j-i));
            }
        }
        return maxArea;
    }
};

But the time complexity of this approach is O(n^2) which is not accepted.

Better Approach

The main catch in this question is to find the maximum area which can be caused due to two factors:

  1. Bigger Width
  2. Bigger Height

Lets firstly maximize the width by taking the two extreme ends of the input array i.e. 0 and n-1 as two pointers and then continue to decrease each end along with calculating area for each case. But question is which end should we decrease?

There are two possibilities:

  1. Both pointers’ heights are same
  2. They have different heights

If we switch from a pointer having more height, the we are losing a potential pair which can have better area while decreasing the pointer having less height will not cause any trouble. So, we should decrease the pointer having less height. This is a greedy approach, for a mathamatical proof for this approach, refer here.

Lets understand the approach with the same example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Step 1. Here area = 8 and Maximum Area = 8
Step 2. Here area = 49 and Maximum Area = 49
Step 3. Here area = 18 and Maximum Area = 49
Step 4. Here area = 40 and Maximum Area = 49
Step 5. Here area = 24 and Maximum Area = 49
Step 6. Here area = 6 and Maximum Area = 49
Step 7. Here area = 10 and Maximum Area = 49
Step 8. Here area = 4 and Maximum Area = 49

At step 2, we achieved the maximum area.

Code:

Implemented in C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        // Initializing maximum Area as zero
        // Initializing the two pointers as beginning and end.
        int maxArea=0,i=0,j=height.size()-1;

        while(i<j){ //work till area is positive
            // Calculate area for each pair
            maxArea = max(maxArea, min(height[i], height[j])*(j-i));
            if(height[i]<=height[j]) i++; // if left pointer is small
            else j--; // if right pointer is small
        }
        return maxArea; //returning maximum area
    }
};

The time complexity of this approach is O(n) which is accepted. This technique of using two pointers is called Two Pointer Technique or Sliding Window Technique, click here for more questions.

Similar Articles

Filed Under: Amazon Interview Question, Array, Facebook, Google, LeetCode Tagged With: Array, Two Pointer

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Level order traversal in Spiral form

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Generate largest number arranging a no. of given non negative integer numbers

Add Sub Multiply very large number stored as string

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Check Binary Tree is Binary Search Tree or not

Find the number ABCD such that when multipled by 4 gives DCBA.

Memory Efficient LinkedList

Maximum sum contiguous subarray of an Array

1014 Practice Question of New GRE – Princeton

Doubly linked list

Calculate price of parking from parking start end time prices

Python Array String

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Walmart Labs Interview Experience

Edit Distance ( Dynamic Programming )

How Radix sort works

Stickler thief

Find loop in Singly linked list

simple sql injection

Closed Parentheses checker

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Handle duplicates in Binary Search Tree

Given a string, find the first character which is non-repetitive

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Test Cases for Round Function

Naurki.com Security Breach

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Connect n ropes with minimum cost

VMWare SDEII Interview

Copyright © 2025 · Genesis Framework · WordPress · Log in