algoadvance

Leetcode 228. Summary Ranges

Problem Statement:

You are given a sorted unique integer array nums. A range [a,b] (inclusive) is defined as a range of numbers from a to b where a and b are the bounds of the range and every number in range [a,b] is in the array nums.

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 a <= x <= b is not in nums.

For example, the input nums = [0,1,2,4,5,7] should return ["0->2","4->5","7"].

Clarifying Questions:

  1. Can the input array be empty?
    • Yes, it can be. In such a case, the output should be an empty list.
  2. Is the array always sorted and unique?
    • Yes, per the problem statement.
  3. What is the range or constraint for the numbers in the array?
    • The numbers are standard 32-bit integers. -2^31 <= nums[i] <= 2^31 - 1.

Strategy:

  1. Initialize an empty list to store the result ranges.
  2. Traverse through the input array.
  3. Keep track of the start of each range.
  4. If the current number is not continuous with the previous number, close the current range and start a new range.
  5. After finishing the loop, make sure to close the last range.
  6. Convert each range to the required format (either “a” for a single number or “a->b” for a range) and add to the results.

Code:

import java.util.ArrayList;
import java.util.List;

public class SummaryRanges {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;

        int start = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                if (start == nums[i - 1]) {
                    result.add(Integer.toString(start));
                } else {
                    result.add(start + "->" + nums[i - 1]);
                }
                start = nums[i];
            }
        }

        // Close the last range
        if (start == nums[nums.length - 1]) {
            result.add(Integer.toString(start));
        } else {
            result.add(start + "->" + nums[nums.length - 1]);
        }

        return result;
    }

    public static void main(String[] args) {
        SummaryRanges sr = new SummaryRanges();
        int[] nums = {0, 1, 2, 4, 5, 7};
        System.out.println(sr.summaryRanges(nums)); // Output: ["0->2", "4->5", "7"]
    }
}

Time Complexity:

The time complexity of this solution is (O(n)), where (n) is the length of the input array nums. We traverse the array once to form the ranges.

Space Complexity:

The space complexity is (O(1)) for the additional variables used, ignoring the space required for the output list. The output list space complexity is (O(m)), where (m) is the number of ranges formed, which in the worst case is the same as (O(n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI