Variable Sized Arrays

  • + 0 comments

    O(m log m + n log n) Solution in Python The logic is the same as ryanfehr18' solution, but this will help those who have trouble understanding as to why the complexity of the loop block is O(m+n). Both keyboards and drives are sorted in ascending order. For keyboards, we move from left to right, for drives from right to left. We match the cheapest keyboard with most expensive drive, if it works, update the cur_max and try to pick up a costly keyboard. Else, we try to pick up a cheaper drive.

    def getMoneySpent(k, d, b):
        #
        # Write your code here.
        #
        keyboards = sorted(k)
        drives = sorted(d)
        m = 0
        n = len(drives) - 1
        cur_max = -1
        while m < len(keyboards) and n >= 0:
            cur_sum = keyboards[m]+drives[n]
            if  cur_sum <= b:
                cur_max = max(cur_max, cur_sum)
                m += 1 # try expensive keyboard
            else:
                n -= 1 # try cheaper drive
        return cur_max