Greedy

Greedy for Beginners https://leetcode.com/discuss/general-discussion/669996/greedy-for-beginners-problems-sample-solutions

122. Best Time to Buy and Sell Stock II

Add all slope of between the peeks and valleys when the second number is larger than the first one.

T: O(n) S: O(1)

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] >= 0) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

// Peak/Valley solution
int maxProfit(vector<int>& prices) {
    int peak = prices[0], valley = prices[0];
    int i = 0;
    int sum = 0;
    while (i < prices.size() - 1) {
        while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
        valley = prices[i];
        while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
        peak = prices[i];
        sum += peak - valley;
    }
    return sum;
}

55. Jump Game

Maintain the farest point it can jump, if i is larger than farest it means it is not possible to jump to i.

T: O(n) S: O(1)

    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        int farest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farest) return false;
            farest = Math.max(farest, i + nums[i]);
        }
        return true;
    }

45. Jump Game II

Initiate the maximum position that one could reach starting from the current index i or before: max_pos = nums[0]. Initiate number of steps: at least one, if array has more than 1 cell.

Iterate over number of elements in the input array:

• If max_step < i, one needs one more jump: jumps += 1. To minimize the number of jumps, choose the longest possible one: max_steps = max_pos.

• Update max_pos = max(max_pos, i + nums[i]).

    public int jump(int[] nums) {
        if (nums.length < 2) return 0;
        int maxPos = nums[0], maxSteps = nums[0];
        int step = 1;
        for (int i = 1; i < nums.length; i++) {
            if (maxSteps < i) {
                step++;
                maxSteps = maxPos;
            }
            maxPos = Math.max(maxPos, i + nums[i]);
        }
        return step;
    }

134. Gas Station

"The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That's what the first loop does.

If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station." @pigwall

T: O(n) S: O(1)

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

763. Partition Labels

Record all last indicies of each character. Consider the first label, say it's 'a'. The first partition must include the last occurrence of 'a'. However, before the last 'a' there might be a different label makes the partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.

public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); i++) {
        last[S.charAt(i) - 'a'] = i;
    }
    List<Integer> res = new ArrayList<>();
    int j = 0, anchor = 0;
    for (int i = 0; i < S.length(); i++) {
        j = Math.max(j, last[S.charAt(i) - 'a']);
        if (i == j) {
            res.add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return res;
}

843. Guess the Word

Narrow down the answer by guessing the score and update the list to ONLY keep the ones that have exact x matches with word. In this way, we narrow the candidates after we call master.guess(), and guarantee that secret is in candidates left. Full explanation.

T: O(n^2)

public void findSecretWord(String[] wordlist, Master master) {
    Arrays.sort(wordlist);
    List<String> list = new ArrayList<>(Arrays.asList(wordlist));
    int score = -1;
    for (int i = 0; i < 10; i++) {
        score = master.guess(list.get(0));
        if (score == 6) return;
        list = updateList(list, list.get(0), score);
    }
}

private List<String> updateList(List<String> list, String target, int score) {
    List<String> res = new ArrayList<>();
    for (String s : list) {
        if (getSimilarityScore(s, target) == score) {
            res.add(s);
        }
    }
    return res;
}

private int getSimilarityScore(String s, String target) {
    int count = 0;
    for (int i = 0; i < Math.min(s.length(), target.length()); i++) {
        if (s.charAt(i) == target.charAt(i)) count++;
    }
    return count;
}

316. Remove Duplicate Letters

public String removeDuplicateLetters(String s) {
    if (s.length() == 0) {
        return "";
    }

    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    int pos = 0;  // position of the smallest lex character
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) < s.charAt(pos)) {
            pos = i;
        }
        if (--count[s.charAt(i) - 'a'] == 0) {
            break;
        }
    }

    char ch = s.charAt(pos);
    String remaining = s.substring(pos + 1).replaceAll(String.valueOf(ch), "");
    return ch + removeDuplicateLetters(remaining);  
}

1029. Two City Scheduling

int twoCitySchedCost(vector<vector<int>>& costs) {
    vector<int> refund;
    int N = costs.size()/2;
       int minCost = 0;
       for(vector<int> cost : costs){
        minCost += cost[0];
        refund.push_back(cost[1] - cost[0]); 
    }
    sort(refund.begin(), refund.end());
    for(int i = 0; i < N; i++){
        minCost += refund[i];
    }
    return minCost;
}

1419. Minimum Number of Frogs Croaking

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] count = new int[5]; // c, r, o, a, k
        int frogs = 0;
        int maxFrogs = 0;
        
        for (char ch : croakOfFrogs.toCharArray()) {
            if (ch == 'c') {
                count[0]++;
                frogs++;
                maxFrogs = Math.max(maxFrogs, frogs);
            } else if (ch == 'r') {
                if (count[0] == 0) return -1;
                count[0]--;
                count[1]++;
            } else if (ch == 'o') {
                if (count[1] == 0) return -1;
                count[1]--;
                count[2]++;
            } else if (ch == 'a') {
                if (count[2] == 0) return -1;
                count[2]--;
                count[3]++;
            } else if (ch == 'k') {
                if (count[3] == 0) return -1;
                count[3]--;
                frogs--;
            } else {
                return -1; // invalid char
            }
        }
        
        // All counts except 'k' should be zero at the end
        if (frogs == 0) {
            return maxFrogs;
        } else {
            return -1; // incomplete croak
        }
    }
}

1353. Maximum Number of Events That Can Be Attended

Let the current day be $i$. At each day, we perform the following steps:

• Add to the candidate queue (the min-heap) all meetings whose start day is less than or equal to $i$. At this point, the heap contains all meetings available to attend on day $i$ or earlier.

• Remove from the heap all meetings whose end day is less than $i$, as they can no longer be attended.

• If the heap is not empty, we attend the meeting with the earliest end time (which is at the top of the heap), increment the count of attended meetings by $1$, and remove it from the heap.

Finally, return the total number of meetings attended.

First Tab

class Solution {
    public int maxEvents(int[][] events) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int max = 0;
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        for (int[] e : events) {
            max = Math.max(max, e[1]);
        }
        int res = 0;
        for (int day = 1, j = 0; day <= max; day++) {
            while (j < events.length && events[j][0] <= day) {
                pq.offer(events[j][1]);
                j++;
            }
            while (!pq.isEmpty() && pq.peek() < day) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
        }
        return res;
    }
}

1005. Maximize Sum Of Array After K Negations

Sort

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
       // Sort to process smallest (most negative) numbers first
        sort(nums.begin(), nums.end());
        
        // Negate negative numbers first (greedy approach)
        for (int i = 0; i < nums.size() && k > 0; ++i) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            } else {
                break; // No more negative numbers
            }
        }
        
        // If k is still positive and odd, negate the smallest element
        if (k > 0 && k % 2 == 1) {
            sort(nums.begin(), nums.end()); // Re-sort after negations
            nums[0] = -nums[0]; // Negate smallest element
        }
        
        // Calculate sum
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        return sum;
    }
};

HashMap