Greedy.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------Greedy-----------------------------------------

1. Job sequencing Problem
//Function to find the maximum profit and the number of jobs done.
    //Greedy Approach
    public int[] JobScheduling(Job arr[], int n)
    {
       Arrays.sort(arr,(a,b)->(b.profit-a.profit));
       
       int max_deadline=0;
       for(int i=0;i<n;i++){
           if(arr[i].deadline>max_deadline){
               max_deadline=arr[i].deadline;
           }
       }
       int[] result=new int[max_deadline+1];
       for(int i=1;i<=max_deadline;i++){
           result[i]=-1;
       }
       int count_jobs=0,job_profit=0;
       //traverse through (i==job_id);
       for(int i=0;i<n;i++){
           for(int j=arr[i].deadline;j>0;j--){
               if(result[j]==-1){
                 result[j]=i;   
                 count_jobs++;
                 job_profit+=arr[i].profit;
                 break;
               }
           }
       }
       int[]res=new int[2];
       res[0]=count_jobs;
       res[1]=job_profit;
       return res;
    }
---------------------------------------------------------------------------------
2. Chocolate Distribution Problem, Minimum Cost of ropes , Rearrange characters in a string such that no two adjacent are same -> These 3 questions are already done in some previous section of problems.
---------------------------------------------------------------------------------
3. N meetings in one room ->Also known as Activity Selection Problem
Intuition-> the earlier the meeting will end the more we can organize. that's why in this question we sorted the array accoding to the end time.
static class meeting {
		int start;
		int end;
		int pos;

		meeting(int s, int e, int p) {
			this.start = s;
			this.end = e;
			this.pos = p;
		}
	}

	static class meetingComparator implements Comparator<meeting> {
		@Override
		public int compare(meeting o1, meeting o2) {
			if (o1.end < o2.end)
				return -1;
			else if (o1.end > o2.end)
				return 1;
			else if (o1.pos < o2.pos)
				return -1;
			return 1;
		}
	}

	public static int maxMeetings(int[] start, int[] end, int n) {
		ArrayList<meeting> meet = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			meet.add(new meeting(start[i], end[i], i + 1));
		}

		meetingComparator mc = new meetingComparator();
		Collections.sort(meet, mc);
		ArrayList<Integer> ans = new ArrayList<>();
		ans.add(meet.get(0).pos);
		int limit = meet.get(0).end;
		for (int i = 1; i < n; i++) {
			if (meet.get(i).start > limit) {
				limit = meet.get(i).end;
				ans.add(meet.get(i).pos);
			}
		}

		System.out.println(ans);
		return ans.size();
	}
---------------------------------------------------------------------------------
4. Minimum Platforms
Intuition> we sort both arrays and check whether there is platform needed for any arrival or departure train. because in our approach we just need the time of arrival (platform++) and time of departure(platform--) and we traverse through time.
DryRun the code to get better Understanding
 static int findPlatform(int arr[], int dep[], int n)
    { 
	//arrival->start time, departure-> end time
       Arrays.sort(arr);
       Arrays.sort(dep);
       
       int plat_needed=1,result=1;
       int i=1,j=0;  //second arrival train and first departure train
       
       while(i<n && j<n){

 //as if train hasn't departured yet then the new arrival train if comes earlier has to use new platform
           if(arr[i]<=dep[j]){
               plat_needed++;  
               i++;
           }else if(arr[i]>dep[j]){
               plat_needed--;
               j++;
           }
           
           if(plat_needed>result)
                result=plat_needed;
       }
        return result;       
    }
---------------------------------------------------------------------------------
5. Minimum Number of coins Needed to make a change
 public static int minCoins(int val){
        ArrayList<Integer>ans=new ArrayList<>();
        int[]den={1,2,5,10,20,50,100,500,1000}; //follows Greedy as sum upto i-1 is smaller than ith element
        int n=den.length;
        for(int i=n-1;i>=0;i--){
            while(val>=den[i]){
                val-=den[i];
                ans.add(den[i]);
            }
        }
        System.out.println(ans);
        return ans.size();
    }
