Group the People Given the Group Size They Belong To — LeetCode 1282 Python Solution
MediumGreedyArrayHash Table
- Problem
- #1282
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.
Example
- Input
- groupSizes = [3,3,3,3,3,1,3]
- Output
- [[5],[0,1,2],[3,4,6]]
- Explanation
- The first group is [5]. The size is 1, and groupSizes[5] = 1.
Python solution
Python
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
g = defaultdict(list)
for i, v in enumerate(groupSizes):
g[v].append(i)
return [v[j : j + i] for i, v in g.items() for j in range(0, len(v), i)]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1282. Group the People Given the Group Size They Belong To is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
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 1282. Group the People Given the Group Size They Belong To?
- LeetCode 1282. Group the People Given the Group Size They Belong To is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1282. Group the People Given the Group Size They Belong To?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1282. Group the People Given the Group Size They Belong To?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1282. Group the People Given the Group Size They Belong To cover?
- LeetCode 1282. Group the People Given the Group Size They Belong To is tagged Greedy, Array and Hash Table on LeetCode.