Monday, September 11th

 Groups

There are a given number of people, each of whom is assigned to a group.  The number identifier of the group is also its size.  The size of a group may be a multiple of its size, e.g. a group of 3 may have 6 people.  Return the collection of all groups.

Team USA Softball (a group).  Shared by USASoftball, via Wikipedia, distributed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made.

This problem is pretty straightforward.  The idea is to create a map (or a vector) keyed by the group, storing an array of individuals belonging to the group.

First we create the vector-of-vectors to store our solution, then we initialize a vector of vectors that will store individuals according to their group numbers.  The size of the solution vector is n+1, because contrary to what the beginning of the problem statement said, the indices/group sizes go from 1 to n, according to the stated constraints.

vector<vector<int>> groupThePeople(vector<int>& groupSizes) {

vector<vector<int> > sol;

int n=groupSizes.size();

vector<vector<int> > groupvec(n+1, vector<int>());

        ...

    

    }

Then we iterate through the groupSizes vector, pushing each individual i to their corresponding vector. 

int group;

for(int i=0; i<groupSizes.size(); i++) {

group=groupSizes[i];

groupvec[group].push_back(i);

        ...

    }

If the size of one of the group vectors equals the size of the group, push the vector onto the solution vector, then clear it

    if(groupvec[group].size()==group) {

sol.push_back(groupvec[group]);

groupvec[group]=vector<int>();

}

Finally, return the solution vector

vector<vector<int>> groupThePeople(vector<int>& groupSizes) {

 ...

        return sol;

}

Definitely one of the easier medium-difficulty problems (some might say a softball), once you figure out the data structures

My initial approach used a map of vectors, but since the group numbers only go up to n, we can use a vector of vectors, indexed by the group size/id.  This appeared to have had a little bit speed up, since there's no hash calculation

I tried looking at other solutions with faster runtime or less memory, and everything is pretty similar

Full code below

    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {

vector<vector<int> > sol;

int n=groupSizes.size();

vector<vector<int> > groupvec(n+1, vector<int>());

int group;

for(int i=0; i<groupSizes.size(); i++) {

group=groupSizes[i];

groupvec[group].push_back(i);

if(groupvec[group].size()==group) {

sol.push_back(groupvec[group]);

groupvec[group]=vector<int>();

}

}

return sol;

}