Maximum Consecutive Floors Without Special Floors - Sorting & Get Max Adjacent Difference [JS]

By on

Description 

Solution: Sorting & Get Max Adjacent Difference

  1. Get all the special floors within the range of [bottom, ..., top].
    Add the edge cases bottom - 1 and top + 1, these are the starting and ending floors within the range.
    The reason for -1 and +1 is that when we compare adjacent floors, both floors are not part of the consecutive floors, but the starting and ending floor is.
  2. Sort the floors.
  3. Get the max difference between two adjacent floors.

Time Complexity: O(n log(n)) 366ms
Space Complexity: O(n) 60.3MB

var maxConsecutive = function(bottom, top, special) {
  let floors = [bottom - 1, top + 1];
  for (let floor of special) {
    if (floor >= bottom && floor <= top) floors.push(floor);
  } 
  floors.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 1; i < floors.length; i++) {
    ans = Math.max(ans, floors[i] - floors[i - 1] - 1);
  }
  return ans;
};

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