Arrays

Write a program to find the greatest and smallest element in an array.

 public class Main
 {
     public static int greatest(int arr[]){
         int n= arr.length;
         int maxNumber= Integer.MIN_VALUE;
         for(int i=0; i<n;i++){
             if(arr[i]>maxNumber){
                 maxNumber=arr[i];
             }
         }
         return maxNumber;
     }
     public static int smallest(int arr[]){
         int n= arr.length;
         int minNumber= Integer.MAX_VALUE;
         for(int i=0; i<n;i++){
             if(arr[i]<minNumber){
                 minNumber= arr[i];
             }
         }
         return minNumber;
         }
     public static void main(String[] args) {
         int arr[]={5,3,7,9,1};
         System.out.println(greatest(arr));//9
         System.out.println(smallest(arr));//1
     }
 }

Write a program to reverse an array.

 public class Main
 {   
     public static void revereArray(int arr[]){
         int n= arr.length;
         int start=0;
         int end= arr.length-1;
         while(start<end){
             int temp =arr[start];
             arr[start]= arr[end];
             arr[end]=temp;
             start++;
             end--;
         }
     }
     public static void print(int arr[]){
         int n= arr.length;
         for(int i=0; i<n;i++){
             System.out.print(arr[i]+" ");
         }
         System.out.println();
     }
     public static void main(String[] args) {
         int arr[]={3,4,6,2,7,2};
         revereArray(arr);
         print(arr);
     }
 }

Write a program to form unique pair of element from an array

 public class Test {
   public static void pairFormation(int arr[]) {
     int n = arr.length;
     for (int i = 0; i < n; i++) {
       for (int j = i + 1; j < n; j++) {
         System.out.print("(" + arr[i] + "," + arr[j] + ")");
       }
       System.out.println();
     }
   }
   public static void main(String[] args) {
     int arr[] = { 1, 2, 3, 4, 5 };
     pairFormation(arr);
   }
 }

Write a program to print all subarrays from the given array.

 public class Test {
   public static void printSubarray(int arr[]) {
     int n = arr.length;
     for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
         for (int k = i; k <= j; k++) {
           System.out.print(arr[k] + " ");
         }
         System.out.println();
       }
     }
   }
   public static void main(String[] args) {
     int arr[] = { 1, 2, 3, 4, 5, 6 };
     printSubarray(arr);
   }
 }

Write a program to find the maximum subarray sum using prefix Sum method.

 public class Test {
   public static int subarraySum(int arr[]) {
     int n = arr.length;
     int curSum=0;
     int maxSum=Integer.MIN_VALUE;
     int prefixSum[] = new int[n];
     prefixSum[0] = arr[0];
     for (int i = 1; i < n; i++) {
       prefixSum[i] = prefixSum[i - 1] + arr[i];
     }
     for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
         curSum = (i == 0) ? prefixSum[j] : prefixSum[j] - prefixSum[i - 1];
         if (curSum > maxSum) {
           maxSum = curSum;
         }
       }
     }
     return maxSum;
   }
   public static void main(String[] args) {
     int arr[] = { 1, -2, 6, -1, 3 };
     System.out.print(subarraySum(arr)); 
   }
 }

Write a program to find maximum subarray sum using Kadane's algorithm

 public class Test {
   public static int subarraySum(int arr[]) {
     int n = arr.length;
     int curSum = 0;
     int maxSum = Integer.MIN_VALUE;
     for (int i = 0; i < n; i++) {
       curSum = curSum + arr[i];
       if (curSum < 0) {
         curSum = 0;
       }
       if (curSum > maxSum) {
         maxSum = curSum;
       }
     }
     return maxSum;
   }
   public static void main(String[] args) {
     int arr[] = { 1, -2, 6, -1, 3 };
     System.out.println(subarraySum(arr));
   }
 }

Trapping Rainwater

Statement:- Given a non-negative integer representing an elevation map where width of each bar is 1, compute how much water it can trap after raining.

height[h]={4,2,0,6,3,2,5}, Answer= 11

 public class Test {
   public static int trappedWater(int arr[]){
     int n= arr.length;
     int maximumLeftBoundary[]=new int[n];
     maximumLeftBoundary[0]=arr[0];
     for(int i=1; i<n;i++){
       maximumLeftBoundary[i]=Math.max(maximumLeftBoundary[i-1], arr[i]);
     }
     int maximumRightBoundary[]=new int[n];
     maximumRightBoundary[n - 1] = arr[n - 1];
     for (int i = n - 2; i >= 0; i--) {
       maximumRightBoundary[i] = Math.max(maximumRightBoundary[i + 1], arr[i]);
     }
     int trappedWater = 0;
     for (int i = 0; i < n; i++) {
       int waterLevel = Math.min(maximumLeftBoundary[i], maximumRightBoundary[i]);
       trappedWater += waterLevel - arr[i];
     }
     return trappedWater;
   }
   public static void main(String[] args) {
     int height[] = { 4, 2, 0, 6, 3, 2, 5 };
     System.out.print(trappedWater(height));
   }
 }

Buy and sell stocks

