DEV Community: sachin26

Sorting Algorithms - #4 Quick Sort

sachin26 — Wed, 02 Feb 2022 09:41:37 +0000

hi👋Devs,

In the previous one we have learned about the Merge Sort algorithm and in this article, we will discuss the QuickSort algorithm, how its work, time & space complexities and pros & cons.

Quick Sort

Quick Sort algorithm is an in-place sorting algorithm means this algo doesn't require any extra space except temp variables, to perform sorting.
This algo is also based on the divide and conquer approach.

lets understand how quick sort work.

step-1 select a pivot element.
you can choose any element as a pivot from the array

first element
last element
any random element

lets say i choose the first element of the array as pivot

step-2 place the pivot element in its right position.
now in this step we have to place the pivot element to its right position but we have to rearrange the array in such a way that

put all smaller elements (which are less than pivot) before pivot element.
put all greater elements (which are greater than pivot) after the pivot element.

we also called this step as a partition logic.

step-3 divide the array into sub-array.
divide the array into the left sub-array and sub-right array based on the pivot point and apply the same approach for the sub-arrays until sub array size becomes 1

implementation

now understand how we can implement this algo pragmatically

Pseudocode for quickSort( arr, start, end)

1. find the pivot index pivotIndex by using partition logic.

pivotIndex = partition( arr, start, end)

2. divide the array into sub-arrays using pivotIndex.

quickSort(arr, start, point-1)
quickSort(arr, point+1, end)

3. repeat these steps until the sub-array size becomes 1.

Pseudocode for partition( arr, start, end)

step-1 make first element as pivot.

pivot = arr[first]

step-2 run a loop while start < end and then,

1. initialise i & j variables.
i = start
j = end

2. linearly increase the i while pivot > arr[i]

3. linearly decrease the j while pivot < arr[j]

4. swap ith element with jth element ,if i < j

step-3 swap pivot element with jth element.

step-4 return the right pivot index position j

Time & Space Complexity

in average case the time complexity will be nLogn.
this algo does not require any extra space so , the space complexity is O(1).

Pros & Cons

it does not require extra memory.
pretty fast & efficient in most cases.
the worst-case complexity is n^2.
use recursion.

Java Implementation

import java.util.Arrays;

class Main{
    public static void main(String[] args){
        int[] arr = new int[] {3,12,90,2,5,16,25,44,70,0};
        System.out.println("unsorted array: "+Arrays.toString(arr));
        qSort(arr,0,9);
        System.out.println("sorted array: "+Arrays.toString(arr));
    }

    private static void qSort(int[] arr,int start,int end){
        if(start < end){

        int p = partition(arr,start,end);
        qSort(arr,start,p-1);
        qSort(arr,p+1,end);
        }
    }

    private static int partition(int[] arr,int s,int e){
        int pivot = arr[s];
                int i = s;
        int j = e;
        while(i < j){

            while(arr[i]<=pivot && i<e) i++;
            while( arr[j]>pivot && j>s ) j--;

            if(i < j)
            swap(arr,i,j);
        }

        swap(arr,s,j);

        return j;

    }

    private static void swap(int[] arr,int i, int j){
        int t = arr[i];
         arr[i] = arr[j];
         arr[j] = t;
    }

}

Thank you for reading this article. save it and share it with your dev friends. if you find any errors let me know in the comment section.

Striver's SDE Sheet Journey - #19 Four sum

sachin26 — Sun, 30 Jan 2022 12:24:13 +0000

Problem Statement :-

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]]

such that,

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example

Input : nums = [1,0,-1,0,-2,2], target = 0

Result : [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Solution 1

fix three pointers and look for the last one

nums = [1,0,-1,0,-2,2] ,target=0

nums = [1,0,-1,0,-2,2]
        | |  | < look for the last one >
        i j  k

step-1 sort the array nums and initialise an variable ans.

step-2 run three loops linearly for i, j, k pointers

1. find the last element, using binary search.
2. if the last element found then add the quadruplet to ans

Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        Set<List<Integer>> ans = new HashSet<List<Integer>>();
        int n = nums.length;

        Arrays.sort(nums);

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

            for(int j=i+1; j<n; j++){

                for(int k=j+1; k<n; k++){

                    int x = target - (nums[i] + nums[j] + nums[k]);

                    if(Arrays.binarySearch(Arrays.copyOfRange(nums,k+1,n),x) >= 0){
                        List<Integer> r = new ArrayList<Integer>();
                        r.add(nums[i]);
                        r.add(nums[j]);
                        r.add(nums[k]);
                        r.add(x);

                        ans.add(r);
                    }
                }
            }
        }

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        for(List<Integer> list : ans){
            result.add(list);
        }

        return result;
    }
}

Striver's SDE Sheet Journey - #19 Two sum

sachin26 — Thu, 27 Jan 2022 12:31:15 +0000

Problem Statement :-

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example

Input : nums = [2,7,11,15], target = 9

Result : [0,1]

Explanation : Because nums[0] + nums[1] == 9, we return [0, 1].

Solution 1

we can solve this problem by using two pointer approach
lets discuss this solution step by step.

step-1 make a copy sortArr array from the nums array.

step-2 sort the copy sortArr array.

step-3 initialise two pointers start=0, end=n.

step-4 run a loop from start to end and then,

1. calculate the sum from start & end indices of array.

2. break the loop if sum == target

3. increase the start by 1 if sum < target

4. decrease the end by 1 if sum > target

step-5 find the original indices from nums array & return it.

Dry Run
nums = [1,3,5,2,7] , target = 4

1. copy the array.
copyArr = [1,3,5,2,7]

2. sort the copied array.
copyArr = [1,2,3,5,7]

3. run two pointers on sorted array

copyArr = [1,2,3,5,7]
           |       |
        start      end

sum = start + end
sum = 1 + 7 => 8
8 > target = 4 ----> end--

copyArr = [1,2,3,5,7]
           |     |
        start    end

sum = start + end
sum = 1 + 5 => 6
6 > target = 4 ----> end--

copyArr = [1,2,3,5,7]
           |   |
        start  end

sum = start + end
sum = 1 + 3 => 4
4 == target = 4 --> stop the loop

return the original indices of values from the nums array.

           0 1 2 3 4
copyArr = [1,2,3,5,7]
           |   |
        start  end

        0 1 3 4 5
nums = [1,3,5,2,7]

ans = [0,1]

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {

        int[] sortArr = nums.clone();
        int[] ans = new int[2];

        Arrays.sort(sortArr);

        int start =0, end = nums.length-1;
        int n1 = 0,n2 = 0;

        while(start < end){

            int sum = sortArr[start] + sortArr[end];

            if(sum == target) {
                n1 = sortArr[start];
                n2 = sortArr[end];
                break;
            }else
             if(sum > target)
                  end--;
              else
                start++;
        }

        for(int i=0; i<nums.length; i++){

            if(n1 == nums[i]){
                ans[0] = i;
                n1 = -1;
            }
            else
            if(n2 == nums[i]){
                ans[1] = i;
                n2 = -1;
        }}


        return ans;



    }
}

Striver's SDE Sheet Journey - #18 Count Reverse Pairs

sachin26 — Tue, 25 Jan 2022 10:21:18 +0000

Problem Statement :-

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where :-

i < j
nums[i] > 2 * nums[j].

Example

Input : nums = [1,3,2,3,1]

Result : 2

Solution 1

this problem can be solved by Merge Sort algorithms.
in the Merge Sort, before merging two sorted sub-arrays we can linearly count the reverse pairs.

step-1 initialise two variables

i = left initial index of subArr1
k = mid + 1 intial index of subArr2

step-2 run a loop from i=0 to subArr1.length,

1. keep increasing k , while subArr1[i] > subArr2[k] * 2
2. if above condition not satisfy then add k to ans

example:- subArr1 = [5,7,8] subArr2 = [1,4,4]

ans = 0
subArr1 = [5,7,8]   subArr2 = [1,4,4]
           i                   k
5 > 1*2 --> increase k++ k = 1

ans = 0
subArr1 = [5,7,8]   subArr2 = [1,4,4]
           i                     k
5 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k

ans = 1
subArr1 = [5,7,8]   subArr2 = [1,4,4]
             i                   k
7 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k

ans = 2
subArr1 = [5,7,8]   subArr2 = [1,4,4]
               i                 k
8 > 4*2 --> it doesn't satisfy the condition then add k to ans
ans += k

we will stop,bcoz i goes out of boundary.

we found ans = 3 reverse pairs from sub arrays.

