Welcome Reader. Thank you for being a part of The Daily Code community. We are delighted to have you on board. In the last blog, we discussed the problem of merging sorted arrays. This article will discuss the problem based on “Arrays” - “Missing Ranges.”
Important Link: Problem Link
Problem Statement:
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Understanding the problem:
1. Given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
2. A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
3. Return the smallest sorted list of ranges that cover every number exactly.
4. Each range [a,b] in the list should be output as :
“a –> b” if a!=b
“a” if a == b
Let us take an example as follows:
1.Input : nums = [0,1,3,50,75], lower = 0, upper = 99
Output : [“2”, “4-> 49”, “51-> 74”, “76-> 99”]
2.Input : nums = [-1], lower = -1, upper = -1
Output : []
Before you proceed to the solution, it is recommended that you give this problem a fair try.
Solution Approach
Traverse each element in nums using a loop. Initialize new variable start =lower.
If nums[i] == start , then nums[i] is not missing
If nums[i] > start, we add the missing range {next, nums[i] -1} and update the start value to nums[i]+1.
After we have finished the loop, we need to check whether start <= upper, ie if we need to add the range { nums[nums.length-1]+1 -> upper}.
We create a separate function getRange(num1, num2) which handles cases where num1 == num2 or num1 < num2
Solution
Complexity Analysis
Time Complexity: O(N)
Where N = length of the input array nums.
As we traverse every array element for one time, the time complexity is O(N).
Space Complexity: O(N)
We hope that this article was helpful. Join our community on Discord.
Doubts, suggestions, and feedback are always welcomed. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
“Don’t let the fear of losing be greater than the excitement of winning.” -Robert Kiyosaki.
All the best for an exciting future! Happy Coding!
Regards,
The Daily Code Team.