Ryan Does Leetcode

 Water Taps Given the locations and ranges of water taps in a 1-dimensional garden, determine the minimum number of taps required to water the garden An irrigation sprinkler courtesy of Nevit Dilmen via Wikipedia .  Distributed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made. This problem can be solved in a greedy manner by organizing taps based on their reach First create a vector to store the maximum reaches of taps int minTaps ( int n , vector < int > & ranges ) { vector< int > maxReach (n + 1 );          ...     } Then for each tap, determine its left and rightmost reach, minding limits of the garden.  Then, for each starting position, use the maxReach vector and the max() function to store the maximum reach of sprinklers beginning from the give start     f or ( int i = 0 ; i < ranges . size (); i++) { int start = ...

Replacements to Sort Given an array of integers, with a single operation one can replace an element by any two elements that sum to the original element.  Find the minimum number of operations  required to sort the array. A hip replacement.  Courtesy of Carl Jones et al via Wikipedia .  Shared under the Creative Commons Attribution 4.0 International license.  No changes made. A couple of key observations: It doesn't make sense to reduce the last element in the array When reducing an element, it makes sense to try and reduce it into as few chunks as possible that are equal to or less than the element to the right We implement a greedy algorithm that operates in linear time First we initialize our answer variable and the length of the array  long long minimumReplacement ( vector < int > & nums ) { long long answer = 0 ; int n = nums . size ();          ...     } Next we loop t...

 Shop penalties Given a customer log consisting of 'Y's and 'N's, find the hour of the minimum penalty .  A penalty occurs when a no customer is in store while it's open, or closed when a customer arrives. Arrival times are denoted by index in the customer array. This problem can be solved using brute force.  Iterate over every index in the customer array, and for each index, iterate over the values before and then after the index, calculating the penalties, then taking the minimum.  The runtime for this is O(n^2), so while it may work, it times out for larger inputs. This can be improved upon.  The idea is to calculate the penalty for the first hour, then iterate over the customer array and recalculate the penalty for each hour.   Initialize some variables     int bestClosingTime ( string customers ) {           int n = customers . size ( ) ; //number of customers int numn = 0 , numy = 0 ; //numbe...

 Stack queues Implement a stack using queues .  The implementation includes methods for pushing, popping, finding the front element (top) and returning empty status. Photo courtesy of Sju .  Distributed via Wikipedia under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made. The beginning of the problem states to use 2 queues.  At the end of the problem, Leetcode challenges one to come up with a solution using 1 queue.  The solution here is for 1 queue, which exercises similar ideas. For my approach, I used 1 queue to implement pushing in constant time and pop/top in O(n). To initialize the stack, we create an empty queue.  The queue q is a global variable. MyStack ( ) { q = queue < int > ( ) ; } For pushing, we simply push the inputted element to the back of the queue void push ( int x ) { q . push ( x ) ; } The idea behind pop and front is the same.  Iterate ove...