Arrays

import java.util.*;
import java.io.*;

class GFG 
{ 
    static void printFreq(int arr[], int n)
    {
    	int freq = 1, i = 1;

    	while(i < n)
    	{
    		while(i < n && arr[i] == arr[i - 1])
    		{
    			freq++;
    			i++;
    		}

    		System.out.println(arr[i - 1] + " " + freq);

    		i++;
    		freq = 1;
    	}
    }

    public static void main(String args[]) 
    { 
       int arr[] = {10, 10, 20, 30, 30, 30}, n = 6;

       printFreq(arr, n);
    } 
}

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int start, int end)
    {
    	if(end <= start)
    		return 0;

    	int profit = 0;

    	for(int i = start; i < end; i++)
    	{
    		for(int j = i + 1; j <= end; j++)
    		{
    			if(price[j] > price[i])
    			{
    				int curr_profit = price[j] - price[i] 
    								  + maxProfit(price, start, i - 1)
    								  + maxProfit(price, j + 1, end);

    				profit = Math.max(profit, curr_profit);
    			}
    		}
    	}

    	return profit;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {1, 5, 3, 8, 12}, n = 5;

       System.out.println(maxProfit(arr, 0, n-1));
    } 
}

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int n)
    {
    	int profit = 0;

    	for(int i = 1; i < n; i++)
    	{
    		if(price[i] > price[i - 1])
    			profit += price[i] - price[i -1];
    	}
    
    	return profit;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {1, 5, 3, 8, 12}, n = 5;

       System.out.println(maxProfit(arr, n));
    } 
}

// Efficient Method : Time Complexity : O(n), Auxilliary Space : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	int lMax[] = new int[n];
    	int rMax[] = new int[n];

    	lMax[0] = arr[0];
    	for(int i = 1; i < n; i++)
    		lMax[i] = Math.max(arr[i], lMax[i - 1]);


    	rMax[n - 1] = arr[n - 1];
    	for(int i = n - 2; i >= 0; i--)
    		rMax[i] = Math.max(arr[i], rMax[i + 1]);

    	for(int i = 1; i < n - 1; i++)
    		res = res + (Math.min(lMax[i], rMax[i]) - arr[i]);
    	
    	return res;
    }


    public static void main(String args[]) 
    { 
       int arr[] = {5, 0, 6, 2, 3}, n = 5;

      System.out.println( getWater(arr, n)); // Output : 6
    } 
}


// Naive Method : Time Complexity : O(n^2)

    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	for(int i = 1; i < n - 1; i++)
    	{
    		int lMax = arr[i];

    		for(int j = 0; j < i; j++)
    			lMax = Math.max(lMax, arr[j]);

    		int rMax = arr[i];

    		for(int j = i + 1; j < n; j++)
    			rMax = Math.max(rMax, arr[j]);

    		res = res + (Math.min(lMax, rMax) - arr[i]);
    	}
    
    	return res; // Output : 6
    }

// Efficient Method : Time Complexity : O(n), Auxiliary space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxConsecutiveOnes(int arr[], int n)
    {
    	int res = 0, curr = 0;

    	for(int i = 0; i < n; i++)
    	{
    		if(arr[i] == 0)
    			curr = 0;
    		else
    		{
    			curr++;

    			res = Math.max(res, curr);
    		}
    	}
    	
    	return res;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {0, 1, 1, 0, 1, 1, 1}, n = 7;

       System.out.println(maxConsecutiveOnes(arr, n)); // Output : 3
    } 
}


// Naive Method : Time Complexity : O(n^2), Auxiliary space : O(1)

    static int maxConsecutiveOnes(int arr[], int n)
    {
    	int res = 0;

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

    		for(int j = i; j < n; j++)
    		{
    			if(arr[j] == 1) curr++;
    			else break;
    		}

    		res = Math.max(res, curr);
    	}
    	
    	return res;
    }

// Efficient Method (KADANE's ALGORITHM) : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxSum(int arr[], int n)
    {
    	int res = arr[0];

    	int maxEnding = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		maxEnding = Math.max(maxEnding + arr[i], arr[i]);

    		res = Math.max(maxEnding, res);
    	}
    	
    	return res;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {1, -2, 3, -1, 2}, n = 5;

       System.out.println(maxSum(arr, n));
    } 
}


// Naive : Time Complexity : O(n^2)

	static int maxSum(int arr[], int n)
    {
    	int res = arr[0];

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

    		for(int j = i; j < n; j++)
    		{
    			curr = curr + arr[j];

    			res = Math.max(res, curr);
    		}
    	}
    	
    	return res;
    }

