PantherHawk

Requirements

Return the median of two sorted arrays.

Strategy

Concatenate arrays, sort, then find median.

Justification of strategy

We want to find the median of the set of numbers provided by both arrays. Assume we instead tried to find the medians of each array seperately and then sought the median of those medians.

PantherHawk

var maxArea = function(height) {
  // declare pointer variables to move from front and back
  // declare area to store max area
  let maxarea = 0;
  let forward = 0;
  let back = height.length - 1;
  // while the pointer moving forward is less than the pointer moving backwards ...
  while(forward < back) {
    // compare the area stored to the area formed by width and the shorter of the two lines indexed by the pointers.
    maxarea = Math.max(maxarea, Math.min(height[forward], height[back]) * (back - forward));

PantherHawk

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

PantherHawk

var intToRoman = function(num) {
    // store numerals 
    let romanNums = '';
    // make a graph mapping an array of integers to an array of roman numerals such that an index will map the two as we iterate through the integers array.
    let integers = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let romans = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
    // iterate over integers
    for (var i = 0; i < integers.length; i++) {
      // while the remainder of the input number divided by the roman numeral's integer is greater than than the integer at i ...
      while(num%integers[i] < num) {

PantherHawk

Requirements

Given a number, return the roman numeral.

Strategy

We're going back in time to the third century! Subtract the integer value of a roman numeral from the input value until the value is less than that the roman numeral value. Then move to the next roman numeral.

Justification of strategy

Roman numerals are just sums of particular integers. We want to find the sum created by the discrete number of integers provided by roman numerals. So we have to break the integer down, starting with our biggest building blocks. We only need to move to a smaller roman numeral if after dividing our input by the roman numeral there's a remainder. We handle the thousands, and then the hundreds, and finally the units. Once we find a value that is smaller or equal to our number, we will push the matching letter to our solution and subtract this value from our number.

Define test cases

• intToRoman(123) should return "CXXIII"

PantherHawk

var MinStack = function() {
    this.stack = [];
    this.min;
};

MinStack.prototype.push = function(x) {
    this.stack.push(x);
    if (!this.min && this.min !== 0) {
        this.min = x;
    } else if (x < this.min) {

PantherHawk

Requirements

Create a stack prototype with a method that returns the smallest value in constant time.

Strategy

Constructor has a push, pop, and get minimum value methods. Update the minimum value whenever we push or pop a value.

Justification of strategy

To get that sweet, sweet constant time look up for our minimum value, we have to compare the minimum value stored in our instance to any value we add, and then iterate through the stack to find a new smallest value whenever we pop.

Define test cases

• push(3), push(2), getMin() should return 2
• push(0 ... 500), getMin() should return 0
• push(-2), push(-3), push(-5), pop(), getMin() should return -3

PantherHawk

function minMoves(list) {
  var sum = list.reduce((a, b) => a + b)
  var minNum = Math.min(...list)
  var n = list.length;
  return sum-(minNum)*n
}

PantherHawk

Requirements

Given a list of integers, return the number of times it takes produce a list of equal integers by incrementing n - 1 elements by one.

Strategy

Maths!

Justification of strategy

The largest number in the list, x, is greater than or equal to the product of s, the smallest number, 1, the number we increment the smallest number by, and m, the number of times we increment, and the value we're after.  Refactoring, we find that the product of m and the number of elements we increment equals the difference between the sum of all elements and the product of the largest element and the number of elements.  = sum-x*n >= sum-(minNum+m)n)

PantherHawk

Requirements

Return true if a singly linked list has a loop.

Strategy

Use two pointers, the second moving twice the speed of the first, and see if the two pointers ever land on the same node.

Justification of strategy

Consider two runners on a track. The faster runner will lap the slower one. The faster runner in our case is a pointer incremented douple the incrementation of the slower pointer.
The edge case we have to account for is when the slow or the fast or the immediate child of the fast node is null.

Define Test Cases

let linkedList = new LinkedList();