---------------------------------------------------------------------------------
6. Fractional Knapsack
 class itemComparator implements Comparator<Item>{
        @Override
        public int compare(Item a,Item b){
        
        double r1=(double)a.value/(double)a.weight;
        double r2=(double)b.value/(double)b.weight;
        
        if(r1<r2)return 1;
        else if(r1>r2)return -1;
        return 0;
        }
    }
    
    double fractionalKnapsack(int W, Item arr[], int n) 
    {
       Arrays.sort(arr,new itemComparator());
       
       int curr_weight=0;
       double finalans=0.0;
       
       for(int i=0;i<arr.length;i++){
           if(curr_weight+arr[i].weight<=W){
               curr_weight+=arr[i].weight;
               finalans+=arr[i].value;
           }else{
               int remain=W-curr_weight;
               finalans+=(double)arr[i].value/(double)arr[i].weight * (double)remain;
               break;
           }
       }
       return finalans;
    }
---------------------------------------------------------------------------------
7. Maximum product subset of an array
 static int maxProductSubset(int a[], int n) {
        if (n == 1) {
            return a[0];
        }
 
        int max_neg = Integer.MIN_VALUE;
        int count_neg = 0, count_zero = 0;
        int prod = 1;
        for (int i = 0; i < n; i++) {
 
            if (a[i] == 0) {
                count_zero++;
                continue;
            }
 
            if (a[i] < 0) {
                count_neg++;
                max_neg = Math.max(max_neg, a[i]);
            }
 
            prod = prod * a[i];
        }
 
        if (count_zero == n) {
            return 0;
        }

        if (count_neg % 2 == 1) {
 
            // Exceptional case: There is only
            // negative and all other are zeros
            if (count_neg == 1
                    && count_zero > 0
                    && count_zero + count_neg == n) {
                return 0;
            }
 
            // Otherwise result is product of
            // all non-zeros divided by
            //negative number with
            // least absolute value.
            prod = prod / max_neg;
        }
 
        return prod;
    }

---------------------------------------------------------------------------------
8. Huffman Encoding
 static class Node{
        int freq;
        Node left, right;

        Node(int freq){
            this.freq = freq;
            this.left = this.right = null;
        }
    }


    static void preOrder(Node root, String code, ArrayList<String> list){
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            list.add(code);

        preOrder(root.left, code+"0", list);
        preOrder(root.right, code+"1", list);
    }

    static ArrayList<String> huffmanCodes(String S, int[] f, int N){
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.freq == o2.freq)
                    return 1;
                return Integer.compare(o1.freq, o2.freq);
            }
        });

        for(int i = 0;i < N;i++){
            pq.add(new Node(f[i]));
        }

        while (pq.size() != 1){
            Node first = pq.poll();
            Node second = pq.poll();

            Node newNode = new Node(first.freq + second.freq);

            newNode.left = first;
            newNode.right = second;

            pq.add(newNode);
        }

        ArrayList<String> list = new ArrayList<>();

        Node root = pq.peek();

        preOrder(root, "", list);

        return list;

    }
---------------------------------------------------------------------------------
9. Maximum Trains for which stoppage can be provided.
Logic-> Just like Activity Selection Problem.
Here, in this question we have been given train no. , arrival time, departure time, req platform no.
so we will make an array(Platform) of size (no of platforms) for each no. platform and put -1 in every index.
Make a class(say Trains) which contain arrival time, departure time and platform no. as data members. Now traverse through given 2d array and put all in ArrayList<Trains>Tlist and now sort according to its departure time. and then traverse this Tlist and check if for a given platform train can be stopped or not, if its first time that we have a train for a given platform then just put it in array (Platform) and after that the above condition. if possible then increment the MAXStopage++.
---------------------------------------------------------------------------------
10. Buy Maximum Stocks if i stocks can be bought on i-th day
 public static void MaxStocks(int[]price,int k){
        ArrayList<pair>list=new ArrayList<>();
        for(int i=0;i<price.length;i++){
            list.add(new pair(price[i],i+1));   //stock price ,day
        }
        
        Collections.sort(list);
        
        int stocks=0;
        for(int i=0;i<list.size();i++){
            stocks+=Math.min(list.get(i).second,k/list.get(i).first);
            k-=list.get(i).first*Math.min(list.get(i).second,k/list.get(i).first);
        }
        System.out.println(stocks);
    }
---------------------------------------------------------------------------------
11. Shop in Candy Store
static ArrayList<Integer> candyStore(int candies[],int n,int k){
      Arrays.sort(candies);
      int min=0;
      int c=0;
      int i=0;
      int j=n-1;
      while(i<=j){
           if(c>=n)
             break;
          min+=candies[i];
          c=c+k+1;     //added 1 for bought candy and k for free candy
          i++;
      }
      
      int max=0;
       c=0;
       i=n-1;
      while(i>=0){
           if(c>=n)
             break;
          max+=candies[i];
          c=c+k+1;
          i--;
      }
      
      ArrayList<Integer>list=new ArrayList<>();
      list.add(min);
      list.add(max);
     
     return list;
    }
---------------------------------------------------------------------------------
12. Minimum Cost to cut a board into squares/CHOCOLA - Chocolate (Spoj)
private static int Chocolate(int m, int n, ArrayList<Integer> x, ArrayList<Integer> y) {
		int cost = 0;
		int v_cut = 1;
		int h_cut = 1;
		int i = 0;
		int j = 0;
		Collections.sort(x, Collections.reverseOrder());
		Collections.sort(y, Collections.reverseOrder());
		// we are taking MaxPriceEdge first because initially we have less pieces so
		// increment in total cost will be less,
		// after cutting... the pieces will increase at that time we will be taking
		// MinPriceEdge ->Greedy
		while (i < m && j < n) {
			if (x.get(i) > y.get(j)) {
				cost += v_cut * x.get(i);
				i++;
				h_cut++;
			} else {
				cost += h_cut * y.get(j);
				j++;
				v_cut++;
			}
		}
		while (i <m) {
			cost += v_cut * x.get(i);
			i++;
		}
		while (j < n) {
			cost += h_cut * y.get(j);
			j++;
		}
		return cost;
	}
---------------------------------------------------------------------------------
13. Check if it is possible to survive on Island
->Sunday is holiday.
// function to find the minimum days
    static void survival(int S, int N, int M)
    {
 
        // If we can not buy at least a week
        // supply of food during the first
        // week OR We can not buy a day supply
        // of food on the first day then we
        // can't survive.
        if (((N * 6) < (M * 7) && S > 6) || M > N)
            System.out.println("No");
 
        else {
 
            // If we can survive then we can
            // buy ceil(A/N) times where A is
            // total units of food required.
            int days = (M * S) / N;
 
            if (((M * S) % N) != 0)
                days++;
 
            System.out.println("Yes " + days);
        }
    }
 
---------------------------------------------------------------------------------
14. Maximize sum after K negations  
 public static long maximizeSum(long arr[], int n, int k)
    {
       Arrays.sort(arr);
        for(int i=0;i<arr.length;i++){
            if(arr[i]<0 && k>0){
                arr[i]=-arr[i];
                k--;
            }
        }
        long min=Integer.MAX_VALUE;
        long sum=0;
        
        for(int i=0;i<n;i++){
            sum+=arr[i];
            min=Math.min(min,arr[i]);
        }
        if((k&1)==1)sum-=2*min;
        
       return sum;
    }