// Efficient Method : Time Complexity : O(n)
// Based on KADANE's ALGORITHM

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxEvenOdd(int arr[], int n)
    {
    	int res = 1;
    	int curr = 1;

    	for(int i = 1; i < n; i++)
    	{
    			if((arr[i] % 2 == 0 && arr[i - 1] % 2 != 0)
    			   ||(arr[i] % 2 != 0 && arr[i - 1] % 2 == 0))
    				{
    					curr++;

    					res = Math.max(res, curr);
    				}
    				else
    					curr = 1;
    	}
    	
    	return res;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {5, 10, 20, 6, 3, 8}, n = 6;

       System.out.println(maxEvenOdd(arr, n));
    } 
}




// Naive : Time Complexity : O(n^2)

    static int maxEvenOdd(int arr[], int n)
    {
    	int res = 1;

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

    		for(int j = i + 1; j < n; j++)
    		{
    			if((arr[j] % 2 == 0 && arr[j - 1] % 2 != 0)
    			   ||(arr[j] % 2 != 0 && arr[j - 1] % 2 == 0))
    				curr++;
    			else
    				break;
    		}

    		res = Math.max(res, curr);
    	}
    	
    	return res;
    }

// Efficient Method (Based on KADANE's ALGORITHM) : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
  	// STANDARD KADANE's ALGORITHM
    static int normalMaxSum(int arr[], int n)
    {
    	int res = arr[0];

    	int maxEnding = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		maxEnding = Math.max(maxEnding + arr[i], arr[i]);

    		res = Math.max(maxEnding, res);
    	}
    	
    	return res;
    }

    static int overallMaxSum(int arr[], int n)
    {
      	// Normal Sum
    	int max_normal = normalMaxSum(arr, n);

    	if(max_normal < 0)
    		return max_normal;

    	int arr_sum = 0;
		// Circular Sum
    	for(int i = 0; i < n; i++)
    	{
    		arr_sum += arr[i];

    		arr[i] = -arr[i];
    	}

    	int max_circular = arr_sum + normalMaxSum(arr, n);

    	return Math.max(max_circular, max_normal);
    }

    public static void main(String args[]) 
    { 
       int arr[] = {8, -4, 3, -5, 4}, n = 5;

       System.out.println(overallMaxSum(arr, n));
    } 
}



// Naive Method : Time Complexity : O(n^2)

    static int maxCircularSum(int arr[], int n)
    {
    	int res = arr[0];

    	for(int i = 0; i < n; i++)
    	{
    		int curr_max = arr[i];
    		int curr_sum = arr[i];

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

    			curr_sum += arr[index];

    			curr_max = Math.max(curr_max, curr_sum);
    		}

    		res = Math.max(res, curr_max);
    	}
    	return res;
    }

// Efficient Solution : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int findMajority(int arr[], int n)
    {
    	int res = 0, count = 1;

    	for(int i = 1; i < n; i++)
    	{
    		if(arr[res] == arr[i])
    			count++;
    		else 
    			count --;

    		if(count == 0)
    		{
    			res = i; count = 1;
    		}
    	}

    	count = 0;

    	for(int i = 0; i < n; i++)
    		if(arr[res] == arr[i])
    			count++;

    	if(count <= n /2)
    		res = -1;

    	return res; 
    }


    public static void main(String args[]) 
    { 
       int arr[] = {8, 8, 6, 6, 6, 4, 6}, n = 7;

       System.out.println(findMajority(arr, n));  // Output : 3
    } 
}


// Naive Solution : Time Complexity : O(n^2)

    static int findMajority(int arr[], int n)
    {
    	for(int i = 0; i < n; i++)
    	{
    		int count = 1;

    		for(int j = i + 1; j < n; j++)
    		{
    			if(arr[i] == arr[j])
    				count++;
    		}

    		if(count > n / 2)
    			return i;
    	}

    	return -1;
    }

// Time Complexity : O(n), Auxiliary space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 

    static void printGroups(int arr[], int n)
    {
    	for(int i = 1; i < n; i++)
    	{
    		if(arr[i] != arr[i - 1])
    		{
    			if(arr[i] != arr[0])
                    System.out.print("From " + i + " to ");
    			else
                    System.out.println(i - 1);
    		}
    	}

    	if(arr[n - 1] != arr[0])
            System.out.println(n-1);
    }

    public static void main(String args[]) 
    { 
       int arr[] = {0, 0, 1, 1, 0, 0, 1, 1, 0}, n = 9;

       printGroups(arr, n);
    } 
}

