Identifying and collecting consecutive ranges from an array

Question

Task

Given int[] arrays such as I have to identify consecutive ranges and build a corresponding String

Another example would be

---

Notes

I can assume that the array is already ordered and there are no overlaps in the ranges.

Also, the array might be empty.

---

Ideas

I know how to build a string that just lists all numbers, like 4, 5, 6, 8, 14, 15, 16 but I have no idea how to identify the ranges and especially how to add a ~ between them.

I thought maybe regex might be usefull here, but I am unsure.

Answer 1

Explanation

You can simply iterate from left to right and maintain ranges while doing so.

For that, just remember the start of a range and the last value in each iteration. Then you can easily figure out if a range just stopped or is continuing. If it stopped, conclude the range and start the next.

For the special case of an empty array, just add a simple if to the start of the method, to handle it separately.

---

Build ranges

public static String buildRanges(int[] values) {
    if (values.length == 0) {
        return "";
    }

    StringJoiner result = new StringJoiner(", ");

    int rangeStart = values[0];
    int lastValue = values[0];
    // Skip first value to simplify 'lastValue' logic
    for (int i = 1; i < values.length; i++) {
        int value = values[i];

        if (value != lastValue + 1) {
            // Range ended, wrap it up
            int rangeEnd = lastValue;
            result.add(rangeStart == rangeEnd
                ? Integer.toString(rangeStart)
                : rangeStart + "~" + rangeEnd);
            rangeStart = value;
        }

        lastValue = value;
    }

    // Conclude last range
    int rangeEnd = lastValue;
    result.add(rangeStart == rangeEnd
            ? Integer.toString(rangeStart)
            : rangeStart + "~" + rangeEnd);

    return result.toString();
}

Simplify

To tackle the code duplication and to improve readability, I would suggest to also introduce a helper method rangeToString:

public static String rangeToString(int rangeStart, int rangeEnd) {
    return rangeStart == rangeEnd
        ? Integer.toString(rangeStart)
        : rangeStart + "~" + rangeEnd);
}

The code then simplifies to:

