1

This logic is to find the number n in the array in which the range between n and n + 5 will include the most numbers in the array. I came up with a solution but it requires a nested loop, therefore it is kind of slow. Is there any way to improve its performance? Thanks in advance.

The array is guaranteed to sorted.

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
int bestNumber = 0;
int MaxMatchFound = 0;

for (int o = 0; o < myArray.Length; o++)
{

    int TempMatchFound = 0;

    for (int i = 0; i < myArray.Length; i++)
    {
        if (myArray[i] >= myArray[o] && myArray[i] <= (myArray[o] + 5))
        {
            TempMatchFound++;
        }
    }
    if (TempMatchFound > MaxMatchFound)
    {
        bestNumber = myArray[o];
        MaxMatchFound = TempMatchFound;
    }

}

return bestNumber;
Improve this question
13
  • 4
    How fast does it need to execute, and how large of a data set will you be using for this? Commented Jun 10, 2013 at 20:48
  • 2
    Can you be guarantee the array is sorted initially? Commented Jun 10, 2013 at 20:49
  • 2
    Note that if you ensure the input data is sorted you can break out of the inner loop as soon as a value is greater than the upper bound, and you can start the inner loop at the item after the current item, rather than at the start. Commented Jun 10, 2013 at 20:49
  • 1
    @JoelCoehoorn yes it is sorted. I forgot to mention. Commented Jun 10, 2013 at 20:52
  • 4
    Also, to explain the first comment by @Servy: performance is relative and expensive. Relative in that, for the size of the sample dataset, what you have now is already more than fast enough. Expensive, because programmer time is typically more expensive (and scarce) than cpu time. Time spent optimizing this code comes at the expense of optimizing other code. If you need to optimize something, whether you spend that time here or somewhere else depends on how much data you have to look at and how long the cpu can spend on it. Commented Jun 10, 2013 at 20:53

4 Answers 4

Reset to default
5

Bucket the values, then loop over the values v and sum the associated counts for all values w that satisfy v <= w <= v + 5, then find the max count:

var buckets = myArray.GroupBy(n => n)
                     .ToDictionary(g => g.Key, g => g.Count());
var rangeCounts = 
    buckets.Keys
           .Select(v =>
               new {
                   Value = v,
                   Count = Enumerable.Range(0, 6)
                                     .Sum(i => buckets.ContainsKey(v + i) ? 
                                               buckets[v + i] : 
                                               0
                                         )
               }
    );
var bestRange = rangeCounts.MaxBy(x => x.Count);

Now, bestRange.Value is the starting point for your best range and bestRange.Count is the number of elements falling into the range [bestRange.Value, bestRange.Value + 5]. Here, I've used MaxBy.

Think this gets you linear performance. Building dictionary is linear, building rangeCounts is linear, MaxBy is linear. Even works on non-sorted.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

@ghord Then what is it? It takes O(1) time to add a single item to a dictionary. (When amortized, which it can be here.) You do that N times, that's O(N).
+1 An interesting solution. I wonder if it can be done in constant extra space.
Yes, it can be done in O(n) using O(1) constant extra space, regardless of range. See my answer.
4

Here you go: This runs in O(N) time, and O(1) memory. This forms the buckets described in other solutions, then discards them as you move through the array. The Queue is used to track which buckets are 'active' in the sense that they can be added to. The Dictionary will never have more than 6 entries in it, neither will the Queue.

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
Dictionary<int, int> counts = new Dictionary<int, int>();
Queue<int> q = new Queue<int>();

int n = 0;
int currentMaxCount = 0;


for(int i = 0; i < myArray.Length; i++)
{
    var currentNum = myArray[i];
    if(counts.ContainsKey(currentNum))
    {
        counts[currentNum]++;
    }
    else
    {
        counts[currentNum] = 1;
        q.Enqueue(currentNum);
    }

    for(int j = 1; j <= 5; j++)
    {
        if(counts.ContainsKey(currentNum - j))
            counts[currentNum - j]++;
    }

    if(q.Peek() + 5 < currentNum)
    {
        if(counts[q.Peek()] > currentMaxCount)
        {
            currentMaxCount = counts[q.Peek()];
            n = q.Peek();
        }
        counts.Remove(q.Dequeue());

    }
}

while(q.Count > 0)
{
    if(counts[q.Peek()] > currentMaxCount)
    {
        currentMaxCount = counts[q.Peek()];
        n = q.Peek();
    }
    counts.Remove(q.Dequeue());
}

Console.WriteLine("There are {0} matches between {1} and {2}", currentMaxCount, n, n + 5);
Improve this answer

7 Comments

With a nested loop, looks like that's going to be n^2. In any case this also requires O(n) extra space. Not necessarily a bad thing, but you should point that out.
It's not O(n^2) Since there's less than 5 elements that can be in that range. That nested loop is effectively O(1).
That's true only if duplicates aren't allowed.
Updated to maintain O(n) time and correctness in the case of duplicates.
Updated further to only use constant space.
|
3

Here's a solution that is O(n) and uses O(1) extra space regardless of the range.

It does a single pass through the array, always making 2N comparisons. I don't see any way to improve on this algorithm, although there are certainly micro optimizations that could squeeze a little more speed out of the implementation.

private int FindRange(int[] myArray)
{
    const int range = 5;
    int start = 0;
    int maxMatchFound = 0;
    int maxIndex = 0;
    for (int i = 0; i < myArray.Length; ++i)
    {
        if (myArray[i] > myArray[start] + range)
        {
            int matchLength = i - start;
            if (matchLength > maxMatchFound)
            {
                maxMatchFound = matchLength;
                maxIndex = start;
            }
            // move forward until within range
            do
            {
                ++start;
            } while (myArray[i] > myArray[start] + range);
        }
    }
    // Final check, from myArray[start] to end of array
    int len = myArray.Length - start;
    if (len > maxMatchFound)
    {
        maxMatchFound = len;
        maxIndex = start;
    }
    return maxIndex;

The idea here is that if a particular number a[x] falls within the range for a[i] then it will fall within the range for a[i+1], assuming that x > i. (So in your original array, the value at a[3] falls within the range of a[0], so it will also fall within the range of a[1] and a[2]).

So the index i is incremented until the value it references falls out of the range of a[start]. Then, start is incremented until a[i] is in range again. The two indexes move forward through the array in that alternating fashion.

Improve this answer

3 Comments

Doesn't work: int[] myArray = new int[]{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7}; returns 0, should return 1 (or 2).
I tried to throw some horrible data at it, and it ran in O(n). The code is a bit hard to follow. var myArray = Enumerable.Range(1, 10000).SelectMany (i => Enumerable.Range(1, i).Select (j => i)).ToArray(); produces a pyramid array with 50 million items, and it ran ~100 million times.
@Shlomo: Perhaps you'll find the new version easier to follow.
0

Here's a one-line LINQ option. Not the best in terms of performance (it iterates multiple times). Still worth noting.

var result = myArray
             .OrderByDescending(i => myArray.Count(i2 => i2 >= i && i2 <= i + 5))
             .First();
Improve this answer

1 Comment

He's specifically asking how to improve the performance. While this method is a lot less code, it's slower than what the OP already has, making this a very poor answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.