FastPrep
Problem · Dynamic Programming

Relative Sort (Google Singapore)

Learn this problem
● MediumGoogleINTERNOA
See Google hiring insights

Problem statement

Relative sorting is defined as sorting two arrays (both in strictly ascending order) such that the only operation allowed is swapping i'th element of one array with the i'th element of the other array. An array is said to be in strictly ascending order if i'th element of the array is smaller than (i+1)'th element of the array. You are given two arrays of size N. print the minimum number of swaps required to make both arrays relatively sorted.

Note:

  • If the arrays are already relatively sorted, then print '0'
  • If the arrays cannot be relatively sorted, then print '-1'.

    • Input Format:

    The input consist of 3 lines:

  • First line consist of the size of each array, i.e. N
  • The next two lines contain N elements each separated by a space

    • Output Format:

    The output will be an integer i.e., the minimum number of swaps required to make both arrays relatively sorted.

    Function

    minSwapsToMakeSequencesIncreasing(N: int, A: int[], B: int[]) → int

    Examples

    Example 1

    N = 4A = [1, 4, 4, 9]B = [2, 3, 5, 10]return = 1
    To make both arrays strictly increasing we can swap 4 and 3 or 4 and 5.

    Constraints

    0 < N < 11000
    0 < Elements in array <= 10^9

    More Google problems

    drafts saved locally
    public int minSwapsToMakeSequencesIncreasing(int N, int[] A, int[] B) {
    // write your code here
}
    N4
    A[1, 4, 4, 9]
    B[2, 3, 5, 10]
    expected1
    checking account