Statement:- You are given price where price[i] is price of given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stack and choosing different day in future to sell that stock. Return maximum profit you can achieve from this transaction. If you can not achieve return 0,

price[]={7,1,5,3,6,4}, Maximum profit:- 5

 public class Test {
   public static int maxProfit(int arr[]) {
     int n = arr.length;
     int maxProfit = 0;
     int buyPrice = Integer.MAX_VALUE;
     for (int i = 0; i < n; i++) {
       if (arr[i] > buyPrice) {
         int profit = arr[i] - buyPrice;
         maxProfit = Math.max(profit, maxProfit);
       } else {
         buyPrice = arr[i];
       }
     }
     return maxProfit;
   }
   public static void main(String[] args) {
     int price[] = { 7, 1, 5, 3, 6, 4 };
     System.out.print(maxProfit(price));
   }
 }

Write a program to find second smallest and greatest without sorting.

 import java.util.*;

 public class Main {
   public static int s_small(int arr[]){
     int n= arr.length;
     int small= Integer.MAX_VALUE;
     int s_small= Integer.MAX_VALUE;
     for(int i=0; i<n;i++){
       if(arr[i]<small){
         s_small=small;
         small=arr[i];
       }else if(arr[i]<s_small && arr[i]!=small){
         s_small=arr[i];
       }
     }
     return s_small;
   }
    public static int s_large(int arr[]){
    int n= arr.length;
    int large= Integer.MIN_VALUE;
    int s_large= Integer.MIN_VALUE;
    for(int i=0;i<n;i++){
      if(arr[i]>large){
        s_large=large;
        large= arr[i];
      }else if(arr[i]>s_large && arr[i]!=large){
        s_large= arr[i];
      }
    }
    return s_large;
  }
     public static void main(String[] args) {
       int arr1[]= {2,1,7,8,9,6,11};
       int arr2[]= {11,7,6,4,10,12};
       System.out.println(s_small(arr1));
       System.out.println(s_small(arr2));
       System.out.println(s_large(arr1));
       System.out.println(s_large(arr2));
   }
 }

Write a program to remove duplicate from sorted array.

import java.util.*;

public class Main {
    public static int remove(int arr[]){
      int i=0; 
      int n= arr.length;
      for(int j=1; j<n;j++){
        if(arr[i]!=arr[j]){
          i++;
          arr[i]=arr[j];
        }
      }
      return i+1;
    }
    public static void main(String[] args) {
      int arr[]={2,4,4,6,6,8};
      int k= remove(arr);
      for(int i=0; i<k;i++){
        System.out.print(arr[i]+" ");
      }
  }
}

Write a program to left rotate an array by one place.

import java.util.*;

public class Main {
  public static void rotateByOnePlace(int arr[]){
    int n=arr.length;
    int temp=arr[0];
    for(int i=0; i<n-1;i++){
      arr[i]=arr[i+1];
    }
    arr[n-1]=temp;
    for(int i=0; i<n;i++){
      System.out.print(arr[i]+" ");
    }
  }
    public static void main(String[] args) {
      int arr[]={1,2,3,4,5};//2 3 4 5 1
      rotateByOnePlace(arr);
  }
}

Write a program to right rotate an array by one place

import java.util.*;

public class Main {
  public static void rotateByOnePlace(int arr[]){
    int n=arr.length;
    int temp=arr[n-1];
    for(int i=n-1; i>0;i--){
      arr[i]=arr[i-1];
    }
    arr[0]=temp;
    for(int i=0; i<n;i++){
      System.out.print(arr[i]+" ");
    }
  }
    public static void main(String[] args) {
      int arr[]={1,2,3,4,5};//5 1 2 3 4
      rotateByOnePlace(arr);
  }
}

Write a program to left rotate an array by 'd' place.

import java.util.*;

public class Main {
  public static void reverse(int arr[], int start, int end){
    while(start<=end){
      int temp=arr[start];
      arr[start]= arr[end];
      arr[end]= temp;
      start++;
      end--;
    }
  }
  public static void rotateLeftBydPlace(int arr[],int d){
    int n= arr.length;
    reverse(arr,0, d-1);
    reverse(arr,d,n-1);
    reverse(arr,0,n-1);
    for(int i=0; i<n;i++){
      System.out.print(arr[i]+" ");
    }
  }
  public static void main(String[] args) {
      int arr[]={1,2,3,4,5};
      rotateLeftBydPlace(arr,2);//3 4 5 1 2
      System.out.println();
   }
}

Write a program to right rotate an array by 'd' place

import java.util.*;

public class Main {
  public static void reverse(int arr[], int start, int end){
    while(start<=end){
      int temp=arr[start];
      arr[start]= arr[end];
      arr[end]= temp;
      start++;
      end--;
    }
  }
  public static void rotateRightBydPlace(int arr[], int d){
    int n=arr.length;
    reverse(arr,0,n-d-1);
    reverse(arr,n-d,n-1);
    reverse(arr,0,n-1);
    for(int i=0; i<n;i++){
      System.out.print(arr[i]+" ");
    }
  }
  public static void main(String[] args) {
      int arr[]={1,2,3,4,5};
      rotateRightBydPlace(arr,2);//4 5 1 2 3

  }
}