leetcode4.rkt

(require math/flonum)

(define (sorted-lists->stream list-1 list-2)
  (cond ((empty? list-1) list-2)
        ((empty? list-2) list-1)
        ((< (car list-1)
            (car list-2))
         (stream-cons (car list-1)
                      (sorted-lists->stream (cdr list-1) list-2)))
        (else
         (stream-cons (car list-2)
                      (sorted-lists->stream list-1 (cdr list-2))))))

(define (middle-of-a-stream stream)
  (let loop ([scanner stream]
             [middle #f]
             [is-odd #f])
    (cond ((stream-empty? scanner)
           (values middle is-odd))
          ((not middle)
           (loop (stream-rest scanner)
                 scanner
                 (not is-odd)))
          ((not is-odd)
           (loop (stream-rest scanner)
                 (stream-rest middle)
                 (not is-odd)))
          (else
           (loop (stream-rest scanner)
                 middle
                 (not is-odd))))))
          
(define (average a b)
  (/ (+ a b) 2))

(define (stream-second stream)
  (stream-first (stream-rest stream)))

(define/contract (find-median-sorted-arrays nums1 nums2)
  (-> (listof exact-integer?) (listof exact-integer?) flonum?)
  (let-values ([(middle is-odd)
                (middle-of-a-stream (sorted-lists->stream nums1 nums2))])
    (fl (if is-odd
            (stream-first middle)
            (average (stream-first middle)
                     (stream-second middle))))))

This is a solution to the Leetcode problem #4. I wanted to make it Racket because I felt like it.

Earlier versions of the program didn't use streams, so data was stored in lists — I mean Lisp lists, the cons cells — and those lists allocated too much memory. Some of the tests were failing, so I decided to give streams a shot (never used them before).

I like the algorithm I came up with for searching for the middle of the stream (middle-of-a-stream). We can't compute the middle of a stream directly unless we reached the end of the list.

So basically I'm merging two sorted lists into a stream and then I look for the median value which is in the middle of the stream.

I like my solution a lot.