Longest run of consecutive integers in an array — code challenge

Recently I did a code challenge for an apprenticeship position at a large tech company. I liked the questions, kept notes on them, and the time limit and testing suite on their platform allowed me to refine my answer until I was happy with it. Here’s the first question, my process including initial attempts, and my final answer. I hope they’re okay with me writing this — I couldn’t find any language to the contrary.

The question

They wrote a little backstory, like a word problem — “Oh we’re a ticketing agency yadda yadda and an array of prices yadda yadda,” I don’t remember exactly. The point was: Write a function that takes an array of integers and gives the length of the longest run of consecutive integers, including repeats. So for example for an input of [5,1,6,8,5,2,2,1,6,4] it should return 5, for [4,5,5,6,6].

I chose to solve in Ruby.

First attempt

My initial thought process was: We can brute-force this by checking the size of the runs you can get by starting with each element. So in our example, check 1, you get 1,1,2,2 and stop there. Do that for every element, pick the longest one. It’s the most naive method, but it’s good to start by getting results on paper.

def someTicketsFunction(ticketsArray)
  sortedTix = ticketsArray.sort
  m = 0
  sortedTix.each{|price|
      currentprice = price
      innerm = 0
      while sortedTix.include?(currentprice)
        innerm += sortedTix.count(currentprice)
        currentprice += 1
      end
      m = [innerm, m].max
  }
  p m
end

This works just fine, but it’s very inefficient timewise. You can see that it has a nested iteration (the while inside the each), which is the sort of thing you want to factor out.

What’s going on here is that we first sort the input array with ruby’s handy .sort, turning our previous example [5,1,6,8,5,2,2,1,6,4] into [1,1,2,2,4,5,5,6,6,8]. Then we start going through each item and checking if it’s the start of a run, and if it is, we find the size of the run, compare it to the previously-stored size (m — why did I call it m?), and if it’s bigger, replace m with it.

We count the run with this:

innerm = 0
while sortedTix.include?(currentprice)
  innerm += sortedTix.count(currentprice)
  currentprice += 1
end

We’re checking to see if the array contains the subsequent integer, and then the next one, and then the next one. It works, but it’s a hell of a lot of traversing for the program to do.

Second attempt

I realized while drafting this first pass method that we don’t have to check the length of the run for each element, only the ones that are the start of a run. In other words, if the input array has a 1 and a 2 in it, there’s no reason to check the run starting with 2 — we know for a fact that the one starting with 1 is going to be longer. So, with the details worked out:

def someTicketsFunction(ticketsArray)
  sortedTix = ticketsArray.sort
  m = 0
  sortedTix.each{|price|
    if sortedTix.include?(price - 1)
      nil
    else
      currentprice = price
      innerm = 0
      while sortedTix.include?(currentprice)
        innerm += sortedTix.count(currentprice)
        currentprice += 1
      end
      m = [innerm, m].max
    end
  }
  p m
end

We check to see if it’s the start of a run with this:

sortedTix.include?(price - 1)

This checks to see if the value one lower than the value we’re currently checking exists as an entry in the array. If it does, the entry we’re currently checking is not the first of a run, so we don’t care about it and can move on to the next one.

This is an improvement, in that now we’re checking a lot fewer values, but it doesn’t solve our core problem of iterating inside an iterator. We’re still way too slow, and need to figure out a way around that.

Third try (best solution)

def someTicketsFunction(ticketsArray)
  tixFrequencyHash = ticketsArray.sort.reverse.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}
  m = 0
  tixFrequencyHash.each{|price, frequency|
    tixFrequencyHash[price] = frequency + tixFrequencyHash[price + 1]
    m = [tixFrequencyHash, m].max
  }
  p m
end

Impressed? I am, at least. Medium doesn’t like those long lines though, at least not on my screen, so I’m bummed about that.

The concept here is a frequency hash. Actually, this isn’t the first time this specific kind of time improvement has come up for me in a code challenge, so if you’re interviewing I’d recommend looking at and thinking about frequency hashes. A frequency hash for our previous example array would look like this:

# the array
[5,1,6,8,5,2,2,1,6,4]
# frequency hash
{5=>2, 1=>2, 6=>2, 8=>1, 2=>2, 4=>1}

Here’s the first bit of mumbo-jumbo in our function:

tixFrequencyHash = ticketsArray.sort.reverse.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}

This has two parts. One, a boilerplate (but fancy!) Ruby way to create a frequency hash from an array:

tixFrequencyHash = ticketsArray.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}

And then our little edit: We’re sorting and reversing the array first, so that the frequency hash goes in order from largest to smallest value (ticket price, or whatever it’s supposed to be). So for our example:

{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}

That’s the key trick up our sleeve. Now we can read this left to right to find the runs, no nested iteration necessary. Do you see it?

tixFrequencyHash.each{|price, frequency|
  tixFrequencyHash[price] = frequency + tixFrequencyHash[price + 1]
}

To each value in the hash, we add the value assigned to the key that’s one more than the current key. Let’s see how that looks for our example:

#initial state
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[8] = tixFrequencyHash[8] + tixFrequencyHash[9]
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[6] = tixFrequencyHash[6] + tixFrequencyHash[7]
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[5] = tixFrequencyHash[5] + tixFrequencyHash[6]
{8=>1, 6=>2, 5=>4, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[4] = tixFrequencyHash[4] + tixFrequencyHash[5]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>2}
# tixFrequencyHash[2] = tixFrequencyHash[2] + tixFrequencyHash[3]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>2}
# tixFrequencyHash[1] = tixFrequencyHash[1] + tixFrequencyHash[2]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>3}

As it goes through, it collects the length of each run in the value assigned to the key of the start of the run! The 6s, 5s and 4s get added up to form 4=>5.

No nested iteration — much faster.

Comment with your improvements, and next week I’ll talk about the second problem from the same code challenge.

edit Jan 13th 2021 —(1) had a paragraph duplicated in the wrong place, didn’t make any sense; (2) demonstration of frequency hash had errors