LeetCode 4. Median of Two Sorted Arrays - O( log(min(n,m)) )

[@joshsmash1160]

Thanks for shopping at my store man

[@kerensolomon2248]

I love your videos! you are the best!

[@KacyCodes]

Thank you :) If there’s other problems you want to see just let me know 🙂

[@kumarmrinal7796]

@@KacyCodes Design log storage system if you could!

[@KacyCodes]

@@kumarmrinal7796 Hey I don't actually have time to make videos right now, but the problem looked fun so I gave it a shot. Here's my submission: leetcode.com/submissions/detail/722537755/
put() is O( log n )
retrieve() is O( n )
I converted the timestamp string to an int array and used that as the key for a TreeMap. The TreeMap keeps all the keys sorted, you just have to write the comparator so it knows how to compare the int arrays. I mapped the int arrays to Lists of ids because the problem didn't say timestamps were unique (meaning multiple ids can share the same timestamp).
From there you can use TreeMap's subMap method to get the range of timestamps you want. For the granularity, I convert the start and end timestamps into int arrays. I convert the granularity string to an index for the int arrays. For the start array, set everything after the index to 0 to essentially floor the timestamp. For the end array, I increment the number at the index and set the remaining indexes to 0 so now the end array represents a ceiling exclusive. Feed that into subMap, convert it to a List, and you're done.

[@KacyCodes]

I forgot to add this to the top of getKthElement() which makes sure we always binary search on the smaller array (it just swaps nums1 and nums2 if nums1 has more elements):
if ( nums1.length > nums2.length )
return getKthElement( nums2, nums1, k );