Posts Maximum Water between Two Walls
Post
Cancel

Maximum Water between Two Walls

Problem Description

Given an array of size N, where A[i] represents the height of the ith wall, pick any two walls such that maximum water can be stored between them.

Solution

We start from the first and last wall so that we have the largest distance between the walls. If height of water depends on the size of the wall which has smaller value. So, for the next check, we discard the wall which has a smaller value and move to the next wall.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.gauk;

import java.util.Arrays;

public class MaxWaterTrapped {

    public static void main(String[] args) {
        int[] A = new int[]{3,7,4,5,2};
        System.out.println(Arrays.toString(new MaxWaterTrapped().getMaxWaterWalls(A)));
    }

    //Given an array of size N, where A[i] represents the height of the ith wall, pick any two walls such that maximum water can be stored between them.
    public int[] getMaxWaterWalls(int A[]){

        int max=0;
        int[] ans = new int[2];
        //Initialize i and j such that the distance between them is maximum
        int i = 0;
        int j = A.length-1;

        while(i<j){

            int distanceBetweenTheWalls = j-i;
            int minWallSize = Math.min(A[i], A[j]);
            int amountOfWater = distanceBetweenTheWalls*minWallSize;

            if(amountOfWater > max){
                max = amountOfWater;
                ans = new int[]{i, j};
            }

            //Check for better values by discarding the wall which is smaller in size
            if(A[i] < A[j]){
                i++;
            }else{
                j--;
            }

        }

        return ans;

    }

}
This post is licensed under CC BY 4.0 by the author.