A counting technique for an apparent intractable problem

The following problem is a variation of a hacker-rank problem (this one: https://www.hackerrank.com/challenges/picking-numbers). Given a set of M numbers (M ~= 10,000) and a number N (say N = 5), write an algorithm to find the largest set amongst the M numbers such that the difference between any element of that subset is less than N. For example, if the set of M numbers is {1, 2, 3, 7} and N = 3, then the largest set that matches the criteria defined would be {1, 2, 3}. Notice that the difference between any of these numbers is always less than 3 (also, you may assume the numbers of the set M are within a known range, say M[i] in [1,1000]).

There is a linear solution to this problem using constant memory, but let’s first analyze the not-so-optimal solutions. Testing subsets by subsets is clearly intractable given that the number of subsets for a set of 10,000 elements is a massive number. Another solution could be to sort the set and then for each element get the largest subset by traversing the sorted set with 2 nested loops. It might be a feasible approach, with a pros of constant memory, however the big-O time expectation is still quite large: NLogN (the sorting) + N^2 (the two nested loops), which yields O(100,000,000). Certainly doable in a reasonable laptop, but still the moment that we move the M by one extra zero (M=100,000) it becomes intractable, so I consider this solution very limited.

The key to solve this problem in linear time and constant memory is the somewhat casual comment towards the end of the problem statement: “Also, you may assume the numbers of the set M are within a known range, say M[i] in [1,1000].”. That innocent statement unlocks the key to solve the problem in linear time with constant memory.

Given that the numbers will all fall within a fixed range, between 1 and 1000, we can count all the occurrences of these numbers by using an integer array of length 1000 (call this array S). Then, let’s think about the core of the problem: find the largest subset of numbers whose difference between any element is < N. Well, when we look at the array S, like pick an index within this array say index 4, one possible solution are all the numbers that fall into positions S[4], S[5], S[6], S[7] and S[8]. All these numbers differ by less than 5. We can do that for all the indexes in the array S, and for each index check the partial solution for the N consecutive indexes, and keep track of the max number of elements. That’s it! This loop only takes 1000*N, and the memory is constant (1000).

Let’s come up with the final big-O for this algorithm: M (initial parsing adding the numbers to S) + 1000*N. Since we assume that M >> N, then we have a final time complexity of O(M).

The image below is an explanation of the code to solve the problem, and the actual code is down below for reference. Counting techniques like this one are commonly used when the problem is constrained to finite and small ranges. Cheers, Marcelo.

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

class Solution

{

    static void Main(String[] args)

    {

        int n = 1000;

        int m = 10000000;

        int[] randomNumbers = new int[m];

        int minRange = 1;

        int maxRange = 10000;

        Random rd = new Random();

        for (int i = 0; i < randomNumbers.Length; i++)

            randomNumbers[i] = rd.Next(minRange, maxRange + 1);

        int[] slots = new int[maxRange + 1];

        for (int i = 0; i < randomNumbers.Length; i++)

            slots[randomNumbers[i]]++;

        int maxSetOfNumbers = 0;

        int solutionIndex = 0;

        for (int i = 0; i < slots.Length - n; i++)

        {

            int partialSum = 0;

            for (int j = 0; j < n; j++)

                partialSum += slots[i + j];

            if(partialSum > maxSetOfNumbers)

            {

                maxSetOfNumbers = partialSum;

                solutionIndex = i;

            }

        }

        Console.WriteLine("Max set of numbers: {0}", maxSetOfNumbers);

        /* debug only

        Console.Write("Numbers: ");

        for (int i = 0; i < n; i++)

            for (int j = 0; j < slots[solutionIndex + i]; j++)

                Console.Write("{0} ", solutionIndex + i);

        Console.WriteLine();

        */

    }

}