Summary Ranges

🏠 ⬅️ ➡️

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b " if a != b
  • "a " if a == b

Example 1:

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

Example 2:

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

Constraints:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • All the values of nums are unique.
  • nums is sorted in ascending order.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, dimension(n) :: nums = (/ 0, 1, 2, 4, 5, 7 /)
    type(range_t), allocatable :: ranges(:)

    call solve(nums, ranges)

    do i = 1, size(ranges)
        write (*, '(A)') ranges(i)%to_string()
    end do

contains

    subroutine solve(nums, ranges)
        implicit none
        integer, intent(in) :: nums(:)
        type(range_t), allocatable, intent(out) :: ranges(:)
        integer :: i, j, k

        allocate(ranges(size(nums)))

        k = 1
        do i = 1, size(nums)-1
            if (nums(i+1) > nums(i)+1) then
                ranges(k)%start = nums(i)
                ranges(k)%end = nums(i)
                k = k + 1
            end if
        end do
        ranges(k)%start = nums(size(nums))
        ranges(k)%end = nums(size(nums))

    end subroutine solve

    type range_t
        integer :: start
        integer :: end
    contains
        procedure :: to_string => to_string_range
    end type range_t

    character(len=100) function to_string_range(self) result(str)
        implicit none
        class(range_t), intent(in) :: self

        if (self%start /= self%end) then
            str = trim(adjustl(str)) // trim(adjustl(str(self%start))) // "->" // &
                  trim(adjustl(str(self%end))) // " "
        else
            str = trim(adjustl(str)) // trim(adjustl(str(self%start))) // " "
        end if

    end function to_string_range

end program main
❌ Compiled
❌ Executed
❌ Correct 
module range_cover
    implicit none
    private
    public :: range_cover_main

contains

    subroutine range_cover_main()
        integer, parameter :: nums(7) = [0, 1, 2, 4, 5, 7, 9]
        integer :: i, j, k
        integer :: ranges(size(nums), 2)

        ! Initialize the ranges array with the first element of nums
        do i = 1, size(nums)
            ranges(i, 1) = nums(i)
            ranges(i, 2) = nums(i)
        end do

        ! Sort the ranges array by the first element of each range
        call sort_ranges(ranges)

        ! Merge the ranges
        do i = 2, size(nums)
            if (ranges(i, 1) == ranges(i - 1, 2) + 1) then
                ranges(i - 1, 2) = ranges(i, 2)
            else
                ranges(i, :) = ranges(i, :)
            end if
        end do

        ! Print the ranges
        do i = 1, size(nums)
            if (ranges(i, 1) == ranges(i, 2)) then
                write (*, '(A, I0, A)') ' ', ranges(i, 1), ' '
            else
                write (*, '(A, I0, A, I0, A)') ' ', ranges(i, 1), '->', ranges(i, 2), ' '
            end if
        end do

    contains

        subroutine sort_ranges(ranges)
            integer, intent(inout) :: ranges(:, :)
            integer :: i, j

            do i = 2, size(ranges, 1)
                do j = i, 1, -1
                    if (ranges(j, 1) > ranges(i, 1)) then
                        ranges(j + 1, :) = ranges(j, :)
                    else
                        exit
                    end if
                end do
                ranges(j + 1, :) = ranges(i, :)
            end do
        end subroutine sort_ranges

end subroutine range_cover_main
end module range_cover
🌐 Data from online sources 
from typing import List

def find_ranges(nums: List[int]) -> List[str]:
    result = []
    n = len(nums)
    if n == 0: 
        return result

    start = nums[0]
    for i in range(1, n):
        if nums[i] > nums[i-1] + 1:
            if start == nums[i-1]:
                result.append(str(start))
            else:
                result.append(str(start) + "->" + str(nums[i-1]))
            start = nums[i]

    if start == nums[n-1]:
        result.append(str(start))
    else:
        result.append(str(start) + "->" + str(nums[n-1]))

    return result

The algorithm involves iterating through the input array and using a variable named start to keep track of the beginning of the current range. For each element, we compare it with the previous element to check if they form a continuous range by verifying if the current element is greater than the previous element plus 1. If they don't form a continuous range, we know that the current range has ended and a new range starts at the current element. So, we add the current range to the result in the required format and update the start variable to the current element. This process continues until all elements are processed. Finally, we add the last range to the result in the required format.

Since the input array is sorted and unique, this greedy approach ensures that we find the smallest sorted list of ranges that cover all the numbers in the array.

🌐 Data from online sources 
#include <vector>
#include <string>

std::vector<std::string> find_ranges(std::vector<int>& nums) {
    std::vector<std::string> result;
    int n = nums.size();
    if (n == 0) return result;

    int start = nums[0];
    for (int i = 1; i < n; ++i) {
        if (nums[i] > nums[i-1] + 1) {
            if (start == nums[i-1])
                result.push_back(std::to_string(start));
            else
                result.push_back(std::to_string(start) + "->" + std::to_string(nums[i-1]));
            start = nums[i];
        }
    }

    if (start == nums[n-1])
        result.push_back(std::to_string(start));
    else
        result.push_back(std::to_string(start) + "->" + std::to_string(nums[n-1]));

    return result;
}

The algorithm involves iterating through the input array and using a variable named start to keep track of the beginning of the current range. For each element, we compare it with the previous element to check if they form a continuous range by verifying if the current element is greater than the previous element plus 1. If they don't form a continuous range, we know that the current range has ended and a new range starts at the current element. So, we add the current range to the result in the required format and update the start variable to the current element. This process continues until all elements are processed. Finally, we add the last range to the result in the required format.

Since the input array is sorted and unique, this greedy approach ensures that we find the smallest sorted list of ranges that cover all the numbers in the array.