Sourav Dey
Sourav's Digital ๐Ÿ“˜ Notebook

Sourav's Digital ๐Ÿ“˜ Notebook

LeetCode Question - 1710. Maximum Units on a Truck ๐Ÿš›

LeetCode Question - 1710. Maximum Units on a Truck ๐Ÿš›

1st July 2022 | ๐Ÿ—“ Daily LeetCode Challenge - #1

Sourav Dey's photo
Sourav Dey
ยทJul 2, 2022ยท

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

Table of contents

  • About the Series
  • Problem Statement
  • Video Explanation
  • Solution
  • Similar Questions for practice
  • You can find me on the web ๐ŸŒ

About the Series

Problem-solving is a key skill set for any tech-related stuff you might be working on.

When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.

So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. ๐Ÿš€

Problem Statement

Maximum Units on a Truck ๐Ÿš›

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

  • numberOfBoxes is the number of boxes of type i.
  • numberOfUnitsPerBox is the number of units in each box of type i. You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Video Explanation

Sketch-annotation-element-stroke-line-arrow-spiral-up.png

Solution

Algorithm

  1. Sorting the array in descending order based on the no. of units in each box. ๐Ÿ“ฆ
  2. Iterate through the sorted array elements and check the remaining truckSize.
    • If not enough size for all boxes take as many boxes as you can and calculate the total units
    • Else take all the boxes and calculate the total units.
  3. Return the total units

Code ๐Ÿง‘โ€๐Ÿ’ป

var maximumUnits = function (boxTypes, truckSize) {
  boxTypes.sort((a, b) => b[1] - a[1]);

  var maxTotal = 0;
  var i = 0;

  while (truckSize > 0 && i < boxTypes.length) {
    const numOfBoxes = boxTypes[i][0];
    const numOfUnits = boxTypes[i][1];

    if (truckSize <= numOfBoxes) {
      maxTotal += truckSize * numOfUnits;
      truckSize = 0;
    } else {
      maxTotal += numOfBoxes * numOfUnits;
      truckSize -= numOfBoxes;
    }

    i++;
  }
  return maxTotal;
};

Time Complexity : O(nlogn)+O(n) = O(nlogn)

Space Complexity: O(1)

Similar Questions for practice

Now it is time to try more similar questions

You can find me on the web ๐ŸŒ

Add your solutions or approaches to the comments.

Show your love by Sharing the blog. ๐Ÿค—

"I didn't fail 1000 times. The light bulb was an invention with 1000 steps."

~Thomas A. Edison

Did you find this article valuable?

Support Sourav Dey by becoming a sponsor. Any amount is appreciated!

See recent sponsors |ย Learn more about Hashnode Sponsors
ย 
Share this