Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1282.html

1282. Group the People Given the Group Size They Belong To (Medium)

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution. 

 

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

 

Constraints:

  • groupSizes.length == n
  • 1 <= n <= 500
  • 1 <= groupSizes[i] <= n

Related Topics:
Greedy

Solution 1.

The worst case for space complexity analysis is where we have the input in the form of [1, 2, 2, 3, 3, 3, ...]. Assume there are k distinct sizes, then k * (k + 1) / 2 = N, so the space complexity is O(sqrt(N)).

// OJ: https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/
// Time: O(N)
// Space: O(sqrt(N))
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& A) {
        unordered_map<int, int> m;
        vector<vector<int>> ans;
        for (int i = 0; i < A.size(); ++i) {
            int sz = A[i];
            if (m.count(sz) == 0 || ans[m[sz]].size() == sz) {
                m[sz] = ans.size();
                ans.emplace_back();
            }
            ans[m[sz]].push_back(i);
        }
        return ans;
    }
};

  • class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> sizePeopleMap = new HashMap<Integer, List<Integer>>();
        int length = groupSizes.length;
        for (int i = 0; i < length; i++) {
            int groupSize = groupSizes[i];
            List<Integer> people = sizePeopleMap.getOrDefault(groupSize, new ArrayList<Integer>());
            people.add(i);
            sizePeopleMap.put(groupSize, people);
        }
        List<List<Integer>> groups = new ArrayList<List<Integer>>();
        Set<Integer> keySet = sizePeopleMap.keySet();
        for (int groupSize : keySet) {
            List<Integer> people = sizePeopleMap.get(groupSize);
            int size = people.size();
            if (size == groupSize)
                groups.add(people);
            else {
                int groupsCount = size / groupSize;
                for (int i = 0; i < groupsCount; i++) {
                    List<Integer> group = new ArrayList<Integer>();
                    int start = i * groupSize, end = (i + 1) * groupSize - 1;
                    for (int j = start; j <= end; j++)
                        group.add(people.get(j));
                    groups.add(group);
                }
            }
        }
        return groups;
    }
}

############

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        int n = groupSizes.length;
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 0; i < n; ++i) {
            g[groupSizes[i]].add(i);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < g.length; ++i) {
            List<Integer> v = g[i];
            for (int j = 0; j < v.size(); j += i) {
                ans.add(v.subList(j, j + i));
            }
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/
// Time: O(N)
// Space: O(sqrt(N))
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& A) {
        unordered_map<int, int> m;
        vector<vector<int>> ans;
        for (int i = 0; i < A.size(); ++i) {
            int sz = A[i];
            if (m.count(sz) == 0 || ans[m[sz]].size() == sz) {
                m[sz] = ans.size();
                ans.emplace_back();
            }
            ans[m[sz]].push_back(i);
        }
        return ans;
    }
};

  • 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)]

############

# 1282. Group the People Given the Group Size They Belong To
# https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/

class Solution:
    def groupThePeople(self, arr: List[int]) -> List[List[int]]:
        mp = collections.defaultdict(list)
        
        for i,x in enumerate(arr):
            mp[x].append(i)
        
        res = []
        
        for key in mp:
            groups = mp[key]
            n = len(groups)
            
            if n == key:
                res.append(groups)
            else:
                for i in range(0, n, key):
                    res.append(groups[i:i+key])
        
        return res

  • func groupThePeople(groupSizes []int) [][]int {
	n := len(groupSizes)
	g := make([][]int, n+1)
	for i, v := range groupSizes {
		g[v] = append(g[v], i)
	}
	ans := [][]int{}
	for i, v := range g {
		for j := 0; j < len(v); j += i {
			ans = append(ans, v[j:j+i])
		}
	}
	return ans
}

  • function groupThePeople(groupSizes: number[]): number[][] {
    const res = [];
    const map = new Map<number, number[]>();
    const n = groupSizes.length;
    for (let i = 0; i < n; i++) {
        const size = groupSizes[i];
        map.set(size, [...(map.get(size) ?? []), i]);
        const arr = map.get(size);
        if (arr.length === size) {
            res.push(arr);
            map.set(size, []);
        }
    }
    return res;
}


  • use std::collections::HashMap;
impl Solution {
    pub fn group_the_people(group_sizes: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let mut map = HashMap::new();
        for i in 0..group_sizes.len() {
            let size = group_sizes[i] as usize;
            let arr = map.entry(size).or_insert(vec![]);
            arr.push(i as i32);
            if arr.len() == size {
                res.push(arr.clone());
                arr.clear();
            }
        }
        res
    }
}

All Problems

All Solutions