Java

class Solution {
    public int reversePairs(int[] nums) {


        int[] ans = new int[1];

        mergeSort(nums,0,nums.length-1,ans);

        return ans[0];
    }

    private static void mergeSort(int[] arr,int left,int right,int[] ans){


    if(left >= right) return;



    int mid = ( left + right ) / 2;


    mergeSort(arr,left,mid,ans);
    mergeSort(arr,mid+1,right,ans);

    merge(arr,left,mid,right,ans);

   }


      private static void merge(int[] arr,int left,int mid,int right,int[] ans){


    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;


    int[] leftArr = new int[leftArrSize];
    int[] rightArr = new int[rightArrSize];


       // count the reverse pairs   
       int k = mid + 1;

        for(int i = left;i<=mid;i++) {
            while(k<=right && arr[i] > (2 * (long) arr[k])) {
                k++;
            }
            ans[0] += (k - (mid+1));
        }


    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];


    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;


    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{

        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;


      }
    }



    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }


    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }
}

Striver's SDE Sheet Journey - #17 Grid Unique Paths

sachin26 — Mon, 24 Jan 2022 08:11:59 +0000

Problem Statement :-

Given a matrix m X n, count paths from left-top to the right bottom of a matrix with the constraints that from each cell you can either only move to the rightward direction or the downward direction.

Example

Input : m = 2, n= 2

Result : 2

Solution 1

by using recursive call for the downward and rightward direction. by doing that we can able to find out all the possible paths

step-1 in the 2D matrix, we first start at (0,0), and then we make two recursive calls in the direction of the bottom & right to reach the destination.

      (0,0)
     /     \
  (1,0)   (0,1)

step-2 when the recursive call goes out of the boundary of the matrix, we will simply return 0.

in the 2x2 matrix, path (2,0) is out of boundary.

      (0,0)
     /     \
  (1,0)   (0,1)
  /
(2,0) -> return 0

step-3 when the recursive call reaches the destination or end of the matrix, we will return 1.

          (0,0)
         /     \
      (1,0)   (0,1)
     /   \
 (2,0)   (1,1) -> return 1

step-4 we will sum the result from left & right recursive call and return the ans.

step-5 to avoid recomputing, we will use another matrix to store the result of the recursive call for future use.
whenever we found the same sub-problem, we simply return the result from the matrix instead of recomputing.

see the java implementation

Java

class Solution {
    public int uniquePaths(int m, int n) {

        int totalPaths = 0;
        int[][] dp = new int[m][n];

        for(int i=0; i<m; i++) Arrays.fill(dp[i],-1);

        totalPaths = findPaths(m,n,0,0,dp);

        return totalPaths;


    }

    private int findPaths(int m,int n,int i,int j,int[][] dp){

        if(i == m-1 && j == n-1) return 1;

        if(i >= m || j >= n) return 0;

        if(dp[i][j] != -1) return dp[i][j];

        return dp[i][j] = findPaths(m,n,i+1,j,dp) + findPaths(m,n,i,j+1,dp);

    }
}

Striver's SDE Sheet Journey - #16 Majority Element (>N/3 times)

sachin26 — Fri, 21 Jan 2022 09:01:26 +0000

Problem Statement :-

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example

Input : nums = [3,2,3]

Result : 3

Solution 1

in this solution, we just need to find the two most frequent elements in the array nums and count the frequency of the frequent elements if the count is greater than N/3 then return the elements.

let's discuss this approach step by step.

step-1 declare some variables.
firstMajNum = null
secondMajNum = null
firstMajCount = 0
secondMajCount = 0

firstMajNum & secondMajNum will store the currently most frequent elements.

_firstMajCount & secondMajCount will store the frequency of the current most frequent element._

step-2 run a loop from i=0 to n.

1. get the ith element from array nums.
element = nums[i]

2. increase the firstMajCount if element == firstMajNum

3. increase the secondMajCount if element == secondMajNum

4. declare firstMajCount & firstMajNum if firstMajCount == 0.

firstMajCount = 1
firstMajNum = element

5. declare secondMajCount & secondMajNum if secondMajCount == 0

secondMajCount = 1
secondMajNum = element

6. if all the above cases not satisfy, decrease the secondMajCount & secondMajCount by 1

