Bricks in Wheelbarrow

You are transporting bricks on a construction site and want to work as efficiently as possible. The weight of each brick is given by bricks[i]. Given a wheelbarrow that can carry up to (not including) 5000 pounds, return the maximum number of bricks you can place in your wheelbarrow to transport.

Example(s)

Example 1:

Input: bricks = [1000, 1000, 1000, 2000]
Output: 3
Explanation:
Take three 1000-pound bricks: 1000 + 1000 + 1000 = 3000 < 5000
Total: 3 bricks

Alternative: 2000 + 1000 + 1000 = 4000 < 5000 (also 3 bricks)

Example 2:

Input: bricks = [1000, 200, 150, 200]
Output: 4
Explanation:
Take all bricks: 1000 + 200 + 150 + 200 = 1550 < 5000
Total: 4 bricks (all fit)

Example 3:

Input: bricks = [2000, 2000, 2000]
Output: 2
Explanation:
Take two 2000-pound bricks: 2000 + 2000 = 4000 < 5000
Cannot take all three (2000 + 2000 + 2000 = 6000 >= 5000)
Total: 2 bricks

Solution

The solution uses Greedy Algorithm:

Sort bricks: Sort by weight (lightest first)
Greedy selection: Take lightest bricks first until capacity is reached
Maximize count: Since all bricks have equal "value" (count = 1), greedy is optimal

JavaScript Solution
Python Solution

JavaScript Solution - Greedy

/**
* Find maximum number of bricks that fit in wheelbarrow
* @param {number[]} bricks - Array of brick weights
* @return {number} - Maximum number of bricks
*/
function maxBricks(bricks) {
const capacity = 5000; // Up to (not including) 5000 pounds

// Sort bricks by weight (lightest first)
const sorted = [...bricks].sort((a, b) => a - b);

let totalWeight = 0;
let count = 0;

// Take lightest bricks first
for (const weight of sorted) {
  if (totalWeight + weight < capacity) {
    totalWeight += weight;
    count++;
  } else {
    break; // Can't fit any more
  }
}

return count;
}

// Test cases
console.log('Example 1:', maxBricks([1000, 1000, 1000, 2000])); 
// 3

console.log('Example 2:', maxBricks([1000, 200, 150, 200])); 
// 4

console.log('Example 3:', maxBricks([2000, 2000, 2000])); 
// 2

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Greedy

from typing import List

def max_bricks(bricks: List[int]) -> int:
  """
  Find maximum number of bricks that fit in wheelbarrow
  
  Args:
      bricks: Array of brick weights
      
  Returns:
      int: Maximum number of bricks
  """
  capacity = 5000  # Up to (not including) 5000 pounds
  
  # Sort bricks by weight (lightest first)
  sorted_bricks = sorted(bricks)
  
  total_weight = 0
  count = 0
  
  # Take lightest bricks first
  for weight in sorted_bricks:
      if total_weight + weight < capacity:
          total_weight += weight
          count += 1
      else:
          break  # Can't fit any more
  
  return count

# Test cases
print('Example 1:', max_bricks([1000, 1000, 1000, 2000]))  
# 3

print('Example 2:', max_bricks([1000, 200, 150, 200]))  
# 4

print('Example 3:', max_bricks([2000, 2000, 2000]))  
# 2

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Dynamic Programming)

Here's a DP solution for completeness (though greedy is optimal here):

JavaScript DP
Python DP

/**
 * DP solution: 0/1 Knapsack variant
 * Maximize count (each brick has value 1)
 */
function maxBricksDP(bricks) {
  const capacity = 5000;
  const n = bricks.length;
  
  // dp[i][w] = maximum number of bricks using first i bricks with weight w
  // Since we want to maximize count, we can optimize to 1D
  const dp = new Array(capacity).fill(0);
  
  for (let i = 0; i < n; i++) {
    const weight = bricks[i];
    // Process from right to left to avoid overwriting
    for (let w = capacity - 1; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + 1);
    }
  }
  
  // Find maximum count
  return Math.max(...dp);
}

def max_bricks_dp(bricks: List[int]) -> int:
    """
    DP solution: 0/1 Knapsack variant
    Maximize count (each brick has value 1)
    """
    capacity = 5000
    n = len(bricks)
    
    # dp[w] = maximum number of bricks with total weight w
    dp = [0] * capacity
    
    for weight in bricks:
        # Process from right to left to avoid overwriting
        for w in range(capacity - 1, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + 1)
    
    # Find maximum count
    return max(dp)

Complexity

Time Complexity:
- Greedy: O(n log n) - Sorting the bricks, then O(n) to select
- DP: O(n × capacity) - Fill DP table
Space Complexity:
- Greedy: O(1) - Only using a few variables
- DP: O(capacity) - For the DP array

Approach

The solution uses Greedy Algorithm:

Sort bricks:
- Sort by weight in ascending order (lightest first)
- This allows us to maximize the count
Greedy selection:
- Take bricks one by one, starting with the lightest
- Add weight to total if it fits (total + weight < 5000)
- Increment count for each brick added
- Stop when no more bricks can fit
Why greedy works:
- All bricks have equal "value" (each counts as 1)
- To maximize count, we want to fit as many bricks as possible
- Taking lighter bricks first leaves more room for additional bricks
- This is optimal for maximizing count

Key Insights

Greedy algorithm: Optimal for maximizing count when all items have equal value
Sort by weight: Lightest first maximizes the number of items
Capacity constraint: Must be strictly less than 5000
O(n log n) time: Dominated by sorting
Simple solution: Greedy is simpler and more efficient than DP here

Step-by-Step Example

Let's trace through Example 1: bricks = [1000, 1000, 1000, 2000]

bricks = [1000, 1000, 1000, 2000]
capacity = 5000

Step 1: Sort bricks (already sorted)
  [1000, 1000, 1000, 2000]

Step 2: Greedy selection
  totalWeight = 0, count = 0
  
  Brick 1: weight = 1000
    totalWeight + 1000 = 0 + 1000 = 1000 < 5000 ✓
    totalWeight = 1000, count = 1
  
  Brick 2: weight = 1000
    totalWeight + 1000 = 1000 + 1000 = 2000 < 5000 ✓
    totalWeight = 2000, count = 2
  
  Brick 3: weight = 1000
    totalWeight + 1000 = 2000 + 1000 = 3000 < 5000 ✓
    totalWeight = 3000, count = 3
  
  Brick 4: weight = 2000
    totalWeight + 2000 = 3000 + 2000 = 5000 >= 5000 ✗
    Stop (can't fit)

Result: count = 3

Let's trace through Example 2: bricks = [1000, 200, 150, 200]

bricks = [1000, 200, 150, 200]
capacity = 5000

Step 1: Sort bricks
  [150, 200, 200, 1000]

Step 2: Greedy selection
  totalWeight = 0, count = 0
  
  Brick 1: weight = 150
    totalWeight + 150 = 0 + 150 = 150 < 5000 ✓
    totalWeight = 150, count = 1
  
  Brick 2: weight = 200
    totalWeight + 200 = 150 + 200 = 350 < 5000 ✓
    totalWeight = 350, count = 2
  
  Brick 3: weight = 200
    totalWeight + 200 = 350 + 200 = 550 < 5000 ✓
    totalWeight = 550, count = 3
  
  Brick 4: weight = 1000
    totalWeight + 1000 = 550 + 1000 = 1550 < 5000 ✓
    totalWeight = 1550, count = 4
  
  All bricks fit!

Result: count = 4

Visual Representation

Example 1: bricks = [1000, 1000, 1000, 2000], capacity < 5000

Sorted: [1000, 1000, 1000, 2000]

Selection:
  ✓ 1000 (total: 1000)
  ✓ 1000 (total: 2000)
  ✓ 1000 (total: 3000)
  ✗ 2000 (would be 5000, not < 5000)

Result: 3 bricks

Example 2: bricks = [1000, 200, 150, 200], capacity < 5000

Sorted: [150, 200, 200, 1000]

Selection:
  ✓ 150  (total: 150)
  ✓ 200  (total: 350)
  ✓ 200  (total: 550)
  ✓ 1000 (total: 1550)

Result: 4 bricks (all fit)

Edge Cases

All bricks fit: Return total count
No bricks fit: Return 0 (if all bricks are >= 5000)
Empty array: Return 0
Single brick: Check if it fits
Very light bricks: All might fit

Important Notes

Capacity constraint: Must be strictly less than 5000 (< 5000, not <=)
Maximize count: Goal is number of bricks, not total weight
Greedy is optimal: Since all bricks have equal value (count = 1)
O(n log n) time: Dominated by sorting
Simple solution: Greedy is preferred over DP here

Why Greedy Works

Key insight:

All bricks have equal "value" (each counts as 1)
To maximize count, we want to fit as many bricks as possible
Taking lighter bricks first leaves more room for additional bricks
This is mathematically optimal for maximizing count

Proof sketch:

If we can fit k bricks with greedy, we cannot fit more than k bricks
Any other selection that fits k+1 bricks would require total weight < 5000
But greedy already maximizes the number of bricks that fit
Therefore, greedy is optimal

0/1 Knapsack: Similar but with different values per item
Fractional Knapsack: Can take fractions of items
Partition Equal Subset Sum: Different optimization problem
Coin Change: Different knapsack variant

Takeaways

Greedy algorithm is optimal for maximizing count
Sort by weight (lightest first) maximizes items
O(n log n) time dominated by sorting
Simple solution compared to DP
Classic greedy problem with practical applications

Example(s)​

Solution​

JavaScript Solution - Greedy

Output:

Python Solution - Greedy

Output:

Alternative Solution (Dynamic Programming)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why Greedy Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Dynamic Programming)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why Greedy Works

Related Problems

Takeaways