import java.io.*;

class GFG {

	// Function to check if an array is
	// Sorted and rotated clockwise
	static boolean checkIfSortRotated(int arr[], int n)
	{
		// Initializing two variables x,y as zero.
		int x = 0, y = 0;

		// Traversing array 0 to last element.
		// n-1 is taken as we used i+1.
		for (int i = 0; i < n - 1; i++) {
			if (arr[i] < arr[i + 1])
				x++;
			else
				y++;
		}

		// If till now both x,y are greater
		// then 1 means array is not sorted.
		// If both any of x,y is zero means
		// array is not rotated.
		if (x == 1 || y == 1) {
			// Checking for last element with first.
			if (arr[n - 1] < arr[0])
				x++;
			else
				y++;

			// Checking for final result.
			if (x == 1 || y == 1)
				return true;
		}
		// If still not true then definitely false.
		return false;
	}

	// Driver code
	public static void main(String[] args)
	{
		int arr[] = { 5, 1, 2, 3, 4 };

		int n = arr.length;

		// Function Call
		boolean x = checkIfSortRotated(arr, n);
		if (x == true)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}

class Interval {
    int buy;
    int sell;
}

class Solution{
    //Function to find the days of buying and selling stock for max profit.
    ArrayList<ArrayList<Integer> > stockBuySell(int A[], int n) {
        
        ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
      //Prices must be given for at least two days else return the empty result.
        if(n==1){
            return result;
        }
        
        //Creating solution vector.
        ArrayList<Interval> sol = new ArrayList<Interval>();
        int i=0, cnt=0;
        //Traversing through given price array.
        while (i < n-1) {
            //Finding Local Minima. Note that the limit of loop is (n-2)
            //as we are comparing present element to the next element.
            while ((i < n-1) && (A[i+1] <= A[i])){
                i++;
            }
            //If we reach the end, we break loop as no further 
            //solution is possible.
            if (i == n-1){
                break;
            }
            Interval e = new Interval();
            //Storing the index of minima which gives the day of buying stock.
            e.buy = i++;
 
            //Finding Local Maxima. Note that the limit of loop is (n-1)
            //as we are comparing present element to previous element.
            while ((i < n) && (A[i] >= A[i-1]))
                i++;
 
            //Storing the index of maxima which gives the day of selling stock.
            e.sell = i-1;
            sol.add(e);
            //Incrementing count of buy/sell pairs.
            cnt++;
        }
        if(cnt==0){
            return result;
        } else {
            //Storing the buy/sell pairs in a list.
            for(int j=0; j<sol.size(); j++){
                result.add(new ArrayList<Integer>()); 
                result.get(j).add(0, sol.get(j).buy);
                result.get(j).add(1, sol.get(j).sell);
            }
        }
        //returning the result.
        return result;
    } 
    
}

class Solution{
    // Function to find the maximum index difference.
    static int maxIndexDiff(int arr[], int n) { 
        if(n==1){
            return 0;
        }
        int RMax[] = new int[n]; 
        int LMin[] = new int[n]; 
        
        //Constructing LMin[] such that LMin[i] stores the minimum value 
        //from (arr[0], arr[1], ... arr[i]).
        LMin[0] = arr[0];
        for (int i = 1; i < n; ++i) 
            LMin[i] = Integer.min(arr[i], LMin[i - 1]);
            
        //Constructing RMax[] such that RMax[j] stores the maximum value 
        //from (arr[j], arr[j+1], ..arr[n-1]). 
        RMax[n - 1] = arr[n - 1]; 
        for (int j = n - 2; j >= 0; --j)
            RMax[j] = Integer.max(arr[j], RMax[j + 1]); 
            
        int i = 0, j = 0, maxDiff = -1; 
        //Traversing both arrays from left to right to find optimum j-i.
        //This process is similar to merge() of MergeSort.
        while (j < n && i < n) { 
            if (LMin[i] <= RMax[j]) { 
                //Updating the maximum difference.
                maxDiff = Integer.max(maxDiff, j - i); 
                j++; 
            } else
                i++;
        }
        //returning the maximum difference.
        return maxDiff; 
    }
}

class Solution
{
    //Function to rearrange an array so that arr[i] becomes arr[arr[i]]
    //with O(1) extra space. 
    static void arrange(long arr[], int n)
    {
        int i = 0;
        
        //Increasing all values by (arr[arr[i]]%n)*n to store the new element.
        for(i = 0; i < n; i++)
         arr[(int)i]+=(arr[(int)arr[(int)i]]%n)*n;
        
        //Since we had multiplied each element with n.
        //We will divide by n too to get the new element at that 
        //position after rearranging.
        for(i = 0; i < n; i++)
            arr[(int)i] = arr[(int)i]/n;
    }
}

class Solution{