step-3 count the frequency of the most frequent elements of the array & return those elements that are >N/3.

see the java implementation.

Java

class Solution {
    public List<Integer> majorityElement(int[] nums) {

        Integer firstMajNum = null;
        Integer secondMajNum = null;
        int firstMajCount = 0;
        int secondMajCount = 0;


        for(int i=0; i<nums.length; i++){

            int element = nums[i];

            if(firstMajNum != null && element == firstMajNum){       
                firstMajCount++;

            }else if (secondMajNum != null && element == secondMajNum){   
                secondMajCount++;

            }else if(firstMajCount == 0){
                firstMajNum = element;
                firstMajCount = 1;

            }else if(secondMajCount == 0){
                secondMajNum = element;
                secondMajCount = 1;
            }else{
                firstMajCount--;
                secondMajCount--;

                if(firstMajCount == 0) firstMajNum = null;
                if(secondMajCount == 0) secondMajNum = null;
            }
        }

         firstMajCount = 0;
         secondMajCount = 0;

        for(int e : nums){
           if(firstMajNum != null && firstMajNum == e) firstMajCount++;

            if(secondMajNum != null && secondMajNum == e) secondMajCount++;
        }

        List<Integer> ans = new ArrayList<Integer>();

        if(firstMajCount > nums.length/3) ans.add(firstMajNum);
        if(secondMajCount > nums.length/3) ans.add(secondMajNum);


        return ans;

    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Thank you for reading this article i hope you like and plz share with your dev friends. if you find something wrong let me in the comment section.

Striver's SDE Sheet Journey - #15 Majority Element (>N/2 times)

sachin26 — Mon, 17 Jan 2022 09:34:46 +0000

Problem Statement :-
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example

Input : nums = [2,2,1,1,1,2,2]

Result : 2

Solution 1

using sorting,we can easily find the majority element in an array.
lets understand this approach step by step.

step-1 sort the array nums.

stpe-2 initialize three variables max = 0, count = 1, majEle = 0 .

step-3 run a loop from i=1 to n-1.

1. increase counting if the adjacent elements are the same..
if nums[i] == nums[i+1] then count++

2. if not nums[i] == nums[i+1], start recounting for new majority element.

3. if count > max then re-assign new max & majEle

Java

class Solution {
    public int majorityElement(int[] nums) {

        if(nums.length == 1) return nums[0];
        Arrays.sort(nums);

        int max =0;
        int majEle = 0;

        int count = 1;

        for(int i=0; i< nums.length-1; i++){
            if(nums[i] == nums[i+1]){
                count++;

            }else{
                count = 1;
            }

             if(count > max) {
                    max = count ;
                    majEle = nums[i];
                }
        }

        return majEle;

    }
}

Time Complexity : O(nlogn) + O(n)
Space Complexity : O(1)

Solution 2

by using Boyer–Moore majority vote algorithm, we can solve this problem in O(n) time complexity

in this algorithm, we increase or decrease the count of the majority element, in the last, we will get our majority element.

step-1 initialise two variables majEle = nums[0], count = 1

step-2 run a loop from i=1 to n, then

1. if we found the majEle, increase the count by 1
2. if not majEle, decrease the count by 1
3. if count become 0 then, re-initialse majEle & count

Java

class Solution {
    public int majorityElement(int[] nums) {

        int majEle = nums[0];
        int count = 1;

        for(int i=1; i<nums.length; i++){

            if(count == 0){
                majEle = nums[i];
                count++;

            }else if(nums[i] == majEle){
                count++;
            }else{
                count--;
            }
        }

        return majEle;

    }
}

Thank you for reading this article. save it for future use.
if you found something, let me in the comment section.

Striver's SDE Sheet Journey - #14 Pow(x,n)

sachin26 — Sat, 15 Jan 2022 12:15:56 +0000

Problem Statement :-

Given a double x and integer n, calculate x raised to power n. Basically Implement pow(x, n).

Example

Input : x = 2.00000, n = 10

Result : 1024.00000

Solution 1

The simple approach to find pow(x,n) is to initialize a variable ans and run a loop from 1 to n, keep multiplying x with ans.

step-1 Initialise a variable ans = 1.0.

step-2 run a loop from 1 to n.

1. ans = ans * x

step-3 if exponent n < 0 then return 1 / ans.

step-4 return ans.

Java

class Solution {
    public double myPow(double x, int n) {
        double ans = 1.0;

         for(int i=0; i<Math.abs(n); i++){
               ans = ans * x;
            }
        if(n < 0){
           ans = 1 / ans; 
        }

        return ans;
    }
}

Time Complexity : O(n)
Space Complexity : O(1)

Solution 2

this problem can be solved by the Divide & Conquer technique.
so what we are going to do in this approach, we recursively reduce the exponent N by half and compute them individually.

let's understand this approach with an example.

x = 2, n = 12

in this example, we need to find 2^12

reduce exponent N by half.

1. 2^12 ----> 2^6 * 2^6

2. 2^6 -----> 2^3 * 2^3

3. 2^3 -----> 2 * 2^1 * 2^1

4. 2^1 -----> 2 * 2^0 * 2^0

5. 2^0 -----> 1

now, we know that 2^0 is 1 then,

4. 2^1 -----> 2 * 2^0 * 2^0
2^1 -----> 2 * 1 * 1

3. 2^3 -----> 2 * 2^1 * 2^1
2^3 -----> 2 * 2 * 2
2^3 -----> 8

2. 2^6 -----> 2^3 * 2^3
2^6 -----> 8 * 8
2^6 -----> 64

1. 2^12 ----> 2^6 * 2^6
2^12 ----> 64 * 64
2^12 ----> 4096

see the java implementation.

Java

class Solution {
    public double myPow(double x, int n) {
        double ans = pow(x,n);

        if(n < 0) ans = 1.0 / ans;

        return ans;
    }

    private double pow(double x,int n){

       if (n==0)  return 1;

        double ans = pow(x,n/2);

        if((n&1) == 1){

            return x * ans * ans;

        }else{

            return ans*ans;
        } 
    }
}

Time Complexity : O(logn)
Space Complexity : O(logn) for recursion stack

Thank you for reading this article. save it for future use.

Striver's SDE Sheet Journey - #13 Search in a 2d Matrix

sachin26 — Thu, 13 Jan 2022 12:33:02 +0000

Problem Statement :-

Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Input : matrix = [[1,3,5,7],[10,11,16,20], target = 3,[23,30,34,60]]

Result : true

Solution 1

this solution is pretty simple,we just traverse the matrix and linearly check the target element, but it will cost n^2 complexity in the worst case.

step-1 run two nested loops from i,j=0 to n,m.

step-2 check the target element,
if matrix[i][j] == target , then return true

step-3 if target element not found,return false.

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        for(int i=0; i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j] == target) return true;
            }
        }

        return false;
    }
}

