Session 37: Greedy Algorithm

Original Session

Date: 02 Feb 2025

Topic: Greedy

Concept: Is just a way to solve problem.
Choosing what is optimal or less cost.

Programs

1. 135. Candy
   1. leetcode here

      class Solution {
          public int candy(int[] ratings) {
              
              int[] ans = new int[ratings.length];
              ans[0] = 1;
      
              for (int i=1; i<ratings.length; i++) {
      
                  if (ratings[i] > ratings[i-1]) {
                      ans[i] = ans[i-1] + 1;
                  } else {
                      ans[i] = 1;
                  }
              }
      
              for (int i = ratings.length-2; i>=0; i--) {
                  if (ratings[i] > ratings[i+1]) {
                      ans[i] = Math.max(ans[i+1]+1, ans[i]);
                  }
              }
      
              return Arrays.stream(ans).sum();
          }
      }

2. 134. Gas Station
   1. leetcode here

      class Solution {
          public int canCompleteCircuit(int[] gas, int[] cost) {
              
              int n = gas.length;
              int total = 0, avail = 0, start = 0;
      
              for (int i=0; i<n; i++) {
      
                  total = total + gas[i] - cost[i];
                  avail = avail + gas[i] - cost[i];
                  if (avail < 0) {
                      avail = 0;
                      start = i + 1;
                  }
      
              }
      
              if (total < 0) {
                  return -1;
              }
      
              return start;
          }
      }

3. 55. Jump Game
   1. leetcode here

      class Solution {
          public boolean canJump(int[] nums) {
              
              int reached = nums.length-1;
      
              for (int i = nums.length-1; i >= 0; i --) {
      
                  if ((nums[i] + i) >= reached) {
                      reached = i;
                  }
              }
      
              return reached == 0;
          }
      }

4. 221. Maximal Square
   1. leetcode here

      public int maximalSquare(char[][] matrix) {
              
              int m = matrix.length;
              int n = matrix[0].length;
              int[][] arr = new int[m][n];
              int size = 0;
      
              for (int i=0; i<m; i++) {
      
                  for (int j=0; j<n; j++) {
      
                      if (i == 0 || j == 0) {
      
                          if (matrix[i][j] == '1') {
                              arr[i][j] = 1;
                          }
                      } else {
      
                          if (matrix[i][j] == '1') {
                              arr[i][j] = Math.min(arr[i-1][j-1],
                              Math.min(arr[i-1][j], arr[i][j-1])) + 1;
                          }
                      }
                      size = Math.max(size, arr[i][j]);
                  }
              }
      
              return size * size;
          }