Problem:
Given an array of integers. How do we pick two numbers such that their sum is closest to zero.
Solution: 

• Sort the array by comparing absolute value.
• traverse the array once to find the two consecutive numbers with minimum sum.

Complexity: O(n log n)
Code:

a1a2a3....anb1b2b3....bn to a1b1a2b2a3b3....anbn

Problem:
Convert a1a2a3....anb1b2b3.....bn to
a1b1a2b2a3b3.....anbn
in O(n) time and O(1) space
Solution:

[b]       a b c d e 1 2 3 4 5      [2<=5, index=2*2-1=3]

[c]       a b b d e 1 2 3 4 5      [3<=5, index=3*2-1=5]

[e]       a b b d c 1 2 3 4 5      [5<=5, index=5*2-1=9]

[4]       a b b d c 1 2 3 e 5      [9>5, index=(9-5)*2=8]

[3]       a b b d c 1 2 4 e 5      [8>5, index=(8-5)*2=6]

[1]       a b b d c 3 2 4 e 5      [6>5, index=(6-5)*2=2]

[b]       a 1 b d c 3 2 4 e 5      [startindex=index=2]

[d]       a 1 b d c 3 2 4 e 5      [4<=5,index=4*2-1=7]

[2]       a 1 b d c 3 d 4 e 5      [7>5,index=(7-5)*2=4]

[d]       a 1 b 2 c 3 d 4 e 5      [startindex=index=4]

Complexity: O(n) time O(1) space
Code:

|a-b| + |b-c| + |c-a|

Problem:

Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum 

where a E A , bEB , cEC

. Here the answer is a = 15, b = 13, and c = 14

Solution:
Let,
min_dif=INT_MAX
1.Sort the N arrays A,B,C.....
2.Find the minimum and maximum of A[0],B[0],C[0].....
3.Take the difference between MAX-MIN values.
5.If the difference is less than min_dif then update min_dif and save all n values.
6.Now increment the index of the array which contains minimum element.
7.repeat these steps till end of array is reached for atleast one array.

Complexity: O(total no of elements)
Code: