228. Summary Ranges

Задача

Дан отсортированный массив уникальных чисел. Верните наименьший список диапазонов, покрывающих все числа.

Примеры

Пример 1

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Пояснение

Диапазоны: [0,2] → “0->2”, [4,5] → “4->5”, [7,7] → “7”.

Пример 2

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

Пояснение

Диапазоны: [0,0] → “0”, [2,4] → “2->4”, [6,6] → “6”, [8,9] → “8->9”.

Решение

Решение

// Временная сложность: O(n) - линейная
// Пространственная сложность: O(n) - массив result в худшем случае содержит n элементов
 
function getRanges(arr) {
    if (arr.length === 0) return "";
 
    const result = [];
    let rangeStart = arr[0];
    let rangeEnd = arr[0];
 
    for (let i = 1; i < arr.length; i++) { // O(n) - где n длина массива arr
        if (arr[i] === rangeEnd + 1) {
            rangeEnd = arr[i];
        } else {
            result.push(rangeStart === rangeEnd ? `${rangeStart}` : `${rangeStart}-${rangeEnd}`);
            rangeStart = arr[i];
            rangeEnd = arr[i];
        }
    }
 
    result.push(rangeStart === rangeEnd ? `${rangeStart}` : `${rangeStart}-${rangeEnd}`);
 
    return result.join(",");
}

Решение 2

// Временная сложность: O(n²) - цикл O(n) * конкатенация строк O(k) на каждой итерации
// Пространственная сложность: O(n) - результирующая строка пропорциональна размеру входа
 
function getRanges(arr) {
    let result = "";
    let lastValue = null;
    let lastRange = null;
 
    arr.forEach((val, index) => {
        if (!lastValue) {
            result += val;
        } else if (lastValue + 1 === val) {
            lastRange = val;
        } else if (lastRange) {
            result += "-" + lastRange;
            result += "," + val;
            lastRange = null;
        } else {
            result += "," + val;
        }
 
        if (index === arr.length - 1 && lastRange) {
            result += "-" + lastRange;
        }
 
        lastValue = val;
    });
 
    return result;
}