    //Function to rearrange  the array elements alternately.
    public static void rearrange(long arr[], int n)
    {
        //Initialising index of first minimum and first maximum element. 
    	int max_idx = n - 1, min_idx = 0; 
    
    	 //Storing maximum element of array.
    	long max_elem = arr[n - 1] + 1; 
    
    	for (int i = 0; i < n; i++) { 
    	    
    		//At even index, we have to put maximum elements in decreasing order. 
    		if (i % 2 == 0) { 
    			arr[i] += (arr[max_idx] % max_elem) * max_elem; 
    			//Updating maximum index.
    			max_idx--; 
    		} 
    
    		//At odd index, we have to put minimum elements in increasing order. 
    		else { 
    			arr[i] += (arr[min_idx] % max_elem) * max_elem; 
    			//Updating minimum index.
    			min_idx++; 
    		} 
    	} 
    
    	//Dividing array elements by maximum element to get the result. 
    	for (int i = 0; i < n; i++) 
    		arr[i] = arr[i] / max_elem;
        
    }
    
}

class Solution
{
    //Function that puts all non-positive (0 and negative) numbers on left 
    //side of arr[] and return count of such numbers.
    static int segregate (int arr[], int size)
    {
        int j = 0, i;
        for(i = 0; i < size; i++)
        {
           if (arr[i] <= 0)  
           {
               int temp;
               //changing the position of negative numbers and 0.
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               //incrementing count of non-positive integers.
               j++;  
           }
        } 
        return j;
    }
    
    //Finding the smallest positive missing number in an array 
    //that contains only positive integers.
    static int findMissingPositive(int arr[], int size)
    {
        int i;
        //marking arr[i] as visited by making arr[arr[i] - 1] negative. 
        //note that 1 is subtracted because indexing starts from 0 and 
        //positive numbers start from 1.
        for(i = 0; i < size; i++)
        {
            if(Math.abs(arr[i]) - 1 < size && arr[Math.abs(arr[i]) - 1] > 0)
            arr[Math.abs(arr[i]) - 1] = -arr[Math.abs(arr[i]) - 1];
        }
        
        for(i = 0; i < size; i++)
        {
            if (arr[i] > 0)
            {
                //returning the first index where value is positive.
                // 1 is added because indexing starts from 0.
                return i+1;
            }
        }
        return size+1;
    }
    
    //Function to find the smallest positive number missing from the array.
    static int missingNumber(int arr[], int size)
    {
        //first separating positive and negative numbers. 
        int shift = segregate (arr, size);
        
        int arr2[] = new int[size-shift];
        int j=0;
        //shifting the array to access only positive part.
        for(int i=shift;i<(size);i++)
        {
            arr2[j] = arr[i];
            j++;
        }
        
        //calling function to find result and returning it.
        return findMissingPositive(arr2, j);
    }
    
}

class Solution{
    //Function to find the leaders in the array.
    static ArrayList<Integer> leaders(int arr[], int n){
        
        int maxEle = arr[n-1];
        
        ArrayList<Integer> res = new ArrayList<>();
        
        //We start traversing the array from last element.
        for(int i=n-1; i>=0; i--) {
            
            //Comparing the current element with the maximum element stored. 
            //If current element is greater than max, we add the element.
		    if(arr[i] >= maxEle){
		        //Updating the maximum element.
		        maxEle = arr[i];
		        //Storing the current element in arraylist for leaders.
		        res.add(maxEle);
		    }
		}
		
		//Reversing the arraylist.
		Collections.reverse(res);
		//returning the arraylist.
        return res;
    }
    
}

class Solution {
    // Function to find equilibrium point in the array.
    public static int equilibriumPoint(long a[], int n) {

        //We store the sum of all array elements.
        long sum = 0;
        for (int i = 0; i < n; i++) 
           sum += a[i];

        //sum2 is used to store prefix sum.
        long sum2 = 0;
        int ans = -1;

        for (int i = 0; i < n; i++) {
            
            //Leaving out the value of current element from suffix sum.
            sum = sum - a[i];
            
            //Checking if suffix and prefix sums are same.
            if (sum2 == sum) {
                //returning the index or equilibrium point.
                return (i + 1);
            }
            
            //Adding the value of current element to prefix sum.
            sum2 = sum2 + a[i];
        }
        return -1;
    }
}

class Solution{
    //Function to count the frequency of all elements from 1 to N in the array.
    public static void frequencyCount(int arr[], int N, int P)
    {
        //Decreasing all elements by 1 so that the elements
        //become in range from 0 to n-1.
        int maxi = Math.max(P,N);
        int count[] = new int[maxi+1];
        Arrays.fill(count, 0);
        for(int i=0;i<N;i++){
            count[arr[i]]++; 
        }
        
        for(int i=0;i<N;i++){
            arr[i] = count[i+1];
        }
    }
}

class Solution{

