Solving the easiest “Medium” difficulty algorithm on leet code

For a couple of months now, I have been working on solving algorithms almost daily. I do this by participating in an algorithm group where we take turns solving problems out loud in front of each-other, which I’m learning, helps get used to the nerves of trying to act smart in front of people.

For the most part, I would stick to “easy” ranked problems as some mediums had easily stumped me. After completing quite a few easy problems in front of the group I decided to pick a random “medium” to challenge myself. This problem happened to be leetcode problem 1227. Airplane Seat Assignment Probability. The problem is as follows:

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:

• Take their own seat if it is still available,
• Pick other seats randomly when they find their seat occupied

What is the probability that the n-th person can get his own seat?

Right away I used the skills I had been learning about stepping through a problem slowly and thoroughly. Right away we know we have “n” number of seats and “n” number of passengers. So we have as many seats as passengers and therefore there will never be an empty seat. Naturally my inclination was to solve what the probability is that the first person will sit in the right seat. Which was easy enough to figure out

var nthPersonGetsNthSeat = function(n) {
   n / (n * n)
};

However this doesn’t meet the condition the question asks. It wants to know what is the probability the “nth” person will sit in the correct seat, not the first. If we read the conditions carefully, it states that every person with the exception of the first passenger will sit in their assigned seat if it is open. What that tells me is each passenger only has to meet a condition, “is this seat taken” This transforms the probability from the computation above to a simple true/false boolean value. Therefore, beyond the first passenger everyone else's chance is simply a 50% chance. It seems a bit strange but the actual solution is

var nthPersonGetsNthSeat = function(n) {
   if (n == 1){
       return 1
   }else{
       return .5
   }
};

I chose to write about this particular algorithm because I think it illustrates an easy to overlook characteristic of computer programing, “reading the instructions carefully and thoughtfully” I see a glaring parallel between this problem and when I am overwhelmed with errors in the console of a program I’m creating. Often when I get an error I franticly try to fix it. However, like with this problem, when I take those errors slow, read them all the way through and think about it the solution seems to bubble to the surface pretty easily. I often wonder how applicable algorithms are to the jobs in the field and I’m often told “oh you wont use algorithms a day after you get hired” but I think this problem would be a good illustration of someones thought and problem solving process as well as a good reminder to slow down and take a problem step by step.

At any rate, thanks for reading and happy hacking!