A Photographer's Dilemma

The sliding window technique

Today’s task comes to you from a famous photographer.

A photographer

During the year he is invited to several schools to take photographs of the students. There are N classes, and each class has S students. He selects exactly 1 student from each class and lines them up to take a photo. For photographic beauty, he wants to ensure that the height difference between the N selected students is minimised. So he sends you a single problem statement.

Write a program for me that determines which N students I should select such that the height difference between the shortest student and the tallest student is minimised. The program must also tell me what that height difference is, so I know how to frame the photograph.

Sounds simple enough right? Well, the problem is that the photographer rarely deals with single schools. Instead, he handles entire groups of schools at once, making a total of as many as 1000 classes, each with up to 100 students. Clearly, he can’t calculate the answer manually, and if your code is too slow he won’t bother using it. So, how do you solve his problem?

Thank you for reading Elucidate: for the curious coder!

If you enjoy coding related content, consider subscribing or upgrading your subscription.

If you are already subscribed, you can trust quality content weekly. I ask less than 2 cups of coffee a month. Consider supporting my work by upgrading your subscription!

The naïve solution

At first, you don’t even know how to solve this problem. If you try every possible combination of students, the total possible number of ways to select N students from this group is S^N. That’s simply too much.

Since the question is asking for ranges, perhaps there is a better way to solve it. Ranges have a minimum and maximum value right? So how about you try fixing one of them? That gives you an idea for a new algorithm.

• For each student, you assume that student is the shortest among all those you will select. Call this student x.

• For each other class, you find the shortest student who is at least as tall as student x. Continue till you have chosen N students. Calculate the height difference.

• Repeat this process until you eventually find the best choice of N students.

There are N*S students. Every time you run this algorithm you loop through all N*S students, giving a total time complexity of O(N^2S^2).

Of course, there’s some ways to make this faster. For example, if you sort the students in each class in increasing order of height, you realise you can run step 2 of the algorithm in O(Nlog(S)), giving you a total time complexity of O(N^2SlogS).

Sliding Window

You realise there’s a smarter solution out there somewhere, you just need to search for it. And in your search you encounter a new algorithm called the “sliding window”.

Imagine some array. The sliding window defines a range in the form of a “window” of a fixed length.

The window continues sliding to the right one at a time.

This is where the “sliding” part of the algorithm comes from.

Eventually, the window finishes sliding and we have our answer.

Note that the length of the window can change as it slides.

Observations

You realise that things are often easier when sorted, so you start off with that. You arrange the students in increasing order of height by creating a sorted array of heights.

Next, you will binary search the answer using the sliding window technique. Here’s how it works. Assume that the difference between the shortest and tallest student is H. Say you guess a random value of h. How do you check if it is possible?

You need a sliding window whose length can change for this. The “window” is defined as 2 pointers, one that points to the beginning of the window and one that points to its end.

We know students are identified by their height and class. So let’s create an array with that information. Let’s first sort the students by height and ignore their classes. There are N*S students, so let us created an array as follows.

The students are labelled from 0 to N*S-1, with student 0 being the shortest and the students labelled in increasing order of height 

Let h[i] be the height of the ith student 
Let c[i] be the class of the ith student 

At first, both pointers point to h[0]. Now we create another array, cnt. We also create a variable called size.

cnt[i] represents the number of students in the ith class within the sliding window. Initially all cnt[i] = 0

size represents the number of i such that cnt[i] > 0. Initially size = 0

At the beginning, our sliding window consists of just 1 person. So we set cnt[c[0]] = 1. Set size = 1.

Now we increment the ending pointer. At any time, let the ending pointer be pointing to h[e].

• Case 1: h[e] - h[s] <= H

  • This means we can include h[e] in our list of student

  • Increment cnt[c[e]] += 1

  • If cnt[c[e]] was previously 0, then set size += 1

• Case 2: h[e] - h[s] > H

  • This means the student cannot yet be included in the window

  • Move the starting pointer forwards to remove the shorter students until Case 1 is met

  • Decrease cnt[c[s]] -= 1

  • If cnt[c[s]] = 0, set size -= 1

  • Repeat until case 1 conditions are met, then treat it like case 1

During this slide we need to track 2 things.

• If at any point size = N, it means we have 1 student from each class all within the height difference H. We can immediately stop the algorithm and move on- we have our answer.

• If by the time the pointer reaches the end of the array we still haven’t reached a solution, we end the algorithm and report that H is an impossible restriction

Based on these 2 we can binary search the smallest value of H and report it to the photographer, as well as the students in the window where we got this height difference from.

Coded solution

Instead of the full coded solution presented in a large, unreadable chunk, I’ll break it down and construct the code step-by-step. I’ll also present the time complexity at the end.