    //Function to swap two elements in the array.    
    public static void swap(int arr[], int x, int y){
        //Use of a temporary variable to swap the elements.
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    //Function to sort the array into a wave-like array.
    public static void convertToWave(int arr[], int n){
        
        //Iterating over the array. 
        for(int i=0;i<n-1;i=i+2){
            //Swapping two neighbouring elements at a time.
		    swap(arr, i, i+1);
		}
        return;
    }
    
}

class Solution{
    
    //Function to find minimum adjacent difference in a circular array.
    // arr[]: input array
    // n: size of array
    public static int minAdjDiff(int arr[], int n) {
    
       int min=Math.abs(arr[0]-arr[n-1]),diff;
        for(int i=0;i<n-1;i++)
        {
            diff=Math.abs(arr[i]-arr[i+1]);
            if(diff<min)
            min=diff;
        }
        return min;
       
    }
}

class Solution{
    //Function to reverse any part of the array.
    void reverse(ArrayList<Integer> arr, int n,int left, int right)
    {
           //reversing the sub-array from left index to right index.
            while (left < right) { 
                //swapping values at index stored at left and right index.
                int temp = arr.get(left); 
                arr.set(left, arr.get(right)); 
                arr.set(right, temp);
                
                //updating values of left and right index.
                left+=1; 
                right-=1;  
            }
    }
    
    //Function to reverse every sub-array group of size k.
    void reverseInGroups(ArrayList<Integer> arr, int n, int k) {
        for (int i = 0; i < n; i += k) { 
            
            //If (ith index +k) is less than total number of elements it means
            //k elements exist from current index so we reverse k elements 
            //starting from current index.
            if(i+k < n){ 
                //reverse function called to reverse any part of the array.
                reverse(arr,n,i,i+k-1);
            }
            //Else k elements from current index doesn't exist. 
            //In that case we just reverse the remaining elements.
            else{
                //reverse function called to reverse any part of the array.
                reverse(arr,n,i,n-1);
            }
           
        }
    }
}

class StrongestNeighbour{
    
    // Function to find maximum for every adjacent pairs in the array.
    static void maximumAdjacent(int sizeOfArray, int arr[])
    {
        int sum=0;
        for(int i=0; i<sizeOfArray-1; i++)
        {
            sum = Math.max(arr[i], arr[i+1]);  
            System.out.print(sum+" ");
            
        }
    }
}

class Solution{
    
    // Function to find largest and second largest element in the array
    public static ArrayList<Integer> largestAndSecondLargest(int sizeOfArray, int arr[])
       {
           //code here.
           int largest=-1;
           int sec_largest=-1;
           for(int i=0;i<sizeOfArray;i++)
           {
               largest = Math.max(largest,arr[i]);
           }
           for(int i=0;i<sizeOfArray;i++)
           {
               if(arr[i]<largest)
               {
                   sec_largest= Math.max(sec_largest,arr[i]);
               }
           }
           ArrayList<Integer> al = new ArrayList<Integer>(2);
           al.add(largest);
           al.add(sec_largest);
           return al;
       }
    }
}

class Solution {
    // Function to find element with more appearances between two elements in an
    // array.
    public int majorityWins(int arr[], int n, int x, int y) 
    {
        int countX=0;
        int countY=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==x)
                countX++; 
             
             if(arr[i]==y)
                 countY++;
         }
         
        if(countX>countY)
            return x;
         
        else if(countX==countY && x<y)
            return x;
         
        else 
            return y;
    }
}

class Solution
{
  //Function to find median of the array elements.  
  public int median(int A[],int N)
    {
      
        Arrays.sort(A);
        int k=N/2;
        if(N%2!=0){
            return A[k];
        }
        else{
            return (A[k-1]+A[k])/2;
        }
    }
    //Function to find median of the array elements.
    public int mean(int A[],int N)
    {
        int sum=0;
        for(int i=0;i<N;i++)
        {
            sum=sum+A[i];
        }
        return sum/N;
    }

}