---------------------------------------------------------------------------------
15. Maximize sum(arr[i]*i) of an Array -> Very basic Question
int mod = (int)1e9+7;
int Maximize(int arr[], int n)
{
Arrays.sort(arr);

long sum = 0;
for (int i = 0; i < n; i++)
sum = (sum + (long)arr[i] * i) % mod;

return (int)sum;
}
---------------------------------------------------------------------------------
16. Maximum sum of absolute difference of any permutation
Logic-> we take an arraylist and story elements like smaller bigger alternatively to get max absolute diff.
static int MaxSumDifference(Integer []a, int n)
    {
        List<Integer> finalSequence = new ArrayList<Integer>();
    
        Arrays.sort(a);
     
        for (int i = 0; i < n / 2; ++i) {
            finalSequence.add(a[i]);
            finalSequence.add(a[n - i - 1]);
        }
        if (n % 2 != 0)
            finalSequence.add(a[n/2]);
        
        int MaximumSum = 0;
     
        for (int i = 0; i < n - 1; ++i) {
            MaximumSum = MaximumSum + Math.abs(finalSequence.get(i) - finalSequence.get(i + 1));
        }
     
        // absolute difference of last element
        // and 1st element
        MaximumSum = MaximumSum + Math.abs(finalSequence.get(n - 1) - finalSequence.get(0));
  
        return MaximumSum;
    }
---------------------------------------------------------------------------------
17. Maximize sum of consecutive differences in a circular array /Swap and Maximize
-> Just like above Question
 long maxSum(long arr[] ,int n)
    {
        Arrays.sort(arr);
        int i=0;
        int j=n-1;
        int count=0;
        long sum=0;
        
        while(i<j){
            sum+=Math.abs(arr[i]-arr[j]);
            if(count%2==0)
                i++;
            else
                j--;
            count++;    
        }
        sum+=Math.abs(arr[j]-arr[0]);
        return sum;
    }
---------------------------------------------------------------------------------
18. Minimum sum of absolute difference of pairs of two arrays
Logic-> sort both the given arrays and just do sum+=Math.abs(arr[i]-brr[i]);
---------------------------------------------------------------------------------
19. Smallest subset with sum greater than all other elements
In Greedy also we check that sum of elements upto ith element should be smaller than (i+1)th, here also we kinda checked it.
static int minElements(int arr[], int n)
    {
        int halfSum = 0;
        for (int i = 0; i < n; i++)
            halfSum = halfSum + arr[i];
        halfSum = halfSum / 2;
     
         Arrays.sort(arr);
         
        int res = 0, curr_sum = 0;
        for (int i = n-1; i >= 0; i--) {
            curr_sum += arr[i];
            res++;
     
            if (curr_sum > halfSum)        
                return res;
        }
        return res;
    }
---------------------------------------------------------------------------------
20. Smallest number (when sum of digits and no. of digits is given)
 static String smallestNumber(int sum, int dig){
        String str="";
        if(dig*9<sum){
            return "-1";
        }
        
        for(int i=1;i<=dig;i++){
            if(i==dig){
                str=sum+str;
                break;
            }
            
            if(sum>9){
                str="9"+str;
                sum-=9;
            }else{
                int temp=sum-1;
                str=temp+str;
                sum=1;
            }
        }
        return str;
    }
---------------------------------------------------------------------------------
21. Find maximum sum possible equal sum of three stacks
public static int maxSum(int stack1[], int stack2[],int stack3[], int n1, int n2, int n3)
    {
      int sum1 = 0, sum2 = 0, sum3 = 0;
      
      for (int i=0; i < n1; i++)
          sum1 += stack1[i];
      
      for (int i=0; i < n2; i++)
          sum2 += stack2[i];
      
      for (int i=0; i < n3; i++)
          sum3 += stack3[i];
      
      // As given in question, first element is top
      // of stack..
      int top1 =0, top2 = 0, top3 = 0;
      int ans = 0;
      while (true)
      {
          // If any stack is empty
          if (top1 == n1 || top2 == n2 || top3 == n3)
             return 0;
      
          if (sum1 == sum2 && sum2 == sum3)
             return sum1;
          
          if (sum1 >= sum2 && sum1 >= sum3)
             sum1 -= stack1[top1++];
          else if (sum2 >= sum1 && sum2 >= sum3)
             sum2 -= stack2[top2++];
          else if (sum3 >= sum2 && sum3 >= sum1)
             sum3 -= stack3[top3++];
       }
    }
