Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Mahendran
Mahendran

Posted on • Edited on • Originally published atmahendranv.github.io

     

LeetCode — Median of Two Sorted Arrays

Problem definition ishere.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Sample inputs

Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2.
Enter fullscreen modeExit fullscreen mode
Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Enter fullscreen modeExit fullscreen mode

TOC

What is median?

In a given sorted data set, median is the middle element. It is not neccessarily themean/average.

[2, 2,3, 4, 10]

⇨ mean = (2+2+3+4+10)/5 = 4.2

⇨ median 3

...

Draft

Few things to note, before solving the problem:

  1. Input arrays are already sorted. That means, we don't have to sort the resulting array if we pick the elements in correct order.
  2. Result asking for median of the resulting array, not the array itself. So, we don't have to allocate a new arrray at all.
  3. From the inputs, if total number of elements is odd, we'll pick a single element. Otherwise, average of the two elements in the middle.

...

Hypothesis

Iteration

Since we're looking for median, we don't have to iterate all the way uptom + n. Here, m and n are size of each array. For odd number of elements, we pick one median and it's two for even numbers. So, how far do we iterate?

m+nmedian indexvis.
31[0,1, 2]
41,2[0,1, 2, 3]
52[0, 1,2, 3, 4]
62,3[0, 1,2, 3, 4, 5]

Notice that I mentioned median index and index starts with zero. So, when I mention first index, it is the second element in the result array.

Can we formulate the number here?
4 ⇨ 4/2 = 2 [m1 = 1, m2 = 2]
5 ⇨ 5/2 = 2 [m2 = 2]

For a given total(m+n), we'll iterate up to(m+n)/2 index. If the total is odd, pick only m2, otherwise average of m1 + m2. So,last two iterations matters most.

Picking elements

In order to fill elements in result array, we have to pick the least element of the two arrays.

Input:[1, 4][2, 9]0 --> [1]1 --> [1,2]2 --> [1,2,4]3 --> [1,2,4,9] // we don't move this far — iteration stops at index 2
Enter fullscreen modeExit fullscreen mode

What if same number present in two arrays? 🤔 It doesn't matter. Both will be placed adjacent in array anyway, and we're just focusing on the value.

So, we need to keep two pointers(i, j) for both arrays to pick element in head. What do we pick?

if (nums1[i] < nums2[j]) {   m2 = nums2[i]   i++} else {   m2 = nums2[j]   j++}
Enter fullscreen modeExit fullscreen mode

There is a special case as well. What if one of the arrays ran out of elements?. In such case, we have to pick element from the other array and move pointer accordingly.

// num1 reached its endif (num1.size == i) {   m2 = nums2[j]   j++}
Enter fullscreen modeExit fullscreen mode

Handling odd/even number of elements

Through each iteration, we update medians m1 & m2. At the end, last two picks (or just one) considered for median. Values always stored in m2 and on each iteration, m1 will cache the previous value of m2. Things will be much clear with actual solution below.

...

Solution

Putting all the above together, we have the solution here. Again, I added comments inline.

funfindMedianSortedArrays(nums1:IntArray,nums2:IntArray):Double{// Pointers to arrayvari=0varj=0// Identified mediansvarm1=0varm2=0// iterate upto - (m+n)/2for(kin0..(nums1.size+nums2.size)/2){// caching previous valuem1=m2if(i==nums1.size){// First array ran out of elements, pick secondm2=nums2[j]j++}elseif(j==nums2.size){// Second array ran out of elements, pick firstm2=nums1[i]i++}elseif(nums1[i]<nums2[j]){// First array element is lowerm2=nums1[i]i++}else{// Second array element is lowerm2=nums2[j]j++}}// For even numbers avg of m1 & m2, m2 otherwisereturnif((nums1.size+nums2.size)%2==0){(m1+m2)/2.0}elsem2.toDouble()}
Enter fullscreen modeExit fullscreen mode

🧑‍💻🧑‍💻 peace 🧑‍💻🧑‍💻

Top comments(0)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

Android / Kotlin / Python / KMP
  • Location
    India
  • Work
    Senior android developer at Omnissa
  • Joined

More fromMahendran

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp