Straight to the Point !

Are you landed to this page and rushing for the immediate solution in javascript. here you go !!

1. 1. Step 1: ....
2. 1. Step 2: ....
3. 1. Step 3: ....

1var findMissingRanges = function(nums, lower, upper) {
2};

On High level note, It worth to read in detail for a better understanding.
This is one of the Facebook interview question and Refer to Similar Leet code problem as well - 415. Add Strings

Table of Contents

• Problem Statement
• Constraints
• Expected
• Test Cases
• Foot Note
• Solution Intro
• Solutions
  • Brute Force
  • Approach 1: Linear Scan
  • $Approach-2$
  • Time Optimized
  • Space Optimized
• Other Possible Questions
  • $Question-1$
  • $Question-2$
  • $Question-3$
  • $Question-4$

Problem Statement

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:

1. "a->b" if a != b
2. "a" if a == b

1String [] findMissingRanges(number[] nums, number lower, number upper)

Constraints

1. -109 <= lower <= upper <= 109
2. 0 <= nums.length <= 100
3. lower <= nums[i] <= upper
4. All the values of nums are unique.

Expected

1. Sum of Two String return in String

Test Cases

1. Input = nums = [0,1,3,50,75], lower = 0, upper = 99 Output = ["2","4->49","51->74","76->99"]
   Explanation: The ranges are:
   [2,2] --> "2"
   [4,49] --> "4->49"
   [51,74] --> "51->74"
   [76,99] --> "76->99"
   
2. Input = nums = [-1], lower = -1, upper = -1 Output = []
   Explanation: There are no missing ranges since there are no missing numbers.

Foot Note

Complexity 1: Any solution must have time and space complexities of at least O(N) to deal with the array of N integers. A relatively simple solution considering all possible contiguous subarrays, or in fact any solution counting the valid subarrays one-by-one, would require a time complexity of at least O(N^2). However, a number of observations can allow this to be optimized down to the ideal time complexity of O(N). For example, letting L[i] be the number of valid subarrays ending at index i (useful to compute on the way to the final answer), consider how we might efficiently compute L[i] for each i from 1 to N by reusing past information rather than computing it from scratch.
Complexity 2: When analyzing such a solution, note that even if we’re computing N values L[1..N], and computing any single one of those values might take on the order of N steps, the overall time complexity will not necessarily be O(N^2) - we should instead consider how many steps may occur in total across all N of them in the worst case.

Solution Intro

Lets see the list of approaches and their complexities.

1. Approach 1: Elementary Math
2. Approach 2: Using type casting operators.
3. Approach 3: Computing G[i] for each i from 1 to N is a promising approach, but we’ll still need to consider how to do so as efficiently as possible. We can observe that it’s not possible to compute G[i] purely based on the values of G[i-1], a[i-1], and a[i]; we may need more information about earlier a values as well, but would like to avoid simply scanning over all of them. Out of earlier indices j (such that j < i), we can consider which indices are worth considering as potential candidates for G[i] - for example, if there exists a pair of indices j and k such that j < k and a[j] < a[k], can index j ever be a candidate for G[i] for any i > k? If we can maintain information about the set of these possible candidate indices as we go through the array, it’s possible to efficiently determine the one that’s actually equal to G[i] for each i.

Solutions

With no further due, lets take a example of code solutions.

Brute Force

Description

1var findMissingRanges = function(nums, lower, upper) {
2};

Approach 1: Linear Scan

Basically, Program need to iterate the given number nums array and find missing series using another method formatMissingNumbers to update the given pattern format them "4->49"

1. Step 1: Initialize the array variable result.
   
2. Step 2: Initialize the integer variable previous with computing lower minus one (lower - 1).
   
3. Step 3: Iterate the given number nums array.
   
4. Step 3.1: Inside Loop, Initialize the integer variable current with value current indexed number nums[i] if its not last item else store the upper value with adding one (1).
   
5. Step 3.2: If lower value which is previous is still lesser than or equal to current value then read the previous + 1 (lower value) and current - 1 (upper value) to generate those series using formatMissingNumbers.
   
6. Step 3.2: Create formatMissingNumbers function to find all the missing numbers passsing previous plus 1 (previous + 1) and current minus 1 (current - 1).
   
7. Step 3.3: Push the Formatted value to result array.
   
8. Step 3.3: Assign the current value to previous variable.
   
9. Step 4: Return the result.
   
10. Step 5: In formatMissingNumbers function, read the lower and upper value.
    
11. Step 6: Return the lower if lower and upper are same.
    
12. Step 7: Else, format the number like ${lower} -> ${upper}.
    

1var findMissingRanges = function(nums, lower, upper) {
2    const result = [];
3    let previous = lower - 1;
4    function formatMissingNumbers(lower, upper) {
5      if (lower === upper) {
6        return lower.toString()
7      }
8      return lower.toString() + upper.toString()
9    }
10    // iterate the given numbers.
11    for(let i=0;i<=nums.length;i++) {
12      let current = (i < nums.length) ? nums[i] : upper + 1;
13      // add the missing numbers.
14      if(previous + 1 <= current - 1) {
15        result.push(
16          formatMissingNumbers(
17            previous + 1,
18            current - 1
19          )
20        )
21      }
22      // assign current value to previous
23      previous = current
24    }
25    return result;
26};

$Approach-2$

1var findMissingRanges = function(nums, lower, upper) {
2  // Code goes here...
3}

$Time-Optimized$

Coming Soon...

1Code goes here...

1Code goes here...