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 A0,A1,...,An-1.
And the constraints are:
- 2 <= n <= 100
- 0 < Ai < 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(n2), 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?
Top comments (7)
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:
This has several benefits:
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.
repl:
ramdajs.com/repl/?v=0.25.0#?const%...
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 secmap.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 functionJavaScript can be pretty confusing at time but I hope you stick around and again nice work :D
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. :))
The solution and explanation are great.
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.
`
I love the way you approached the problem. Shows how well you understand the techniques you opted to use.
Thanks man! :) I appreciate that!
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.