Minimum Time to Complete Trips - Binary Search

By on

Description

Solution: Binary Search

Upper bound set to 10^7 * 10^7, since time[i], totalTrips <= 10^7.
Binary search for the minimum time where each bus can complete at least 'time' number of trips.

Time Complexity: O(n log(10^14))
Space Complexity: O(1)

var minimumTime = function(time, totalTrips) {
  let low = 1, high = 100000000000000 + 1;
  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    if (isEnough(mid)) high = mid;
    else low = mid + 1;
  }
  return low;

  function isEnough(minTime) {
    // for each bus, Math.floor(minTime / time[i])
    let trips = 0;
    for (let i = 0; i < time.length; i++) {
      trips += Math.floor(minTime / time[i]);
    }
    return trips >= totalTrips;
  }
};

javascript
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Beautiful Towers II - Monotonic Increasing Stack [JS]

By on
Description   Solution: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  left[i]  = sum of heights from ( 0, ..., i ) such that they are descending from index  i  to  0 . right :  right[i]  = sum of heights from ( i, ..., n - 1 ) such that they are descending from index  i  to  n - 1 . Use a monotonic increasing stack to store indices of  maxHeights  such that they are smaller than  maxHeights[i] . left to right: We know that from index  i  to  stack[stack.length - 1] , all heights are smaller than  maxHeights[i] . Take the existing sum up to  stack[stack.length - 1]  ( left[stack[stack.length - 1]] ) and add the sum for the current range ( maxHeights[i] * (i - stack[stack.length - 1]) ) Then, do the same from right to left. Take each  maxHeights[i]  as the peak of the mountain and use the results from  ...
Read more

Check if There is a Valid Partition For The Array - Two Approaches - DP & Recursion w/ Memoization [JS]

By on
Description   Solution 1: DP - Recursion w/ Memoization Memoize each  dp(i) , where  dp(i) = whether it is possible to have a valid partition from index i to n . For each index  i , try to make it part of a valid partition (one of the three cases): Two equal elements Three equal elements Three consecutive elements Time Complexity:  O(n)  158ms Space Complexity:  O(n)  59.9MB var validPartition = function ( nums ) { let n = nums.length, memo = Array (n).fill(- 1 ); return dp( 0 ); function dp ( i ) { if (i === n) return true ; if (i === n - 1 ) return false ; if (memo[i] !== - 1 ) return memo[i]; if (nums[i] === nums[i + 1 ] && dp(i + 2 )) return memo[i] = true ; if (i < n - 2 ) { if (!dp(i + 3 )) return memo[i] = false ; let hasThreeEqual = nums[i] === nums[i + 1 ] && nums[i + 1 ] === nums[i + 2 ]; let hasThreeConsecutive = nums[i] + 1 === nums[i + 1 ] && nu...
Read more

Minimum Number of Operations to Sort a Binary Tree by Level - BFS & Cycle Counting Explained [JS]

By on
Description   Solution: BFS & Cycle Counting BFS level-by-level and get minimum swaps for the node values at each level. How to calculate the minimum swaps to sort an array: Get the index of each number in its sorted position (store in a hashmap  indexes ) For each  nums[i] , store the number we need to swap with to place  nums[i]  in its sorted position (store in a hashmap  next ) Find the size of each cycle. Get the total sum of each ( cycle size - 1 ). Why sum of ( cycle size - 1 ) is correct: If cycle size =  1 , we don't need any swaps. If cycle size =  2 , we only need 1 swap. If cycle size =  3 , we need 2 swaps. ---  Main Proof  --- Starting from the smallest number in the cycle, swap each  nums[i]  (where  nums[i]  is in the cycle) into its sorted position. Since the number is now in the correct position, it is no longer in the cycle and this leaves us with a cycle of size ( n - 1 ), where  n = ...
Read more

Count Elements With Maximum Frequency - Hashmap [JS]

By on
Description   Solution: Hashmap Store the counts of elements in a hashmap. Keep track of the running max frequency. If a count exceeds the max frequency, reset the total count. If a count is equal to the max frequency, add to the total count. Time Complexity:  O(n) Space Complexity:  O(n) var maxFrequencyElements = function ( nums ) { let maxFreq = 0 , countMap = {}, ans = 0 ; for ( let num of nums) { countMap[num] = (countMap[num] || 0 ) + 1 ; let count = countMap[num]; if (count > maxFreq) { ans = count; maxFreq = count; } else if (count === maxFreq) { ans += count; } } return ans; };
Read more

Mice and Cheese - Greedy w/ Sorting [JS]

By on
Description   Solution: Greedy w/ Sorting The first mouse should always take the  k  cheese with the maximum difference ( reward1[i] - reward2[i] ). This ensures the loss is minimal. Time Complexity:  O(n log(n)) Space Complexity:  O(n) var miceAndCheese = function ( reward1 , reward2 , k ) { let n = reward1 . length , rewards = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { rewards . push ( [ reward1 [ i ] , reward2 [ i ] , reward1 [ i ] - reward2 [ i ] ] ) ; } rewards . sort ( ( a , b ) => b [ 2 ] - a [ 2 ] ) ; let score = 0 ; for ( let i = 0 ; i < n ; i ++ ) { score += i < k ? rewards [ i ] [ 0 ] : rewards [ i ] [ 1 ] ; } return score ; } ;
Read more