LeetCode Entry

4. Median of Two Sorted Arrays

21.09.2023 hard 2023 kotlin

Median in two concatenated sorted arrays

4. Median of Two Sorted Arrays hard blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/346

Problem TLDR

Median in two concatenated sorted arrays

Intuition

We already know the target position of the median element in the concatenated array.

There is an approach with Binary Search, but it’s harder to come up with in an interview and write correctly.

Approach

We can maintain two pointers and increase them one by one until targetPos reached.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
      val targetPos = (nums1.size + nums2.size) / 2
      var i = 0
      var j = 0
      var prev = 0
      var curr = 0
      while (i + j <= targetPos) {
        prev = curr
        curr = when {
          i == nums1.size -> nums2[j++]
          j == nums2.size -> nums1[i++]
          nums1[i] <= nums2[j] -> nums1[i++]
          else -> nums2[j++]
        }
      }
      return if ((nums1.size + nums2.size) % 2 == 0)
        (prev + curr) / 2.0
       else
        curr.toDouble()
    }