How Many Apples Can You Put into the Basket — LeetCode 1196 Python Solution
EasyLeetCode PremiumGreedyArraySorting
- Problem
- #1196
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You have some apples and a basket that can carry up to 5000 units of weight. Given an integer array weight where weight[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.
Example
- Input
- weight = [100,200,150,1000]
- Output
- 4
- Explanation
- All 4 apples can be carried by the basket since their sum of weights is 1450.
Python solution
Python
class Solution:
def maxNumberOfApples(self, weight: List[int]) -> int:
weight.sort()
s = 0
for i, x in enumerate(weight):
s += x
if s > 5000:
return i
return len(weight)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(\log n) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1196. How Many Apples Can You Put into the Basket is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1196. How Many Apples Can You Put into the Basket?
- LeetCode 1196. How Many Apples Can You Put into the Basket is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1196. How Many Apples Can You Put into the Basket?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 1196. How Many Apples Can You Put into the Basket?
- The Python solution on this page uses O(\log n) auxiliary space.
- What topics does LeetCode 1196. How Many Apples Can You Put into the Basket cover?
- LeetCode 1196. How Many Apples Can You Put into the Basket is tagged Greedy, Array and Sorting on LeetCode.
- Is LeetCode 1196. How Many Apples Can You Put into the Basket a premium problem?
- Yes. LeetCode 1196. How Many Apples Can You Put into the Basket is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.