---------------------------------------------------------------------------------
22. Page Faults in LRU
-> Dry Run the Code 
->Page faults occur when they are not in memory 
static int pageFaults(int n, int c, int pages[]) {
		Set<Integer> set = new HashSet<>();
		HashMap<Integer, Integer> map = new HashMap<>(); 

		int pgfault = 0;

		for (int i = 0; i < n; i++) {
			if (set.size() < c) {
				if (!set.contains(pages[i])) {
					pgfault++;
					set.add(pages[i]);
				}
			} else {
				if (!set.contains(pages[i])) {
					pgfault++;
					// checking for Least Recently Used
					int lru = Integer.MAX_VALUE;// min index refers lru
					int val = 0;
					for (Integer s : set) {
						if (map.get(s) < lru) {
							lru = map.get(s);
							val = s;
						}
					}
					set.remove(val);
					set.add(pages[i]);
				}
			}
			map.put(pages[i], i);
		}

		return pgfault;
	}
---------------------------------------------------------------------------------
23. DEFKIN | Defence of a Kingdom (Spoj)
		int t = scn.nextInt();
		while (t-- > 0) {
			int w = scn.nextInt();
			int h = scn.nextInt();
			int n = scn.nextInt();
			int[] x = new int[n + 1];
			int[] y = new int[n + 1];

			for (int i = 0; i < n; i++) {
				x[i] = scn.nextInt();
				y[i] = scn.nextInt();
			}
			x[n] = w + 1;
			y[n] = h + 1;

			if (n == 0) {
				System.out.println(w * h);
				continue;
			}

			Arrays.sort(x);
			Arrays.sort(y);

			int mx = x[0] - 1;
			for (int i = 1; i < x.length; i++) {
				mx = Math.max(mx, x[i] - x[i - 1] - 1);
			}
			int my = y[0] - 1;
			for (int i = 1; i < y.length; i++) {
				my = Math.max(my, y[i] - y[i - 1] - 1);
			}
			int area = mx * my;
			System.out.println(area);
		}
---------------------------------------------------------------------------------
24. DIEHARD - DIE HARD (Spoj)
public static void main(String args[]) {

		int t = scn.nextInt();
		while (t-- > 0) {
			int H = scn.nextInt();
			int A = scn.nextInt();

			int days = 1;
			H += 3;
			A += 2;
			while (H > 0 && A > 0) {

				if (H > 5 && A > 10) {
					H -= 5;
					A -= 10;
					days++;
				} else if (H > 20) {
					H -= 20;
					A += 5;
					days++;
				} else {
					break;
				}
				if (H > 0 && A > 0) {
					days++;
					H += 3;
					A += 2;
				}
			}
			System.out.println(days);
		}

---------------------------------------------------------------------------------
25. Wine trading in Gergovia (Spoj)
		while (true) {
			long n = scn.nextInt();
			if (n == 0) {
				break;
			}
			long ans = 0;
			long val = 0;
			for (int i = 1; i <= n; i++) {
				val += scn.nextInt();
				ans += Math.abs(val);
			}
			System.out.println(ans);
		}
---------------------------------------------------------------------------------
26. ARRANGE - Arranging Amplifiers (Spoj)
-> Read The question properly to know what exactly we have to do 
btw in this question 5 4 6-> if given amplication factors then to maximise it using given formula would be 6 5 4, because (4)^5^6  (^->power ) whether the base is small or not (except for one) the exponent should be larger for larger ans.
	public static void main(String args[]) {
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int[] arr = new int[n];

			for (int i = 0; i < arr.length; i++) {
				arr[i] = scn.nextInt();
			}
			Arrays.sort(arr);
			int i = 0;
			for (i = 0; i < n && arr[i] == 1; i++) {
				System.out.print(arr[i] + " ");
			}
			// special case 2^3 < 3^2
			if (i == n - 2 && arr[i] == 2 && arr[i + 1] == 3) {
				System.out.println(arr[i] + " " + arr[i + 1]);
			} else {

				for (int j = n - 1; j >= 0 && arr[j] != 1; j--)
					System.out.print(arr[j] + " ");

				System.out.println();
			}
		}
	}