Solution 2

we know that the given matrix is sorted by column-wise & row-wise.so we can solve this problem by applying a binary search algorithm on row-wise and the Time Complexity of this solution will be O(n) + O(logn)

step-1 run a loop from i=0 to n.

1. get the ith row from the matrix.
row = matrix[i]

2. apply binary search algorithm on row,if target element found then return true

step-2 end loop and return false.

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        for(int i=0;i<matrix.length;i++){
            int[] row = matrix[i];

            int r = Arrays.binarySearch(row,target);

            if(r >= 0) return true;
        }

        return false;

    }
}

Solution 3

treat matrix as a 1D sorted array and apply binary search.

step-1 calculate the total elements n of matrix.

step-2 initialise low=0 & high=n-1

step-3 run a loop if low <= high

1. find the mid. mid = low + high
2. convert 1D array mid index to 2D metrix index.
row = mid/colSize
col = mid%colSize

3. if matrix[row][col] == target then return true.

4 if target < matrix[row][col] then high = mid-1

5. if target > matrix[row][col] then low = mid+1

step-4 end loop & return false.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
       int n = matrix.length;
       int m = matrix[0].length;

        int low = 0;
        int high = ( n*m )- 1;

        while(low <= high){
            int mid = (low + high) / 2;
            int value = matrix[mid/m][mid%m];

            if(value == target) return true;

            if(value > target)
                high = mid-1;
            else
                low = mid+1;
        }

        return false;
    }
}

Striver's SDE Sheet Journey - #12 Count inversions in an array

sachin26 — Tue, 11 Jan 2022 07:17:33 +0000

Problem Statement :-

Given an array of N integers, count the inversion of the array.
An inversion is defined for a pair of integers in the array when the following two conditions are met.

