1
\$\begingroup\$

I'm doing some toy problems in a variety of languages and wanted to do the following in Racket Lisp.


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"]

As you can see on the linked page I had to take two whacks at it but eventually came up with the following. How does it look? Is it idiomatic? Could I have done certain things far better?

(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))])]))))
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Your solution seems to me quite complex, with iterations, recursions, and the use of match.

Here is an alternative version with a simple linear recursion, where the result is given with lists and not with strings.

(define (missing-ranges nums lower upper)
  (cond ((> lower upper) '())
        ((null? nums) (list (list lower upper)))
        ((= lower (car nums)) (missing-ranges (cdr nums) (+ lower 1) upper))
        ((= (car nums) (+ 1 lower)) (cons (list lower) (missing-ranges nums (+ lower 1) upper)))
        (else (cons (list lower (- (car nums) 1)) (missing-ranges (cdr nums) (+ (car nums) 1) upper)))))

(missing-ranges '(0 1 3 50 75) 0 99)
'((2) (4 49) (51 74) (76 99))

(missing-ranges '(8) 0 99)
'((0 7) (9 99))

(missing-ranges '() 0 99)
'((0 99))

(missing-ranges '(3 9 88 99) 0 99)
'((0 2) (4 8) (10 87) (89 98))

(missing-ranges '(0 99) 0 99)
'((1 98))

(missing-ranges '(1 2 3) 1 3)
'()
\$\endgroup\$
1
  • \$\begingroup\$ Yeah, the string thing was an original requirement (though I control the requirements). I suppose taking those output lists and stringifying could just be a separate step. I also wanted to use generators specifically, though I think that should still be possible with your version \$\endgroup\$ Jun 17, 2020 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.