container-with-most-water.md

Requirements

Return the area of the largest rectangle formed by two heights in an array of heights.

Strategy

Take two pointers, one at the beginning and one at the end of the array. The difference between these to indexes constitutes the area's width. Store the maximum area obtained till now. At every iteration, we find out the area formed between them, update maximum area and move the pointer pointing to the shorter line towards the other end by one step.

Justification of strategy

The area formed by two lines will always be limitted by the shorter of the two. When the two pointers are at their starting positions, 0 and array.length -1 respectively, width is greatest. But moving the pointer and decrementing the width could increase the height and make up for the lost width. So we look for larger lines by moving the pointer and compare the area of the new rectangle formed to the stored area.

Define test cases

• [1, 2] should return 1
• [1,8, 6, 2, 5, 4, 8, 3, 7] should return 49
• [] should return 0

Implementation skeleton

• declare pointer variables to move from front and back
• declare area to store max area
• while the the pointer moving forward through the array is less than the pointer moving backwards ...
  • compare the area stored to the area formed by the product of the width and the shorter of the two lines indexed by our pointers
• increment the pointer pointing to the shorter line
• return the max area

Actual implementation

https://gist.github.com/PantherHawk/09e08d725bc3274d084d389e01aa9820

Execute test cases

function assertArrays(a, b) {
  return JSON.stringify(a) === JSON.stringify(b) ? 'SUCCESS' : 'FAILURE';
}

assertArrays(findMedianSortedArrays([1, 2]), 1);
assertArrays(findMedianSortedArrays([1,8, 6, 2, 5, 4, 8, 3, 7]), 49);
assertArrays(findMedianSortedArrays([]), 0);

Big-O Analysis

O(n)

Optimization (if applicable)