ARR[i] > ARR[j]
i < j

Input : array = [2, 5, 1, 3, 4]

Result : 4

Explanation: We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4).

Solution 1

we can solve this problem by using two nested loop,but it will cost n^2 time complexity.

step-1 initialise a variable pairs=0 .
step-2 run a loop from i=0 to n.

1. run another loop from j=i+1 to n.

check, if arr[i] > arr[j] is true, then increase the inversion count.

step-3 end.

Java

public class Solution {
    public static long getInversions(long arr[], int n) {
        long pairs =0;

     for(int i=0; i<arr.length;i++){

          for(int j=i+1; j<arr.length;j++){

              if(arr[i] > arr[j]) pairs++;
          }
      }
      return pairs;
    }
}

Solution 2

we can also solve this problem by using the Merge Sort algorithm. if you know, how we merge two sorted subarrays in the merge sort algorithm then you can easily understand this solution.

while merging the subarrays, count inversion pairs,
if an element of the left subarray is greater than an element of the right subarray.

let's visually understand how we solve this problem while merging two subarrays.

Array = [5,3,2,1,4]

as you can see 5 is greater than 3 which means it satisfies the first condition of inversion pairs and it also satisfies the second one,i<j.
we have found the first inversion pair while merging two subarrays.
pairs - (5,3)

3 > 2 &5 > 2 this pairs also satisfy the both conditions then we will count them as inversion pairs.
pairs - (3,2) (5,2)

now this time, the left subarray element 1 is not greater than the right subarray element 4, which does not satisfy the first condition of the inversion pairs.

2 > 1 then we can makes - (2,1) (3,1) (5,1) pairs.
2 < 4 doesn't satisfy the conditions.
3 < 4 doesn't satisfy the conditions.
5 > 4 then - (5,4)

Java

public class Solution {
    public static long getInversions(long arr[], int n) {
        // Write your code here.
        long[] ans = new long[1];
        mergeSort(arr,0,arr.length-1,ans);

      return ans[0];
    }

    private static void mergeSort(long[] arr,int left,int right,long[] ans){

    // return if arr size becomes 1
    if(left >= right) return;


    // calculate the mid
    int mid = ( left + right ) / 2;


    mergeSort(arr,left,mid,ans);
    mergeSort(arr,mid+1,right,ans);

    merge(arr,left,mid,right,ans);

   }

     private static void merge(long[] arr,int left,int mid,int right,long[] ans){

    // calculate the size of left & right subarrays
    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;

    // initialise temp subarrays
    long[] leftArr = new long[leftArrSize];
    long[] rightArr = new long[rightArrSize];

    // copy left & right array into temp arrays
    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];

    // set initial indexes of subarrays
    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;

    // copy temp subarrays, in ascending order
    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{
        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;
         ans[0] += leftArrSize - leftPointer; 
      }
    }


    // copy the remaining elements of left subarray into a marge array
    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }

    // copy the remaining elements of right subarray into a merge array
    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }

}

The Time & Space complexity will be the same as the Merge Sort algorithm, O(Nlogn), bcoz we add some lines of code for counting the inversion pairs.

thank you for reading this article, if you find any mistakes, let me know in the comment section and save it for future use.

Sorting Algorithms - #3 merge Sort

sachin26 — Sun, 09 Jan 2022 12:18:58 +0000

hi👋Devs,

I hope you getting some things from this Sorting Algorithms series.
in this article, we will discuss the very efficient and fast algorithm, Merge Sort algorithms.

Merge Sort

Merge Sort algorithm is based on the divide & conquer principle which states that repeatedly breaks down the problem into sub-problem, solves each sub-problem individually, and combines the sub-problem solutions into a final solution.

Let's understand this algorithm in a much better way with an example.

step-1 find the mid point and recursively divide the array into two subarrays until the array size becomes 1.

step-2 merge the two subarrays into an array till the final array is merged, in ascending order.

Pseudocode for recursively divide the array into two sub-arrays.

step-1 initialise left & right index of an array.

step-2 return if array size is 1.
if left >= right return.

step-3 find the mid of the array.
mid = (left + right) / 2

step-4 divide the array into two sub-array.
divide( array, left, mid)
divide( array, mid+1, right)

step-5 merge the two sub-array into a array.
marge( array, left, mid, right)

