ARRAYREOR - Editorial

editorial
, ,
1

Problem Link - Array Reordering Practice Problem in Sorting

Problem Statement:

You are given two arrays A and B of size N. Given a function F such that F(i,j) = A_i + B_j. ​Reorder the arrays A and such that F(i,j)≥F(j,i), 1≤i≤N,1≤j≤N,i<j.

Approach:

To solve the problem, you need to reorder the two arrays A and B such that the condition F(i, j) >= F(j, i) is satisfied for all valid i and j, where:

  • F(i,j)=A[i]+B[j]
  • F(j,i)=A[j]+B[i]

Given the constraint F(i,j)≥F(j,i), this reduces to ensuring that:

A[i]+B[j]≥A[j]+B[i]

After simplifying the inequality:

A[i]−A[j]≥B[i]−B[j]

This suggests that the largest values in A should be paired with the smallest values in B (and vice versa) to maximize the sum of the elements, ensuring the condition holds.

  • Sort A in descending order and sort B in ascending order: By doing this, you ensure that the larger values in A are paired with the smaller values in B, which satisfies the given condition.

Complexity:

  • Time Complexity: O(N log N) for sorting the two arrays.
  • Space Complexity: O(1) No extra space is required.