Class Photos

Tags

Class Photos

Category

Greedy

Difficulty

Easy

Problem Statement

Given two arrays of positive integers representing the heights of students in two groups (e.g., wearing red shirts and blue shirts), determine whether the students can be arranged in two rows for a class photo such that every student in the back row is strictly taller than the student directly in front of them. All students in one group must be in the same row.

Intuition

For the photo arrangement to work, one group must uniformly serve as the back row and the other as the front row. After sorting both groups by height, the tallest in the back row must be taller than the tallest in the front row, the second tallest must be taller than the second tallest, and so on. Sorting aligns students by height so we can make pairwise comparisons.

Approach

  1. Sort both arrays in descending order.
  2. Determine which group should be in the back row by comparing the tallest student in each group.
  3. If both groups have the same tallest height, return false (strict inequality is required).
  4. Iterate through the sorted arrays pairwise:
    • If any student in the designated back row is not strictly taller than the corresponding student in the front row, return false.
  5. Return true if all pairs satisfy the condition.

Pseudocode

function classPhotos(redShirtHeights, blueShirtHeights):
    sort(redShirtHeights, descending)
    sort(blueShirtHeights, descending)

    if redShirtHeights[0] > blueShirtHeights[0]:
        backRow = redShirtHeights
        frontRow = blueShirtHeights
    else if blueShirtHeights[0] > redShirtHeights[0]:
        backRow = blueShirtHeights
        frontRow = redShirtHeights
    else:
        return false

    for i from 0 to length(backRow) - 1:
        if backRow[i] <= frontRow[i]:
            return false

    return true

Time & Space Complexity

  • Time: O(n log n) for sorting, where n is the number of students in each group.
  • Space: O(1) if sorting is done in-place.

Key Insights

  • Sorting both groups ensures we pair the tallest with the tallest, second tallest with second tallest, etc. This is the optimal pairing because if the tallest back-row person cannot beat the tallest front-row person, no rearrangement will help.
  • The comparison must be strictly greater, not greater than or equal.
  • Only one arrangement can possibly work: the group with the overall tallest student must be in the back row.

Edge Cases

  • Both groups have the same tallest student: return false.
  • Groups of size 1: simply compare the two heights.
  • One group's students are all taller than the other group's students: straightforward true.
  • Groups where the overall tallest is in one group but a middle-height student fails the comparison: return false.

Linked mentions