Split an Array in two arrays such that absolute value of Max(A)-Min(B) is minimized and print the arrays

Problem Statement:Given an array of size n,split the array in two parts A & B (not necessarily equal,but both parts should have atleast one element) such that

| Max(A)-Min(B) | is minimized.Print the minimized value,and the two arrays after splitting it up.

Example:

input:N=4 

arr=[7,9,3,1]  

output:2 

A=[1],B=[3,9,7] 

Explanation:|Max(A)-Min(B|=|1-3|=2 

input:N=5 arr=[3,1,2,6,4] 

output:1 

A=[1,2,4],B=[3,6]

Approach: As given in the question the task is to split the array in two halves but not necessarily equal this means that if we can find two  adjacent elements in the array after sorting whose absolute difference is minimum and then put the max of those two elements in a single array and rest all other array elements in other array then we can find |Max(A)-Min(B)|,we have to also store the indices of the two adjacent elements where the absolute difference is minimum.

Example:In the above test case where N=5 and arr=[3,1,2,6,4],one such possible split is A=[1],B=[2,3,6,4]

Below is the Java implementation of the above approach

Code

import java.io.*;
import java.util.Arrays;

class Solution {
    public static void main(String[] args)
    {
        int n = 4;
        int[] a = { 7, 9, 3, 1 };
        // calling function
        findMinDifference(a, n);
    }
    public static void findMinDifference(int[] a, int n)
    {
        // sorting array in increasing order
          int indexOne=-1,indexTwo=-1;
        Arrays.sort(a);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            // if the difference of adjacent value is
            // less than previous difference
              //storing the abs min diff
              //indices
            if (a[i + 1] - a[i] < res) {
                // update difference
                res = a[i + 1] - a[i];
                  indexOne=i;
                  indexTwo=i+1;
            }
        }
        System.out.println("Minimized Value:"+res);
          System.out.print("A=");
          //printing first Array
          for(int i=0;i<=indexOne;i++)
        {
              System.out.print(a[i]+" ");
        }
          System.out.println();
          System.out.print("B=");
          //Printing second Array
          for(int i=indexTwo;i<n;i++)
        {
              System.out.print(a[i]+" ");
        }
          System.out.println();
    }
}

Output:

Minimized Value:2 A=1 B=3 7 9

Time Complexity:O(N*logN)

Auxiliary Space:O(1)

Feel free to comment if you have any doubt in comments section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here