6 lines O(nlogn) Ruby


  • 1

    Idea from TianhaoSong's solution.

    def max_envelopes(envelopes)
      ends = []
      envelopes.sort_by { |w, h| [w, -h] }.each { |_, h|
        i = (0...ends.size).bsearch { |i| ends[i] >= h }
        ends[i || ends.size] = h
      }
      ends.size
    end
    

    If we had Ruby 2.3 here, this should also work and would be nicer:

        i = ends.bsearch_index { |x| x >= h }

  • 0
    J

    @StefanPochmann Very nice solution! I had been wondering about a follow up for this question:

    What happens if the dolls have 3 dimensions instead of 2? How would the complexity change?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.