It’s photo day at the local school, and you’re the photographer assigned to take class photos. The class that you’ll be photographing has an even number of students, and all these students are wearing red or blue shirts. In fact, exactly half of the class is wearing red shirts, and the other half is wearing blue shirts. You’re responsible for arranging the students in two rows before taking the photo. Each row should contain the same number of the students and should adhere to the following guidelines:

• All students wearing red shirts must be in the same row.
• All students wearing blue shirts must be in the same row.
• Each student in the back row must be strictly taller than the student directly in front of them in the front row.

You’re given two input arrays: one containing the heights of all the students with red shirts and another one containing the heights of all the students with blue shirts. These arrays will always have the same length, and each height will be a positive integer. Write a function that returns whether or not a class photo that follows the stated guidelines can be taken.

Note: you can assume that each class has at least 2 students.

Sample Input

redShirtHeights=[5, 8, 1, 3, 4]
blueShirtHeights=[6, 9, 2, 4, 5]

Sample Output

true

Solution

1. Sort lists in reversed order
2. Find which row goes in the back and which row goes in the front by comparing the tallest height of red and blue lists
3. Loop through both lists and compare height for each position
4. Return false if a position in the front row is taller than a position in the back row, else return true

Time Complexity: O(n log n)

Space Complexity: O(1)

Algorithm used: Greedy Algorithm

static boolean canTakeClassPhotos(List<Integer> redShirtHeights, List<Integer> blueShirtHeights) {
    Collections.sort(redShirtHeights, Collections.reverseOrder());
    Collections.sort(blueShirtHeights, Collections.reverseOrder());

    System.out.println("redShirtHeights: " + redShirtHeights);
    System.out.println("blueShirtHeights: " + blueShirtHeights);

    boolean canTakePhoto = true;

    String frontRowColor = (redShirtHeights.get(0) < blueShirtHeights.get(0)) ? "RED" : "BLUE";

    System.out.println("frontRowColor: " + frontRowColor);

    for (int i = 0; i < redShirtHeights.size(); i++) {
        int redShirtHeight = redShirtHeights.get(i);// front row
        int blueShirtHeight = blueShirtHeights.get(i);// back row

        if (frontRowColor.equals("RED")) {

            if (redShirtHeight >= blueShirtHeight) {
                canTakePhoto = false;
                break;
            }

        } else if (frontRowColor.equals("BLUE")) {
            if (redShirtHeight <= blueShirtHeight) {
                canTakePhoto = false;
                break;
            }
        }
    }

    System.out.println("canTakePhoto: " + canTakePhoto + "\n\n");

    return canTakePhoto;
}

List<Integer> redShirtHeights = Arrays.asList(5, 8, 1, 3, 4);
List<Integer> blueShirtHeights = Arrays.asList(6, 9, 2, 4, 5);

canTakeClassPhotos(redShirtHeights, blueShirtHeights);// true

redShirtHeights = Arrays.asList(6, 9, 2, 4, 5);
blueShirtHeights = Arrays.asList(5, 8, 1, 3, 4);

canTakeClassPhotos(redShirtHeights, blueShirtHeights);// true

redShirtHeights = Arrays.asList(6, 9, 2, 4, 5, 1);
blueShirtHeights = Arrays.asList(5, 8, 1, 3, 4, 9);

canTakeClassPhotos(redShirtHeights, blueShirtHeights);// false

redShirtHeights = Arrays.asList(6);
blueShirtHeights = Arrays.asList(6);

canTakeClassPhotos(redShirtHeights, blueShirtHeights);// false

Source code on Github