CtCI - Simplify Selection Ranges

CtCI - Simplify Selection Ranges

You are given an array of numbers and must simplify the array by replacing ranges of three or more items with the shorthand N-M equivalent and returning the result as a string, sorted from lowest to highest.

Input: [1,2,5,6,7,9,12,55,56,57,58,60,61,62,64,65,70]
Output: 1,2,5-7,9,12,55-58,60-62,64,65,70

We assume the list is already sorted, otherwise we can apply Quicksort on it. Then we can start by checking each number in the list, then adding them into a different (smaller) list A if the number is part of a sequence no matter the size. Every number will be added to the second list if this one is empty. For the subsequent index K in the list with value M we will check if M == A[K-1]+1 this means the number is next in the series, for example, if A=[1] and K=2 then 2 == A[1-1]+1.

var total int = len(list)
var sub = []int{list[0]}

for k := 1; k < total; k++ {
    if list[k] == (list[k-1] + 1) {
        sub = append(sub, list[k])
        continue
    }
}

At the end of each iteration we will check if the size of the sublist is greater than two as the size for a series is three or more items. At this point we already have the series collected, we will proceed with the merge using the first and last items on each sublist.

var result []string
if len(sub) >= 3 {
    section := fmt.Sprintf("%d-%d", sub[0], sub[len(sub)-1])
    result = append(result, section)
}

As for the numbers that are not part of a valid series we can simply add them to the result as they are, in this case we are converting from integers to strings so it is easier to iterate to execute the string formatting.

for _, num := range sub {
    result = append(result, fmt.Sprintf("%d", num))
}

At this point we already have a solution, but the last numbers in the original list are not being processed because the iteration stops at one level before the end. We need to execute the same conditionals once again… or we can simply move those conditions to a different function for extensibility.

func merge(result []string, sub []int) []string {
    if len(sub) >= 3 {
        section := fmt.Sprintf("%d-%d", sub[0], sub[len(sub)-1])
        result = append(result, section)
    } else {
        for _, num := range sub {
            result = append(result, fmt.Sprintf("%d", num))
        }
    }

    return result
}

func solution(list []int) []string {
    var result []string
    var total int = len(list)
    var sub = []int{list[0]}

    for k := 1; k < total; k++ {
        if list[k] == (list[k-1] + 1) {
            sub = append(sub, list[k])
            continue
        }

        result = merge(result, sub)
        sub = []int{list[k]}
    }

    result = merge(result, sub)

    return result
}
Do you have a project idea? Let's make it together!