Positions Of Large Groups - Leetcode Solution

Problem Statement:

There are n people standing in a row and they are classified into different groups labeled from 1 to groupCount.

You are given an integer array groupSizes of length n where groupSizes[i] is the size of the ith group.

You are also given the integer maxGroupSize, the maximum size that a group can be.

The groups are positioned in the row such that there are no empty positions between any two adjacent groups.

Return the order in which the groups appear.

If there are multiple valid answers, return any of them.

It is guaranteed that there is at least one valid solution for the given input.

Solution:

The given problem can be solved by using a HashMap. The key in the HashMap will be the size of the groups (groupSize[i]) and the value will be the list of indices of that group.

We first iterate through the groupSizes array and store each group's indices in a hashMap using the key as the group size. Then we iterate through the hashMap to get the indices of the groups with the same size as maxGroupSize. We then divide this list of indices into smaller subgroups of size maxGroupSize and append these subgroups to the final answer.

Step 1: Create a hashmap to store each group's indices based on their group size. Iterate through groupSizes array and add the indices of each group to the hashmap.

Step 2: Iterate through the hashmap to get the indices of the groups with the same size as maxGroupSize.

Step 3: Divide this list of indices into groups of size maxGroupSize. Append these sub-groups to the final result array.

Here is the implementation of the above solution:

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        // Create a hashMap to store each group's indices based on their group size.
        Map<Integer, List<Integer>> hashMap = new HashMap<>();
        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            hashMap.putIfAbsent(size, new ArrayList<>());
            hashMap.get(size).add(i);
        }

        List<List<Integer>> result = new ArrayList<>();
        // Iterate through the hashmap to get the indices of the groups with the same size as maxGroupSize.
        for (int size : hashMap.keySet()) {
            if (size == groupSizes.length) continue;
            List<Integer> indices = hashMap.get(size);
            // Divide this list of indices into groups of size maxGroupSize.
            for (int i = 0; i < indices.size(); i += size) {
                result.add(indices.subList(i, i + size));
            }
        }

        return result;
    }
}

Time Complexity: O(n) Space Complexity: O(n)

1