FastPrepK-th Element of Two Sorted Arrays

K-th Element of Two Sorted Arrays

Flipkart logoFlipkart● HardFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Two integer arrays, first and second, are sorted in nondecreasing order. Return the k-th smallest value across both arrays, where k is one-based.

Your solution must run in O(log(min(first.length, second.length))) time and use O(1) auxiliary space.

Function

kthElement(first: int[], second: int[], k: int) → int

Examples

Example 1

first = [2,3,6,7,9]second = [1,4,8,10]k = 5return = 6

The merged order starts 1, 2, 3, 4, 6, so the fifth value is 6.

Example 2

first = []second = [-5,0,12]k = 2return = 0

When one array is empty, select directly from the other array.

Constraints

  • 0 <= first.length, second.length <= 100000
  • 1 <= first.length + second.length
  • -1000000000 <= first[i], second[i] <= 1000000000
  • Both arrays are sorted in nondecreasing order.
  • 1 <= k <= first.length + second.length

Source note: The source image is a source-neutral excerpt of the author-reported prompt.

More Flipkart problems

See Flipkart hiring insights
public int kthElement(int[] first, int[] second, int k) {
  // Write your code here.
}
first[2,3,6,7,9]
second[1,4,8,10]
k5
expected6
Checking account…