---------------------------------------------------------------------------------
27. GCJ101BB - Picking Up Chicks (Spoj)
public static void main(String args[]) {
		int T = scn.nextInt();
		int Case = 1;
		while (T-- > 0) {
			int n = scn.nextInt(); // Given no. of chicks
			int k = scn.nextInt(); // Required no of chicks
			int b = scn.nextInt(); // Distance of barn
			int t = scn.nextInt(); // total given time

			int[] pos = new int[n];
			int[] speed = new int[n];
			for (int i = 0; i < pos.length; i++) {
				pos[i] = scn.nextInt();
			}
			for (int i = 0; i < speed.length; i++) {
				speed[i] = scn.nextInt();
			}
			int count = 0, swaps = 0, notPossible = 0;
			for (int i = n - 1; i >= 0; i--) {
				int Reqdis = b - pos[i];
				int dis = speed[i] * t;
				if (dis >= Reqdis) {
					count++; // no of chicks that reached the barn
					if (notPossible > 0)
						swaps += notPossible;
// when suppose some chicks(which are slow,cannot reach to barn) are ahead of a chick which can reach 
//then we will do cummulative swap
				} else
					notPossible++;

				if (count >= k)
					break;
			}
			if (count >= k)
				System.out.println("Case #" + Case + ": " + swaps);
			else
				System.out.println("Case #" + Case + ": IMPOSSIBLE");

			Case++;
		}
	}
---------------------------------------------------------------------------------
28. Maximum sum of (disjoint) pairs with specific difference
->disjoint pair-> (a,b) (c,d)
 public static int maxSumPairWithDifferenceLessThanK(int arr[], int n, int k) 
    {
        Arrays.sort(arr);
        int sum=0;
        int i=n-1;
        
        while(i>0){
            if(arr[i]-arr[i-1]<k){
                sum+=arr[i]+arr[i-1];
                i-=2;
            }else{
                i--;
            }
        }
        return sum;
    }
---------------------------------------------------------------------------------
29. Broken Calculator (LC-991)

// Proof of Greedy: https://leetcode.com/problems/broken-calculator/discuss/236565/Detailed-Proof-Of-Correctness-Greedy-Algorithm
        
    int brokenCalc(int x, int y){

    int count=0;
    while(y!=x)
    {
        if(x>=y) return ((x-y) + count);
        
        /* If y is even, the last move was multiplication, else decrement */
        if(y%2==0) y=y/2 ;
        else y++;
        
        // One operation used
        count ++;
    }
    
    return count;
}
---------------------------------------------------------------------------------
30. Boats to Save people (LC-881)

M1) Using Sorting
->
we sorted the people by their weight......then there are two cases:

CASE-I : "minimum weight" man can't sit with "maximum weight" man
it implies that "maximum weight" man can't sit with any other man
hence "maximum weight" man sits alone so decrement only high end pointer.

CASE-II : "minimum weight" man can sit with "maximum weight" man
it implies that "minimum weight" man can sit with any other man
since we want to maximize the amount of weight carried by a single boat we sit "minimum weight" man and "maximum weight" man together.
so increment low end pointer and decrement high end pointer.

public int numRescueBoats(int[] people, int limit) {
       Arrays.sort(people);
       int boats=0;
       int i=0,j=people.length-1;
        while(i<=j)
        {
            if(people[i]+people[j]<=limit)
            {
                i++;
                j--;
            } 
            else
                j--;
            boats++;
        }
        return boats;
    }