Pseudocode for merge the two sub-arrays.

step-1 calculate the size of left & right sub-arrays.
leftArrSize = mid - left+1
rightArrSize = right - mid

step-2 initialise the temps arrays for left & right sub-arrays
leftArr[]
rightArr[]

step-3 copy sub-arrays into the temp arrays.

leftArr[] = array[left....mid]
rightArr[] = array[mid+1...right]

step-4 set initial indexes of subarrays & array.
leftPointer = 0
rightPointer = 0
arrPointer = left

step-5 copy the temp sub-arrays into an array, in ascending or descending order, till the end of any temp sub-arrays.

step-6 copy the remaining elements of temp sub-arrays.

see the java implementation

Java

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {

      int[] arr = new int[]{5,9,2,7,1,10,4,1,50};

      System.out.println("unsorted Array : "+Arrays.toString(arr));

      mergeSort(arr,0,arr.length-1); 

      System.out.println("sorted Array in ascending order : "+Arrays.toString(arr));
    }

   private static void mergeSort(int[] arr,int left,int right){

    // return if arr size becomes 1
    if(left >= right) return;


    // calculate the mid
    int mid = ( left + right ) / 2;

    // divide the array into two subarrays
    mergeSort(arr,left,mid);
    mergeSort(arr,mid+1,right);

    // merge subarrays
    merge(arr,left,mid,right);

   }

   private static void merge(int[] arr,int left,int mid,int right){

    // calculate the size of left & right subarrays
    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;

    // initialise temp subarrays
    int[] leftArr = new int[leftArrSize];
    int[] rightArr = new int[rightArrSize];

    // copy left & right array into temp arrays
    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];

    // set initial indexes of subarrays
    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;

    // copy temp subarrays, in ascending order
    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{
        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;
      }
    }


    // copy the remaining elements of left subarray into a marge array
    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }

    // copy the remaining elements of right subarray into a merge array
    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }
}

Thank you for reading this article. share this article with your dev friends and save it for the future.

Sorting Algorithms - #2 Bubble Sort

sachin26 — Fri, 07 Jan 2022 11:22:01 +0000

Hi Devs,

In the previous article we have discussed the Selection Sort algorithm and in this one, we will learn & understand the Bubble Sort algorithm.

Bubble Sort

Bubble Sort is the simplest sorting algorithm from the others because its working procedure is very easy to understand.
In this algorithm, we do two things.

compare two adjacent elements.
Arr[i] > Arr[i+1] for ascending order
Arr[i] < Arr[i+1] for descending order
and swap them if they are incorrect order (ascending or descending).

in each iteration, each element of the array moves to the end of the array.

let's visually understand this algorithm.

now, we are going to sort this array in ascending order using the above two steps or bubble sort algorithms.

compare two adjacent elements. and swap them if Arr[i] > Arr[i+1]

5 is less than 9, it does not satisfy the swapping condition just move forward.

9 is greater than 2,it satisfy the swapping condition then swap them.

9 is greater than 7,it satisfy the swapping condition then swap them.

9 is greater than 1,it satisfy the swapping condition then swap them.

In the first iteration, we placed one element of the array in its correct position.
The same process will be follow until the last iteration.

after the last iteration,Array looks like this.

See the java Solution.

Java

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {

      int[] arr = new int[]{5,9,2,7,1};

      System.out.println("unsorted Array : "+Arrays.toString(arr));

      bubbleSort(arr); 

      System.out.println("sorted Array in ascending order : "+Arrays.toString(arr));
    }

   private static void bubbleSort(int[] arr){

     for(int i=0; i<arr.length;i++){

       for(int j =0;j<arr.length-i-1;j++){

        if(arr[j] > arr[j+1]){
          swap(arr,j,j+1);
        }
       }

     }
   }

   private static void swap(int[] arr,int i,int j){
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
   }
}

Pros & Cons

good for the smallest data sets.
its easy to implement.
it will take more than n swaps.
not require any extra memory.
required more time to sort.

Time Complexity

In the worst case, the Time complexity of this algorithm
will be O(n^2).
bcoz it required two nested loops for comparing & swapping the two
adjacent elements.

Space Complexity

Bubble sort does not require any extra memory for sorting.
then, Space Complexity will be O(1)

Thank you for reading this article. share this article with your dev friends and save it for the future.