Find a Pair Whose Sum is Closest to Zero in Array

This problem is also called minimum absolute sum pair.

You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero.

importjava.util.Arrays;

/**

 * Class to find the pair whose sum closer to zero.

 * @authorrajesh.kumar

 */

public classSumClosestToZero {

     public static voidmain(String[] args) {

           int[] array = {10,12,14,16,-8,10,18,19,7,-6};

           getPairWithCloserToZeroSum(array);

     }

     /**

      * Method to print the pair.

      * @param array

      */

     private static voidgetPairWithCloserToZeroSum(int[] array) {

           Arrays.sort(array);

           int length = array.length;

          

           if(length==0 || length==1) {

                System.out.println("No pair exists !!");

           }

          

           int i = 0;

           int j = length -1;

           int minSum = array[i] + array[j];

           int minL = i; int minR= j;

           while (i  <  j) {

                int sum = array[i] + array[j] ;

                /* If sum of the elements at index i and j equals 0 */

                if (Math.abs(minSum)>Math.abs(sum)) {

                     minSum = sum;

                     minL = i;

                     minR = j;

                } else if(sum<0) {

                     i++;

                 } else {

                     j--;

                }

           }

           System.out.println("Pair is"

               +array[minL]+","+array[minR]+")");

     }

}

Find two elements in Array whose sum is Zero

SumZeroAmazon.com

import java.util.Arrays; /**  * Class to find the pair whose sum equal to zero.  * @author rajesh.kumar  */ public class SumZeroAmazon {      public static void main(String[] args) {            int[] array = {10,12,14,16,-8,10,18,19,6,-6};            getPairWithZeroSum(array);      }      /**       * Method to print the pair.       * @param array       */      private static void getPairWithZeroSum(int[] array) {            Arrays.sort(array);            int length = array.length;                       if(length==0 || length==1) {                 System.out.println("No pair exists !!");            }                       int i = 0;            int j = length -1;                       while (i  <  j) {                 /* If sum of the elements at index i and j equals 0 */                 if (array[i] + array[j] == 0) {                      System.out.println("Pair is ("+array[i]+","+array[j]+")");                      return;                 } else if(Math.abs(array[i]) > Math.abs(array[j])) {                      i++;                 } else {                      j--;                 }            }            System.out.println("No pair exists !!");      } }

Algorithm vs. Data structure

Algorithm: method for solving a problem.

Data structure: method to store information.

Algorithms + Data Structures = Programs.

Data structures such arrays, stacks, queues, trees and hash tables and their use cases. When to choose a linked list over an array? Should I go for a hash table or a balanced tree for my application? These are the kind of decisions you learn to take during the course.

Algorithms is typically more theoretical (lots of proofs!) and focuses on asymptotic time and space complexities of common algorithms. You also learn various approaches to tackle problems using strategies like Divide and Conquer, Greedy, Dynamic Programming, modelling your data as a graph and so on.

Heapsort implementation in Java

Heapsort is a comparison-based sorting algorithm. It can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n*logn) runtime.

Heapsort is an in-place algorithm, but it is not a stable sort.

public class HeapSort {

      /**

       * Heap sort logic.

       * @param array

       */

      private static void heapSort(int[] array) {

            int size = array.length;

           

            /** Heapify the complete array. */

            for (int i=size/2-1; i>=0; i--) {

                  heapify(array, i, size);

            }

            /**

             * 1. Swap the root element with last unsorted element.

             * 2. Heapify the array excluding the sorted sub-array.

             * 3. Repeat the step#1 and step#2.

             * */

            for (int i =size-1; i>=0; i--) {

                  int temp = array[0];

                  array[0] = array[i];

                  array[i] = temp;

                  heapify(array, 0, i);

            }

      }

      /**

       * To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap

       * @param array

       * @param i

       * @param n

       */

      private static void heapify(int[] array, int i, int n) {

            int left = 2*i+1;

            int right = 2*i+2;

            int largest = i;

            /** Choose biggest element between left and right child. */

            if(left<n && array[largest]<array[left] ) {

                  largest = left;

            }

           

            if(right<n && array[largest]<array[right]) {

                  largest = right;

            }

            /**

             * 1. Swap the largest element to root.

             * 2. Heapify recursively.

             **/

            if (largest != i) {

                  swap(array,largest, i);

                  heapify(array, largest, n);

            }

      }

      public static void main(String args[]) {

           

            int[] array = {22, 19, 23, 15, 16, 17};

            heapSort(array);

           

            System.out.print("Sorted array is: ");

            printArray(array);

      }

      private static void printArray(int array[]) {

            int n = array.length;

            for (int i=0; i<n; i++) {

                  System.out.print(array[i]+" ");

            }

            System.out.println();

      }

     

      private static void swap(int[] array, int i, int j) {

            int temp = array[i];

            array[i] = array[j];

            array[j] = temp;

      }

}