M2) Using Bucket
public int numRescueBoats(int[] people, int limit) {
        int[] buckets = new int[limit+1];
        for(int p: people) buckets[p]++;
        int start = 0;
        int end = buckets.length - 1;
        int solution = 0;
        while(start <= end) {
            //make sure the start always point to a valid number
            while(start <= end && buckets[start] <= 0) start++;
            //make sure end always point to valid number
            while(start <= end && buckets[end] <= 0) end--;
            //no one else left on the ship, hence break.
            if(buckets[start] <= 0 && buckets[end] <= 0) break;
            solution++;
            if(start + end <= limit) buckets[start]--; // both start and end can carry on the boat
            buckets[end]--;
        }
        return solution;
    }
---------------------------------------------------------------------------------
31. Police & Thieves (GFG)
->
 static int catchThieves(char arr[], int n, int k) 
    { 
        List<Integer>thief = new ArrayList<>();
        List<Integer>police = new ArrayList<>();
        
        for(int i=0;i<n;i++){
            if(arr[i]=='P'){
                police.add(i);
            }else{
                thief.add(i);
            }
        }
        
        int i=0;
        int j=0;
        
        int ans=0;
        while(i<police.size() && j<thief.size()){
            int pi = police.get(i);
            int ti = thief.get(j);
            if(Math.abs(pi-ti)<=k){
                ans++;
                i++;
                j++;
            }else if(pi<ti)i++;
            else j++;
        }
        return ans;
    } 
---------------------------------------------------------------------------------
32. Minimum Deletions to Make Character Frequencies Unique (LC-1647)

M1) Sorting
// Example:  freq = [50, 50, 49, 6, 5]
// So for the second 50, exp = 49; And for 49, exp = 48;
// And for 6, exp = 47, but 47 > 6 let's re-adjust exp = 6.

    public int minDeletions(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        Arrays.sort(freq);
        int exp = freq[25];
        int res = 0;
        for (int i = 25; i >= 0; i--) {
            if (freq[i] == 0) break;
            if (freq[i] > exp) {
                res += freq[i] - exp;
            } else {
                exp = freq[i];
            }
            if (exp > 0) exp--; // Lowest exp is zero, cannot be negative
        }
        return res;
    }

M2) HashSet

 public int minDeletions(String s) {
        int[] charCount = new int[26];
        
        for(char ch : s.toCharArray()){
            charCount[ ch - 'a'] ++;
        }
        
        HashSet<Integer> set = new HashSet<>();
        int deletion = 0;
        
        for(int val : charCount){
            while(val !=0 && set.contains(val)){
                val--;
                deletion++;
            }
            set.add(val);          
        }
       
        return deletion;
    }
---------------------------------------------------------------------------------
33. Minimum Increment to Make Array Unique (LC-945)
-> Similar to above

  public int minIncrementForUnique(int[] A) {
        Arrays.sort(A);
        int res = 0, need = 0;
        for (int a : A) {
            res += Math.max(need - a, 0);
            need = Math.max(a, need) + 1; //the current number need to be at least prev + 1.
        }
        return res;
    }
---------------------------------------------------------------------------------
34. Candy (LC-135)

M1) O(N) Space

    public int candy(int[] ratings) {
        int sum=0;
        int[] a=new int[ratings.length];
        for(int i=0;i<a.length;i++)
        {
            a[i]=1;
        }
        for(int i=0;i<ratings.length-1;i++)
        {
            if(ratings[i+1]>ratings[i])
            {
                a[i+1]=a[i]+1;
            }
        }
        for(int i=ratings.length-1;i>0;i--)
        {
            if(ratings[i-1]>ratings[i])
            {
                if(a[i-1]<(a[i]+1))
                {
                    a[i-1]=a[i]+1;
                }
            }
        }
        for(int i=0;i<a.length;i++)
        {
            sum+=a[i];
        }
        return sum;
    }

M2) O(1) Space
->  With Proof:    
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------