Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
| 0 | 1 | 3 | 50 | 75 |
Lower:
0
Upper:
99
Expected Output:
["2", "4->49", "51->74", "76->99"]
This sounds like a problem of synchronizing iteration so my mind as always reaches for generators. I picture this as you holding the input nums written down on a roll of paper. You unroll this one at a time and depending on the values that are unrolled you take certain actions. Hey! That sure sounds like a state machine.
@startuml
[*] --> BuildingRange: until next number
BuildingRange --> TakingNumbers: as long as they are next in sequence
TakingNumbers --> BuildingRange: the next number is not in sequence
TakingNumbers --> [*]: done
@enduml
def missing_ranges(lower, upper, nums):
current = lower
for num in nums:
if current < num:
if current + 1 == num:
yield f'{current}'
else:
yield f'{current}->{num-1}'
current = num
else:
current += 1
if current == upper:
yield f'{current}'
elif current < upper:
yield f'{current}->{upper}'
return list(missing_ranges(int(lower), int(upper), nums[0]))| 2 | 3->49 | 50->74 | 75->99 |
I want to do this the simple way - no writing classes and such. C#9 will actually support a native top-level scripting mode, but barring that, we can use the =dotnet script= tool.
IEnumerable<string> MissingRanges(int lower, int upper, IEnumerable<int> nums) {
var current = lower;
foreach(var num in nums){
if(current < num) {
if(current + 1 == num)
yield return $"{current}";
else
yield return $"{current}->{num-1}";
current = num;
} else
current += 1;
}
if(current == upper)
yield return $"{current}";
else if (current < upper)
yield return $"{current}->{upper}";
}
IEnumerable<int> nums = Args[0].Split("\n").Select(n => Int32.Parse(n));
var (lower, upper) = (Int32.Parse(Args[1]), Int32.Parse(Args[2]));
Console.WriteLine(String.Join(", ", MissingRanges(lower, upper, nums)));dotnet script ./Implementation.cs -- "$nums" $lower $upper| 0 | 1->2 | 3->49 | 50->74 | 75->99 |
Note that while the answer is different it is due to the org mode shell provider for some reason dropping the leading 0 from vars. The algorithm itself is correct.
(require racket/generator)
(require racket/format)
(require threading)
(define (missing-ranges nums lower upper)
(in-generator
(define current lower)
(for ([num nums])
(if (< current num)
(begin
(yield (apply ~a (cons current (if (~> current (+ 1) (eq? num))
'()
`("->" ,(- num 1))))))
(set! current num))
(set! current (+ 1 current))))
(cond [(eq? current upper)
(yield (~a current))]
[(< current upper)
(yield (~a current "->" upper))])))
(sequence->list (missing-ranges (first nums) lower upper))'("2" "3->49" "50->74" "75->99")
Here I realized that I could simplify the in-loop yield. Since we yield either way, its just a matter of what we append to that yielded statement.
Ok, I don’t know what’s more Rackety, but I feel like it should include pattern matching and recursion.
(require racket/generator)
(require racket/format)
(require racket/match)
(require threading)
(define (missing-ranges nums lower upper)
(in-generator
(define (yield-missing-range current num)
(yield (if (eq? num (add1 current))
(~a current)
(~a current "->" (sub1 num)))))
(let recur ([remaining-nums nums]
[current lower])
(match remaining-nums
[(cons num rest-nums) (if (< current num)
(begin
(yield-missing-range current num)
(recur rest-nums num))
(recur rest-nums (add1 current)))]
['() (cond [(<= current upper)
(yield-missing-range current (add1 upper))])]))))
(sequence->list (missing-ranges (first nums) lower upper))'("2" "3->49" "50->74" "75->99")
const missingRanges = function * (nums, lower, upper) {
let current = lower
for(const num of nums) {
if(current < num) {
yield `${current}${(current+1) === num ? `` : `->${num-1}`}`
current = num
} else
current += 1
}
if(current < upper)
yield `${current}->${upper}`
else if(current === upper)
yield `${current}`
}
return [...missingRanges(nums[0], +lower, +upper)]| 2 | 3->49 | 50->74 | 75->99 |