Picking Numbers Algorithm

Howdy fellow programmers! 👋🏽

In this article, I'll be describing how I solved the Picking Numbers Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to 1.

Example

a = [1, 1, 2, 2, 4, 4, 5, 5, 5]

There are two subarrays meeting the criterion: [1, 1, 2, 2] and [4, 4, 5, 5, 5]. The maximum length subarray has 5 elements.

Function Description

Complete the pickingNumbers function in the editor below.

pickingNumbers has the following parameter(s):

• int a[n]: an array of integers

Returns

• int: the length of the longest subarray that meets the criterion

Input Format

The first line contains a single integer n, the size of the array a.

The second line contains n space-separated integers, each an a[i].

Sample Input 0:

Sample Output 0:

Explanation:

We choose the following multiset of integers from the array: {4, 3, 3}. Each pair in the multiset has an absolute difference <=1 (i.e., |4 - 3| = 1 and |3 - 3| = 0), so we print the number of chosen integers, 3, as our answer.

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Solution 🔎

In plain English, you'll be given an array and you need to return the longest subarray where the absolute difference between any two elements is less than or equal to 1. The problem is pretty straightforward this time.

To test our solution, let's consider the same sample input from above.

a = [1, 1, 2, 2, 4, 4, 5, 5, 5]

Let's write down the steps we'll use to solve this problem.

# Sort array 'a' to loop through it and get the first smallest integer
# Check if the absolute difference between a given integer and the smallest meets the condition
# Once this condition breaks, add all integers that initially met the condition to a new subarray 
# Add this new subarray to another main array to track all subarrays
# Then remove all elements in this subarray from the initial array 'a'
# Clear the subarray to store the next elements
# Break out of the loop when we get to the last element and return the length of the longest subarray

Step 1️⃣: Sort the array and get the smallest integer.

It makes sense to sort the array because the difference between any two elements is less than or equal to 1. This means integers will be next to each other in the subarrays😏.

We'll also need to create some variables to track the main array containing subarrays and a counter for tracking elements in a.

# Sort array 'a' to loop through it and get the first smallest integer
def pickingNumbers(a):
    # Write your code here
    counter = 0           # variable for tracking elements in 'a'
    res = []              # array for storing individual subarrays
    main_res = []         # main array for storing all subarrays
    a.sort()              # sort the array 'a'

    while counter <= len(a):
        smallest = min(a)
    ...

Step 2️⃣: Check array elements against the condition.

Here we'll check each element in the array against the condition and create subarrays of elements that match.

The only way to know when the condition becomes invalid is to compare elements against the smallest during each iteration.

# Check if the absolute difference between a given integer and the smallest meets the condition
# Once this condition breaks, add all integers that initially met the condition to a new subarray 
# Add this new subarray to another main array to track all subarrays

def pickingNumbers(a):
    # Write your code here
    counter = 0           # variable for tracking elements in 'a'
    res = []              # array for storing individual subarrays
    main_res = []         # main array for storing all subarrays
    a.sort()              # sort the array 'a'

    while counter <= len(a):
        smallest = min(a)            # track the smallest element in each array iteration
        for i in range(len(a)):
            if not abs(a[i] - smallest) <= 1:
                break
            res.append(a[i])        # add elements to the subarray

        main_res.append(res)        # add subarrays to the main array
    ....

Step 3️⃣: Create a result array of subarrays.

To keep checking elements against the condition stated in the problem, we have to do away with those that have passed, so we can check subsequent elements until the array ends.

# Then remove all elements in this subarray from the initial array 'a'
# Clear the subarray to store the next elements
# Break out of the loop when we get to the last element and return the length of the longest subarray

def pickingNumbers(a):
    # Write your code here
    counter = 0           # variable for tracking elements in 'a'
    res = []              # array for storing individual subarrays
    main_res = []         # main array for storing all subarrays
    a.sort()              # sort the array 'a'

    while counter <= len(a):
        smallest = min(a)            # track the smallest element in each array iteration
        for i in range(len(a)):
            if not abs(a[i] - smallest) <= 1:
                break
            res.append(a[i])        # add elements to the subarray

        main_res.append(res)        # add subarrays to the main array

        a = a[i:]            # remove subarray elements from the initial array 'a'
        res = []             # clear the subarray to store subsequent elements
        if len(a) <= 1:      # break out of the loop on the last element.
            break

    return len( max(main_res, key=len) )

Note: The smallest number will always change after each subarray addition to the main array.

Conclusion

Although not as concise as previous algorithms on this blog, it expresses all the steps followed to solve the problem.

Thanks for reading!

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