Find nth minimum element in an array.

unsigned long partitionArray(int arr[], unsigned long left, unsigned long right)
{
unsigned long pivot = (rand() % (right - left + 1)) + left;
SWAP(arr[left], arr[pivot]);
unsigned long i = left + 1;
for(unsigned long j = left + 1; j <= right; ++j)
{
if(arr[j] < arr[left])
{
swap(arr[j], arr[i]);
++i;
}
}
swap(arr[i-1], arr[left]);
return i-1;
}

int RSelect(int arr[], int left, int right, int n)
{
if(left == right && left == n)
return arr[left];
int pivotIndex = partitionArray(arr, left ,right);
if(pivotIndex + 1 == n)
return arr[pivotIndex];
else if(pivotIndex + 1 > n)
return RSelect(arr, left, pivotIndex - 1, n);
else
return RSelect(arr, pivotIndex + 1, right, n);
}

Find second-largest number in the array in at most n+log2n−2 comparisons.

int* findMax(int *arr, int i, int j, int len)
{
if(i == j)
{
int* comp = new int[len];
comp[0] = 1;
comp[1] = arr[i];
return comp;
}
int *comp1 = findMax(arr, i, i+(j-i)/2, len);
int *comp2 = findMax(arr, 1+i+(j-i)/2, j, len);
if(comp1[1] > comp2[1])
{
int k = comp1[0] + 1;
comp1[0] = k;
comp1[k] = comp2[1];
delete [] comp2;
return comp1;
}
else
{
int k = comp2[0] + 1;
comp2[0] = k;
comp2[k] = comp1[1];
delete [] comp1;
return comp2;
}
}

int findSecondMax(int *arr, int len)
{
int *compared =  findMax(arr, 0, len-1, len);
int *max2Arr = findMax(compared, 2, compared[0], compared[0] + 1);
int max2 = max2Arr[1];
delete [] max2Arr;
return max2;
}

[Gfg] Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Example:

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions: (8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).

Input: arr[] = {1, 20, 6, 4, 5}
Output: 5
Explanation: Given array has five inversions: (20, 6), (20, 4), (20, 5), (6, 4), (6, 5). 

Approach: We can use brute force approach using two loops where we go to every index 'i' and count number of indices on its right (i +1... n) where arr[i] > arr[j] where j = i + 1 ... n. This approach will work but is time consuming (O(n^2)).

We can use merge sort here, basically we can take advantage of merge process. Whenever we see there is an element in the left subarray (left...mid) say leftArr[i] which is greater than element in right subarray (mid + 1...right) say rightArr[j] then we can easily say we will get mid - i + 1 inversions right?

This is because both the arrays are sorted and if there is an element at index i,  leftArr[i] is greater than rightArr[j] then it is obvious that all the elements in leftArr[i....mid] will be greater than rightArr[j].

That's all!

Implementation in C#:

    class Solution

    {

        //Complete this function

        //Function to count inversions in the array.

        public long inversionCount(long[] arr)

        {

            long length = arr?.Length ?? 0;

            if (length <= 1)

            {

                return 0;

            }

            return this.CountInversionCount(arr, 0, length - 1);

        }

        

        private long CountInversionCount(long[] arr, long left, long right)

        {

            if (left >= right)

            {

                return 0;

            }

            long mid = left + (right - left) / 2;

            long leftInvCount = this.CountInversionCount(arr, left, mid);

            long rightInvCount = this.CountInversionCount(arr, mid + 1, right);

            long mergeInvCount = this.Merge(arr, left, mid, right);

            return leftInvCount + rightInvCount + mergeInvCount;

        }

        

        private long Merge(long[] arr, long left, long mid, long right)

        {

            List<long> temp = new List<long>();

            long i = left, j = mid + 1;

            long invCount = 0;

            while (i <= mid && j <= right)

            {

                if (arr[i] > arr[j])

                {

                    invCount += (mid - i + 1);

                    temp.Add(arr[j++]);

                }

                else

                {

                    temp.Add(arr[i++]);

                }

            }

            while (i <= mid)

            {

                temp.Add(arr[i++]);

            }

            while (j <=  right)

            {

                temp.Add(arr[j++]);

            }

            i = left;

            for (j = 0; j < temp.Count; ++j)

            {

                arr[i++] = temp[(int)j];

            }

            return invCount;

        }

    }

Complexity: O(nlogn)