# Sorting and searching problem related to a group of people standing in a rectangle

Please be brutal, and let me know how I've done on this problem, provided I coded it at an interview for a top tech firm.

Time it took me: 44 minutes

Worst case time complexity: O(n2)? Am I right?

Space Complexity: O(n)?

Problem:

A group of people stand before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. You will be given a String[] people containing the height of each person. Elements of people correspond to rows in the rectangle. Each element contains a space-delimited list of integers representing the heights of the people in that row.

Your job is to return 2 specific heights in a int[]. The first is computed by finding the shortest person in each row, and then finding the tallest person among them (the "tallest-of-the-shortest"). The second is computed by finding the tallest person in each column, and then finding the shortest person among them (the "shortest-of-the-tallest").

Definition:

Class: TallPeople

Method: getPeople

Parameters: String[]

Returns: int[]

Method signature: int[] getPeople(String[] people) (be sure your method is public)

Constraints:

• people will contain between 2 and 50 elements inclusive.
• Each element of people will contain between 3 and 50 characters inclusive.
• Each element of people will be a single space-delimited list of positive integers such that:

1. Each positive integer is between 1 and 1000 inclusive with no extra leading zeros.

2. Each element contains the same number of integers.

3. Each element contains at least 2 positive integers.

4. Each element does not contain leading or trailing whitespace.

Examples:

{"9 2 3",
"4 8 7"}


Returns: { 4, 7 }

The heights 2 and 4 are the shortest from the rows, so 4 is the taller of the two. The heights 9, 8, and 7 are the tallest from the columns, so 7 is the shortest of the 3. 1)

{"1 2",
"4 5",
"3 6"}


Returns: { 4, 4 }

{"1 1",
"1 1"}


Returns: { 1, 1 }

public static int[] getPeople(String[] people){
int maxOfMinHeight = Integer.MIN_VALUE;
int minOfMaxHeight = Integer.MAX_VALUE;
int count=0;

String[][]findMaxOfMin = new String[people.length][people[0].split(" ").length];
int[][] findMinOfMax = new int[people[0].split(" ").length][people.length];

for(String s : people){
String[] sort  = s.split(" ");
Arrays.sort(sort);
findMaxOfMin[count++]=sort;
}
for(int i=0; i<findMaxOfMin.length; i++){
maxOfMinHeight = Math.max(maxOfMinHeight, Integer.valueOf(findMaxOfMin[i][0]));
}
count=0;
int cols = people[0].split(" ").length;
for(int i=0; i<cols; i++){
int[] temp = new int[people.length];
for(int j=0; j<people.length; j++){
temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);
}
Arrays.sort(temp);
findMinOfMax[count++]=temp;
}
for(int i=0; i<findMinOfMax.length; i++){
minOfMaxHeight = Math.min(minOfMaxHeight, findMinOfMax[i][people.length-1]);
}
return new int[] {minOfMaxHeight, maxOfMinHeight};
}

• From where do you get these problems? :) Apr 4, 2014 at 22:49
• @SimonAndréForsberg TopCoder. :) I have a major interview coming up in September, and I am preparing for it now. Apr 4, 2014 at 22:54

1. Split it up! The current method does more than one thing, I'd create at least three helper methods:

int[][] parseInput(String[] input);
int getMaxOfMinHeightInColumns(int[][] peoples);
int getMinOfMaxHeightInRows(int[][] peoples);


It would be easier to follow and understand.

2. I looks like a bug that the following testcase fails:

@Test
public void test() {
String[] input = {"9 2 3",
"4 8 7"};
int[] result = getPeople(input);
assertArrayEquals(new int[] {4, 7}, result);
}

3. Reusing the count variable is a bad sing:

count=0;


Try to use two different variables for different purposes and more descriptive names. What does it count? Put that into the name of the variable.

4. A few explanatory variable would be more readable here and remove some duplication:

String[][]findMaxOfMin = new String[people.length][people[0].split(" ").length];
int[][] findMinOfMax = new int[people[0].split(" ").length][people.length];


Consider creating one for people.length and another for people[0].split(" ").length (columnNumber, rowNumber, for example).

5. (String[]) casting seems unnecessary here:

temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);

• what about the space complexity and time complexity of the problem I solved? Apr 5, 2014 at 0:37
• @bazang: Space complexity seems O(n). I can't say too much about time complexity I didn't understand the code completely. Apr 5, 2014 at 1:07

Complexity will essentially be defined by this structure:

for(int i=0; i<cols; i++){
int[] temp = new int[people.length];
for(int j=0; j<people.length; j++){
temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);
}
Arrays.sort(temp);
findMinOfMax[count++]=temp;
}


which, using 'c' for cols, and 'p' for people.length will produce a complexity of:

• O( p * c ) for the inner for-loop

• the loop itself is is O(p) and
• O(c) for the ((String[])people[j].split(" "))
• O(p log p) for the Arrays.sort(temp)

Putting those together in the outer O(c) loop, I calculate the complexity to be in the order of:

O( pc2 + cp log p )

The O(pc2) will be the dominant complexity.

If you move the Split to be outside the outer loop, and do something like:

int[][] data = new int[people.length][cols];
for (int j = 0; j < people.length; j++) {
String[] parts = people[j].split(" ");
for (int i = 0; i < cols; i++) {
data[j][i] = Integer.valueOf(parts[i]);
}
}
for(int i=0; i<cols; i++){
int[] temp = new int[people.length];
for(int j=0; j<people.length; j++){
temp[j] = data[j][i];
}
Arrays.sort(temp);
findMinOfMax[count++]=temp;
}


Then your overall complexity will drop to O(pc log p) because that part of the complexity will bcome dominant.