Let's Solve: Code Challenge - Picking Numbers

Hey hey, welcome to my first Let's Solve! We're going to be solving an algorithm code challenge called Picking Numbers, which is categorized as an easy problem - so our goal is to not only solve the problem, but make our solution fast. In this post I'm going to be outlining and applying the general steps I take when solving a problem like this. I hope to turn this into a series as I run into problems and solutions that I find interesting. :)

I'm building a portfolio of my personal Hacker Rank algorithm problem solutions, which can be found on GitHub.

---

Problem

The first step that I take in solving these problems is obvious, taking a look at the problem statement:

Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is <= 1.

From this, we can see that we will be dealing with an unsorted list.

---

Input/Constraints & Examples

The next step I take, whether I'm solving an algorithm problem in person or online, is figuring out the input/constraints. For online problems, the input/constraints are most likely listed, while in person you may have to ask for them.

For Picking Numbers, the input is:

• The first line contains a single integer, n, denoting the size of the array.
• The second line contains n space-separated integers describing the respective values of A₀,A₁,...,A_n-1.

And the constraints are:

• 2 <= n <= 100
• 0 < A_i < 100
• The answer will be >= 2

The example input given is:

6
4 6 5 3 3 1

This results in the output 3, because we can satisfy the problem by choosing 3, 3, 4. The biggest difference between any two of these numbers is 1.

---

Brute Force

After I understand the problem, constraints, and examples, I look at finding a brute force way of solving the problem. Sorting is always on my mind when trying to solve problems: can sorting help me in this case? For brute force solving this problem, yes it can. We can first sort the array, and then loop through it while keeping track of the longest sequence of numbers that are within one of each other. Our sorted array will look like this: 1, 3, 3, 4, 5, 6.

Then looping through the sorted array, while keeping track of the longest sequence, we will find the longest sequence is: 3, 3, 4.

---

Optimization & Walkthrough

So, our brute force solution works for this small array input. But what if the input gets really big? The sorting at the beginning is going to take too much time, possibly O(n²), which will most likely cause the problem to bust. How could we optimize this? Well, we know that we can look for a sequence to satisfy the problem. This makes me wonder if I can create a sequence in a way that doesn't use sorting.

Now this brings me to something else I keep handy in my algorithm toolbox: hash maps. I find hash maps to be particularly useful when solving problems where the order of things doesn't matter, they help us get rid of duplicates, sort, and all sorts of things. Can a hash map help solve this problem? I think it can. This is what a basic hash map looks like, an index, known as a key, mapping to another value:

We can use a hash map to map the numbers found in our input array to the number of times they appear. This means that our input array values are acting as the keys, and the amount of times they appear are acting as the values. We can then loop through the hash map as if it were the sorted array, and find our longest sequence! Our hash map for the example input will look like this:

We can see our output value is the highest sum of two key values next to each other:

Now that I've drawn the hash map out, I can see that each index of the hash map (0-6) only needs one input value... so we can use an array instead of a hash map. :)

---

Implementation

Now it's time to figure out which language I want to solve this in. Since I want to get better at JavaScript, I'm going to use that!

The first thing that we want to do is read in our values from the input, and initialize our key-value map array with all 0's. We know that there can't be more than 100 array values, and the array values cannot be an integer higher than 100, so we can do that like so:

function main() {
    // Read input
    var n = parseInt(readLine());
    a = readLine().split(' ');
    a = a.map(Number);

    // Construct our map
    var map = new Array(100);
    map.fill(0);
}

Now we want to populate map with a for-loop. The key values of map will have values that correspond with the amount of times that key appears in the input array. So as we loop through the input array, we can just bump the value of each key by one:

function main() {
    // Read input
    var n = parseInt(readLine());
    a = readLine().split(' ');
    a = a.map(Number);

    // Construct our map
    var map = new Array(100);
    map.fill(0);

    // Populate map
    for(var i = 0; i < a.length; i++){
        map[a[i]]++;
    }
    console.log(map);
}

After running what we have with the example input:

6
4 6 5 3 3 1

We can see that map looks like this: [0, 1, 0, 2, 1, 1, 1].

The final thing we need to do is find the max sum of two values with keys within one of each other, this will be our result. Let's create a max value that keeps track of the highest sum, and then loop through the map to update our max value whenever adding each key's value to the key's value before it in the map sums higher than the current max:

