Skip to Content
DifficultyHard

Split Array Largest Sum 

  • Use binary searach with min & max as max & sum of the array
  • Check if the sum can be split into k subarrays for mid value
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function (nums, k) {
  const [sum, max] = getTotalAndMax(nums);
  if (k === nums.length) {
    return max;
  }
 
  if (k === 1) {
    return sum;
  }
 
  let left = max,
    right = sum,
    ans = 0;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const canFit = checkFitment(nums, k, mid);
 
    if (canFit) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function checkFitment(nums, k, limit) {
  let sum = 0,
    count = 1;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (sum > limit) {
      count += 1;
      sum = nums[i];
 
      if (count > k) {
        return false;
      }
    }
  }
 
  return true;
}
 
function getTotalAndMax(arr) {
  let sum = 0,
    max = 0;
 
  for (const item of arr) {
    sum += item;
    if (max < item) {
      max = item;
    }
  }
 
  return [sum, max];
}
Complexity
  • Time: O(n log(sum - max))
  • Space: O(1)

Minimize Max Distance to Gas Station 

  • For a binary search, use left as minimum distance possible and right as maximum distance possible
  • For each distance, check if it is possible to add k stations with gap less than or equal to the distance
/**
 * @param {number[]} stations
 * @param {number} k
 * @return {number}
 */
var minmaxGasDist = function (stations, k) {
  let left = 0, right = stations.at(-1) - stations.at(0);
 
  while (right - left > 1e-6) {
    const mid = left + (right - left) / 2;
    const canFit = checkEligibleGap(stations, k, mid);
 
    if (canFit) {
      right = mid;
    } else {
      left = mid;
    }
  }
 
  return left;
};
 
function checkEligibleGap(stations, k, gap) {
  let newStations = 0;
 
  for (let i = 0; i < stations.length - 1; i++) {
    newStations += Math.ceil((stations[i + 1] - stations[i]) / gap) - 1;
 
    if (newStations > k) {
      return false;
    }
  }
 
  return true;
}
Complexity
  • Time: O(n log(W)) where W is the range of the answer
  • Space: O(1)

Minimum Number of Operations to Make Array Continuous 

  • Sort the given nums array by removing duplicates
  • Consider each element as the first element & find the number of elements that can be included in the subarray till the last
  • Consider the rest of the elements count as number of operations required
/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
  const uniqNums = [...new Set(nums)].sort((a, b) => a - b);
 
  // check if already continuous
  if (uniqNums.at(-1) - uniqNums[0] === 1) {
    return 0;
  }
 
  let minOps = nums.length;
  for (let idx = 0; idx < uniqNums.length; idx++) {
    const first = uniqNums[idx];
    const last = first + nums.length - 1; // last element to make it continuous
 
    const lastIdx = getUpperBound(uniqNums, last);
    const sortedCount = lastIdx - idx; // number of elements that are already present to make it continuous
    const ops = nums.length - sortedCount; // number of elements that need to be replaced
 
    minOps = Math.min(minOps, ops);
  }
 
  return minOps;
};
 
function getUpperBound(arr, k) {
  let left = 0, right = arr.length, ans = arr.length;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (k < arr[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
}
Complexity
  • Time: O(n log(n))
  • Space: O(n)
Last updated on
Medium