FastPrep
Problem · Sliding Window

Fortune Telling 🍒

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

Given a collection of n cards. The i-th card (1 ≤ i ≤ n) has a number Ai on its front and a number Bi on its back. At the start, all the cards are facing upwards. He wants to minimize the range of numbers (i.e. the difference between the maximum and minimum values) on the face-up side. He is allowed to flip a maximum of m cards. Flipping a card will transition Bi to the face up side and Ai to the back. Help him find the minimum possible range after using at most m flips.

Input

The first line of the input consists of 2 integers n and m. The next line contains n integers, i-th of which denotes Ai. The next line contains n integers, i-th of which denotes Bi.

Output

Output a single integer, the minimum possible range.

Function

minimizeTheRange(n: int, m: int, A: int[], B: int[]) → int

Examples

Example 1

n = 5m = 2A = [1, 2, 17, 16, 9]B = [3, 4, 5, 6, 11]return = 8
By flipping card 3 and 4, we get the face up numbers {1, 2, 5, 6, 9}. This makes range=9-1=8.

Constraints

  • 1 <= m <= n
  • 1 <= Ai, Bi <= 107

    • More Amazon problems

    drafts saved locally
    public int minimizeTheRange(int n, int m, int[] A, int[] B) {
  // write your code here
}
    n5
    m2
    A[1, 2, 17, 16, 9]
    B[3, 4, 5, 6, 11]
    expected8
    checking account