public static String buildRanges(int[] values) {
    if (values.length == 0) {
        return "";
    }

    StringJoiner result = new StringJoiner(", ");

    int rangeStart = values[0];
    int lastValue = values[0];
    // Skip first value to simplify 'lastValue' logic
    for (int i = 1; i < values.length; i++) {
        int value = values[i];

        if (value != lastValue + 1) {
            // Range ended, wrap it up
            result.add(rangeToString(rangeStart, lastValue);
            rangeStart = value;
        }

        lastValue = value;
    }

    // Conclude last range
    result.add(rangeToString(rangeStart, lastValue);

    return result.toString();
}

---

OOP solution

If you feel like, you can also introduce dedicated Range classes to solve this. Might be a bit overkill in this particular situation but still.

Let us first create a Range class that knows its start and end. Furthermore, it can convert itself to a String properly and you can attempt to increase the range.

public final class Range {
    private final int start;
    private int end;

    public Range(int value) {
        start = value;
        end = value;
    }

    public boolean add(int value) {
        if (value != end + 1) {
            return false;
        }
        end = value;
        return true;
    }

    @Override
    public String toString() {
        return start == end
            ? Integer.toString(start)
            : start + "~" + end;
    }
}

And now you can easily use that in a simple loop:

public static String buildRanges(int[] values) {
    if (values.length == 0) {
        return "";
    }

    StringJoiner result = new StringJoiner(", ");

    Range range = new Range(values[0]);
    // Skip first value to simplify logic
    for (int i = 1; i < values.length; i++) {
        int value = values[i];

        if (!range.add(value)) {
            // Range ended, wrap it up
            result.add(range.toString());
            range = new Range(value);
        }
    }

    // Conclude last range
    result.add(range.toString());

    return result.toString();
}

Collecting to List<Range>

This approach has the advantage that you can also collect to something like a List<Range> ranges and then continue working with the data, instead of only going to a String. Example:

public static List<Range> buildRanges(int[] values) {
    if (values.length == 0) {
        return List.of();
    }

    List<Range> ranges = new ArrayList<>();

    Range range = new Range(values[0]);
    // Skip first value to simplify logic
    for (int i = 1; i < values.length; i++) {
        int value = values[i];

        if (!range.add(value)) {
            // Range ended, wrap it up
            ranges.add(range);
            range = new Range(value);
        }
    }

    // Conclude last range
    ranges.add(range);

    return ranges;
}

In particular useful if you also add some getStart() and getEnd() method to the Range class.

---

Notes

Note that the method will likely behave funky if the array contains duplicates. You did not specify what to do in that case, so I simply assumed duplicates will not exist for your use case.

Answer 2

Try this.

static String summary(int[] input) {
    int length = input.length;
    if (length == 0) return "";
    StringBuilder sb = new StringBuilder();
    new Object() {
        int start = input[0];
        int end = input[0];
        String separator = "";

        void append() {
            sb.append(separator).append(start);
            if (start != end)
                sb.append("~").append(end);
            separator = ", ";
        }

        void make() {
            for (int i = 1; i < length; ++i) {
                int current = input[i];
                if (current != end + 1) {
                    append();
                    start = current;
                }
                end = current;
            }
            append();
        }
    }.make();
    return sb.toString();
}

public static void main(String[] args) {
    System.out.println(summary(new int[] {4, 5, 6, 8, 14, 15, 16}));
    System.out.println(summary(new int[] {13, 14, 15, 16, 21, 23, 24, 25, 100}));
}

output:

4~6, 8, 14~16
13~16, 21, 23~25, 100

Answer 3

Say you have the following Interval class:

public class Interval {
    public final int min;
    public final int max;

    public Interval(int min, int max) {
        this.min = min;
        this.max = max;
    }

    public Interval(int minmax) {
        this(minmax, minmax);
    }

    public static List<Interval> toIntervals(int... values) {
        List<Interval> list = new ArrayList<>();
        for (int val: values) {
            addInterval(list, val, val);
        }
        return list;
    }

    private static void addInterval(List<Interval> list, int min, int max) {
        int i = 0;
        while (i < list.size()) {
            Interval cur = list.get(i);
            if (max < cur.min-1) {
                break;
            } else if (cur.max >= min-1) {
                min = Math.min(min, cur.min);
                max = Math.max(max, cur.max);
                list.remove(i);
            } else {
                ++i;
            }
        }
        list.add(i, new Interval(min, max));
    }

    @Override
    public String toString() {
        if (min == max) {
            return Integer.toString(min);
        }
        return min + "~" + max;
    }
}

You can convert the list of numbers in your examples to lists of intervals:

    List<Interval> list = Interval.toIntervals(4, 5, 6, 8, 14, 15, 16);

Or:

    List<Interval> list = Interval.toIntervals(13, 14, 15, 16, 21, 23, 24, 25, 100);

And print lists like that:

    System.out.println(list.stream()
            .map(Interval::toString)
            .collect(Collectors.joining(", ")));

Answer 4

It is a int-to-string conversion, not a cast in java sence which means (TYPE2)OBJECTOFTYPE1 for instance int-to-double (widening) or Object-to-String.

The ranges one has to do oneself.

int[] a = {13, 14, 15, 16, 21, 23, 24, 25, 100};

StringBuilder sb = new StringBuilder();
if (a.length > 0) {
    for (int i = 0; i < a.length; ++i) {
        if (sb.length() != 0) {
            sb.append(", ");
        }
        sb.append(Integer.toString(a[i]));

        int rangeI = i;
        while (a[i] != Integer.MAX_VALUE && a[i] + 1 == a[i + 1]) {
            ++i;
        }
        if (i != rangeI) {
            sb.append('~').append(Integer.toString(a[i]));
        }
    }
}
return sb.toString();

You can do append(a[i]) as there is an overloaded method that does internally a conversion. For clearity not done.

The separation by comma is quite standard.

And for every element check its range of increasing followers.

As java ignores integer overflow, the check on MAX_VALUE.

Answer 5

Convert the integers to strings and append them using the StringBuilder class of Java: https://www.geeksforgeeks.org/stringbuilder-class-in-java-with-examples/

StringBuilder str = new StringBuilder();

and append the numbers and '~' (tilda) sign by using:

str.append(start_number);
str.append('~');
str.append(end_number);