Greedy

4 posts with the tag “Greedy”

Leetcode 55: Jump Game

Jul 3, 2025

Question

In this Leetcode question, we are given an array of numbers. We start at the first index of the array, and our goal is to reach the end of the array. Each value of the array represents the maximum jump distance to the right. For example, if the first index’s value is 5, you could jump anywhere between 1 to 5 indexs ahead. If the index’s value is 0, then we are NOT allowed to jump anywhere beyond that spot, effectively trapping us. It is important to note that we are never given negative values in the given array. This means that leftward jumps are never allowed, given this constraint of the array Numbers.

Our goal is to determine if we can reach the end using any series of jumps. We return true or false depending on the reachability of the array’s end.

Solving

To solve this Leetcode problem, I used a greedy approach. I used a for loop to iterate left to right through the array. Whilst I traverse the array, the variable named maxJump records the furthest reachable index. In-between iterations, I check whether my current position is ‘impossible’ to reach. If an impossible index is detected, we return false and terminate early. If we go throughout the entire array, from left to right, without hitting an impossible to reach spot, we return true.

TLDR:

Used a Greedy approach to traverse the array, determining if the array’s end is reachable using any series of jumps. I solved this problem by iterating throughout the array, searching for impossible to reach spots.

Leetcode 763: Partition Labels

Mar 28, 2025

DevGod

Elf Vtuber

For today’s daily leetcode problem, we are given a string and need to split it into as many partitions as possible, ensuring that each letter appears in at most one partition. Additionally, the partitions must preserve the order of letters as they appear in the original string. However, we don’t need to store the actual substrings—our task is simply to return the lengths of these partitions.

Example Walkthrough Consider the string “pizzatime”. The optimal partitions would be [1,6,1,1]. Here’s why:

The letters p, m, and e each form their own single-letter partitions since they don’t share any letter with another partition.
The substring “izzati” forms a partition because it contains multiple occurrences of i and z, and we need to ensure that all instances of a letter belong to a single partition.
Since the letters must remain in order and cannot belong to multiple partitions, “zzati” is grouped together with i to form a partition of length 6.

Another example is “partitionlabels”, which results in [1,13,1]:

The letters p and s form their own separate partitions.
The middle partition, “artitionlabel”, must include all occurrences of a and l.
Since l appears late in the string, we must extend the partition to ensure all ls are included, resulting in a large middle partition.

Implementation Approach Since I was in a hurry and the constraints were small, I used JavaScript’s built-in .lastIndexOf() method to determine the last occurrence of each letter in real time. The key insight is that a letter’s last occurrence dictates where a partition must end. While this approach runs in 𝑂(n^2) time due to repeated .lastIndexOf() calls, an optimized solution could use a hashmap for 𝑂(1) lookups.

To efficiently track when to end a partition, I maintain a max variable, representing the farthest last occurrence seen so far. As I iterate through the string, I update max using:

max = Math.max(max, s.lastIndexOf(s[L]));

This ensures that if a previous letter has a later last occurrence, we extend the current partition accordingly. This is crucial for cases like “partitionlabels”, where encountering l extends the partition beyond a’s last occurrence.

I iterate through the string using a loop and keep track of partitionSize. Whenever I reach max, I add partitionSize to the result array, reset it, and continue. Instead of constructing substrings, I only track partition lengths, as that’s all the problem requires.

This greedy approach ensures an optimal partitioning of the string while keeping the implementation simple and efficient.

Leetcode 921: Minimum Add To Make Parentheses Valid

Oct 7, 2024

DevGod

Elf Vtuber

About

This problem is very similar to yesterday’s problem. The main difference is instead of swapping characters that are already present in the string, we are appending either a ”(” or a ”)” anywhere we want in the string. However, we still have the same goal of finding the minimal number of operations needed to achieve a balanced string of () such that each opening symbol ( has a corresponding symbol ).

For example

((), needs 1 ) symbol at the end to become balanced
()()() is already balanced, so return 0
))) needs 3 opening symbols to become balanced

Thoughts

My thoughts immediately jumped to yesterday. The only difference is I ended up having two variables, one for the remainder of unmatched opening symbols, and one for the unmatched closing symbols. Once I was able to find these two values, at first I mistakenly thought it was some sort of find the max value between them. But in practice, it is the addition of both values together to get the minimal number of additions needed to balance the string.

Implementation

Here in JS, I use a for loop to iterate through the test case string, while also finding the leftmost character & the rightmost character. After I have these varibles, I am then able to move left to right to calculate the remainder of opening ( symbols, while also moving right to left to find the remainder of closing ) symbols. After my for loop is completed, I then return the amount of unmatched opening ( symbols plus the amount of matched closing symbols ) together.

Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

Oct 6, 2024

DevGod

Elf Vtuber

About

This leetcode problem is basically us to find the minimum number of swap operations are needed to make a string of ”[]” symbols balanced. Balanced being if each opening ”["" symbol also has a closing ”]” symbol. For example, the following would be examples of balanced strings.

[]
[[]]
[][][]

Thoughts

One thing to notice off the bat is when considering certain testcases, it is already possible that a string already contains a balanced string. For example, testcase ]][][[ already has a balanced string in the middle, so it is the same as ]][[. For example, all testcases either eventually become testcases such as ][, ]][[, ]]][[[ ect.

After we see this, it is now about finding a remainder inside our testcase string of extra unmatched chars. For example, in ][ the remained would be one, which can be viewed either as having one unmatched opening char, or one unmatched closed char.

After drawing out these certain testcases, I saw a certain pattern involving the remaining total of unmatched charecters in the sring.

][ = 1 Swaps needed
]][[ = 1 Swaps needed
]]][[[ = 2 Swaps needed
]]]][[[[ = 2 Swaps needed
]]]]][[[[[ = 3 Swaps needed

The pattern being, that for the remaining amount of unmatched symbols at the end of the string is then Math Ceil (remaining amount of unmatched chars / 2) is the number of swaps needed.

Implementation

There are two ways you can solve this problem. One way is to use a stack data structure to keep track of previous symbols, and then pushing and popping accordingly. However, what I ended up doing to save memory usage was to simulate the stack size instead. Since we only need to return the minimal amount of swaps needed, we don’t need to have a stack, only the state of the would be stack’s size / length. Once I for loop to simulate the stack size, I simply just return the Math.ceil(remainder / 2) to return the minimal amount of swaps needed.