function main() {
    // Read input
    var n = parseInt(readLine());
    a = readLine().split(' ');
    a = a.map(Number);

    // Construct our map
    var map = new Array(100);
    map.fill(0);

    // Populate map
    for(var i = 0; i < a.length; i++){
        map[a[i]]++;
    }

    // Find the max sum of two values with keys within one of each other
    var max = 0;
    for(var i = 1; i < map.length; i++){
        if(map[i] + map[i - 1] > max){
            max = map[i] + map[i - 1];
        }
    }
    console.log(max);
}

---

Results

Let's run our code on all of Hacker Rank's test cases...

Drum roll please!

Boom! All of our test cases pass in O(n) time. :)

---

Takeaways

I always try to reflect, and think about what I learned by solving a code challenge. For this one, my takeaway is that hash maps can be useful when dealing with unsorted lists. In this case, we were sort of able to create an appearances "attribute" for each value of the array using a hash map - this was useful, and much faster than sorting the entire input array.

Please add to the discussion below! How would/did you solve this problem? Need help?

Comments

[Tobias Salzmann]

I like the approach! Maybe a bit of feedback:

The necessity of using comments to structure code is often an indication for a function being too long. Your code is already well structured, so you can directly extract the parts of your code as functions:

function main() {
    var numbers = readInput();
    var numberCounts = constructAndPopulateMap(numbers);
    var maxSum = findMaxSumOfAdjacentNumbers(numberCounts);

    console.log(maxSum);
}

function readInput() {
  var n = parseInt(readLine());
  a = readLine().split(' ');
  a = a.map(Number);
  return a;
}

function constructAndPopulateMap(numbers){
  var map = new Array(100);
    map.fill(0);

  for(var i = 0; i < a.length; i++){
        map[a[i]]++;
  }

  return map;
}

function findMaxSumOfAdjacentNumbers(map) {
  var max = 0;
  for(var i = 1; i < map.length; i++){
    if(map[i] + map[i - 1] > max){
      max = map[i] + map[i - 1];
    }
  }
  return max;
}

This has several benefits:

• no comments needed
• Variables are scoped appropriately.
• You can easily test the parts of your program.
• Improved readability

Here's a solution (minus the parsing) using exclusively functions from the utility library ramda. Each number is assigned to 2 potential clusters and all that's left is to find the most common cluster.
There is quite some functional lingo in there, but it doesn't require much javascript knowledge.

const largestCluster = (numbers) => {
  const countByValue = reduceBy(inc, 0)(identity)
  const maxOccurences = pipe(countByValue, values, reduce(max, 0))

  const clusters = chain(n => [[n-1, n], [n, n + 1]])(numbers)
  return maxOccurences(clusters)
}

repl:
ramdajs.com/repl/?v=0.25.0#?const%...

[Meghan (she/her)]

Great job on solving the problem!

Just some pointers for future reference:

• new Array(100) is pretty wasteful, but I'll get back to this in a sec
• map.fill(0) in your code isn't doing anything because you don't assign the return value back to map. Array.prototype.fill is not a modifier function
• the entire first few lines could be condensed to

  let map = readLine().split(' ').map((x) => {
      return parseInt(x) + 1;
  });

JavaScript can be pretty confusing at time but I hope you stick around and again nice work :D

[Ryan]

Hey Sean, thanks for the response! I think for the way that I'm approaching the problem, that I actually need to initialize the array with 100 indices - otherwise, I couldn't map the keys to their array index positions. Also, I think fill does modify array values, as well as return the outcome of the fill. I tested that out on JSFiddle.

(Your avatar is dope btw. :))

[Rattanak Chea]

The solution and explanation are great.

var n = parseInt(readLine());
    a = readLine().split(' ');

should be using , instead of ;. And make use of a meaning name. I would also look into making use of built-in Map in ES6.

var n = parseInt(readLine()),
    numbers = readLine().split(' ');

`

[candy_man]

I love the way you approached the problem. Shows how well you understand the techniques you opted to use.

[Ryan]

Thanks man! :) I appreciate that!

[wnds]

Ryan - absolute difference in problem statement should be changed to difference only as this solution of using array indexes does not work when we have negative numbers in the input array.