You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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.
![equation](x <= 1 * m)
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.
![equation](m*(n-1) = sum-x*n >= sum-(minNum+m)n)
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.