How can I find the size of the largest subset where their maximum difference is 5?

Question

I have an array of numbers, and I am trying to find the size of the largest subset, such that all numbers in the subset are less than 5 apart. They can assume to be sorted, if necessary.

For example:

[1, 2, 5, 6, 8, 9, 15]

4 is the largest subset. (5, 6, 8, 9)

I expect that there is a simple LINQ answer, but I am not thinking of it. I could sort it and then iterate through it with each starting number, keeping track of the most from that number, but that seems very ugly and inefficient. Any ideas?

Clarification on what I want to avoid:

(1,2,5) - 3
(2,5,6) - 3
(5,6,8,9) - 4
(6,8,9) - 3
(8,9) - 2
(9) - 1
(15) - 1

How did you downvote so fast??? I literally posted this question less than 10 seconds ago. I guess you want to see sample code for what I am avoiding? — Evorlor, Sep 17 '17 at 00:34
I'll work on it later this week (and Jewish year). Meanwhile take a look at: https://stackoverflow.com/questions/1624341/getting-pair-set-using-linq in conjunction with the ConvertAll or Select function. It's gonna be ugly... — pashute, Sep 17 '17 at 09:46

Prince · Answer 1 · 2017-09-17T00:56:29.033

1

This problem can be solved by maintaining two pointers left and right.

Suppose you have a sorted array arrayof n numbers.

left = 0
right = 0
ans = INT_MIN
while right == n :
    if array[right] - array[left] < 5:
        right++
    else:
        left++
    ans = max(right - left + 1, ans)

edited Sep 17 '17 at 00:56

answered Sep 17 '17 at 00:48

Prince

431
3
16

This is answer for finding consecutive sequence, not a subset. And it is not even C#. – Antonín Lejsek Sep 17 '17 at 00:52
@AntonínLejsek As stated in my question, it can assume to be sorted. And no its not C#, but it is still a helpful answer. – Evorlor Sep 17 '17 at 00:59
This greedy strategy will work. One can prove that the longest contiguous sequence of the sorted array will be the required subset. – Prince Sep 17 '17 at 00:59
From "I could sort it ... but that seems very ugly and inefficient." I expected it is not sorted, but ok, if it is sorted it would work. – Antonín Lejsek Sep 17 '17 at 01:08

score 1 · Answer 2 · answered Sep 17 '17 at 00:58

Start by making the biggest possible set at the beginning of the sorted list. Then keep removing values from the front until the next one fits, and add as many as possible after the next one too. This makes a new set. Keep track of the largest at any given moment.

Something like this in C#:

static IEnumerable<T[]> CloseSublists<T>(this IEnumerable<T> values, Func<T, T, bool> isClose) where T : IComparable<T> {
    var window = new Queue<T>();
    var enumerator = values.GetEnumerator();

    if (!enumerator.MoveNext()) {
        return;
    }

    bool more;

    do {
        window.Enqueue(enumerator.Current);
    } while ((more = enumerator.MoveNext()) && isClose(window.Peek(), enumerator.Current));

    yield return window.ToArray();

    while (more) {
        do {
            window.Dequeue();
        } while (window.Count != 0 && !isClose(window.Peek(), enumerator.Current));

        do {
            window.Enqueue(enumerator.Current);
        } while ((more = enumerator.MoveNext()) && isClose(window.Peek(), enumerator.Current));

        yield return window.ToArray();
    }
}

and

public static T MaxBy<T, TKey>(this IEnumerable<T> items, Func<T, TKey> key) where TKey : IComparable<TKey> {
    var enumerator = items.GetEnumerator();
    enumerator.MoveNext();

    var max = enumerator.Current;
    TKey maxKey = key(max);

    while (enumerator.MoveNext()) {
        T current = enumerator.Current;
        TKey currentKey = key(current);
        int relation = currentKey.CompareTo(maxKey);

        if (relation > 0) {
            max = current;
            maxKey = currentKey;
        }
    }

    return max;
}

used as:

int[] x = {1, 2, 5, 6, 8, 9, 15};
x.CloseSublists((a, b) => b < a + 5).MaxBy(l => l.Length)

This has some unnecessary copying with `window.ToArray()`; you can avoid it by combining `MaxBy` with `CloseSublists`. It kind of makes sense to do that, too; I originally thought something like `MaxBy` was built into .NET. — Ry-, Sep 17 '17 at 01:04

Antonín Lejsek · Answer 3 · 2017-09-17T01:39:12.937

1

Based on answer of Prince, I rewrote it to C# and improved a bit:

protected int MaxSubLen(int[] arr, int diffLessThan)
{
    int l = 0, r = 0;
    while (r < arr.Length)
    {
        if (arr[r] - arr[l] >= diffLessThan)
        {
            ++l;
        }
        ++r;
    }
    return r - l;
}

and, just for fun, the sequence returning generic version:

protected IEnumerable<T> MaxSubarray<T>(IList<T> arr, Func<T, T, bool> isClose_L_R)
{
    int l = 0, r = 0, start = 0;
    while (r < arr.Count)
    {
        if (isClose_L_R(arr[l], arr[r]))
        {
            start = l;
        }
        else
        {
            ++l;
        }
        ++r;
    }
    for (int i = start; i < start + r - l; ++i)
    {
        yield return arr[i];
    };
}

edited Sep 17 '17 at 01:39

answered Sep 17 '17 at 01:24

Antonín Lejsek

6,003
2
16
18

This looks like it gets the last subarray, not the largest one? – Ry- Sep 17 '17 at 02:26
1

In some way both. It returns the last subarray it finds, but when it finds for example subarray of length 3, it never looks for subarrays shorter than 4. So the last it finds is the longest available. – Antonín Lejsek Sep 17 '17 at 02:28
Oh, `r` is just standing in as a short `arr.Count` in that last bit, then. Nice. – Ry- Sep 17 '17 at 02:49

How can I find the size of the largest subset where their maximum difference is 5?

3 Answers3