Greedy Algorithm : Three Problems That Taught Me to Think Beyond Brute Force

Harsh Jaiswal

9 min read

·

Oct 9, 2026

--

1

Listen

Share

Solving a LeetCode problem is not just about finding a solution that passes all test cases. The real learning happens when we understand why an approach works, which decisions we can make greedily, and how to prove that those decisions lead to the correct answer.

Recently, I solved three interesting LeetCode problems:

• 316. Remove Duplicate Letters — Stack + Greedy
• 621. Task Scheduler — Frequency Counting + Greedy Scheduling
• 135. Candy — Greedy + Two-Pass Traversal

Although these problems look different, each teaches an important lesson about making optimal decisions.

Let’s understand them one by one.

1. LeetCode 316 — Remove Duplicate Letters

Difficulty: Medium

Pattern: Monotonic Stack + Greedy

Problem Statement

Given a string s, remove duplicate letters so that every letter appears exactly once. The resulting string must be the smallest possible in lexicographical order among all valid answers.

For example:

Input:  s = "bcabc"
Output: "abc"

Another example:

Input:  s = "cbacdcbc"
Output: "acdb"

Notice that simply removing duplicate characters is not enough. We must also preserve the relative order of the remaining characters and obtain the lexicographically smallest answer.

Step 1: Understand the Greedy Intuition

Suppose we are building our answer from left to right.

When we encounter a character, we have two choices:

1. Include it if it has not already been included.
2. If it is smaller than the last character in our answer, consider removing that last character to make the answer lexicographically smaller.

But there is an important condition!

We can remove a character only if it appears again later in the string.

Otherwise, removing it would mean that the character disappears completely from the answer.

For example, consider:

s = "bcabc"

Initially:

Answer = ""

We process the characters one by one.

CharacterDecisionStackbAdd bbcAdd cbcaRemove c, then b, because both appear laterabAdd babcAdd cabc

Final answer:

"abc"

When we encounter a, both b and c are greater than a. Since both occur again later, we can safely remove them and obtain a smaller answer.

This is the core greedy decision.

Step 2: Why Do We Need a Stack?

A stack gives us access to the most recently added character.

That is exactly what we need because we only want to compare the current character with the last character in our answer.

We use three things:

• last: stores the last occurrence of every character.
• visited: tells us whether a character is already in the answer.
• stack: maintains our answer while allowing us to remove characters from the end.

Press enter or click to view image in full size

Step 4: Understand the Important Conditions

Condition 1:

if (visited[ch - 'a'])
    continue;

If the character is already present in our answer, we skip it. Every character must appear exactly once.

Condition 2:

st.back() > ch

The last character in the stack is greater than the current character. Replacing that larger character with the smaller current character can improve lexicographical order.

Condition 3:

last[st.back() - 'a'] > i

The character at the top of the stack occurs again later. Therefore, removing it now will not cause us to lose that character permanently.

Why reset visited?

visited[st.back() - 'a'] = false;

Once a character is removed from the stack, it must be allowed to enter the answer again when we encounter it later.

Without resetting visited, the algorithm could incorrectly skip it.

Complexity Analysis

• Time Complexity: O(n), because each character is pushed onto and popped from the stack at most once.
• Space Complexity: O(1) auxiliary space, excluding the output string, because the alphabet contains only 26 lowercase English letters.

Key Takeaway

The lesson from this problem is that greedy decisions sometimes require future information.

We use last-occurrence indices to determine whether removing a character is safe, and a monotonic stack to maintain the smallest possible answer.

2. LeetCode 621 — Task Scheduler

Difficulty: Medium

Pattern: Frequency Counting + Greedy Scheduling

Problem Statement

We are given a list of CPU tasks represented by capital letters and an integer n, representing the cooldown period.

The CPU can execute one task per interval. After executing a task, the same task cannot be executed again until at least n intervals have passed.

During these intervals, the CPU can execute other tasks or remain idle.

We need to return the minimum number of intervals required to execute all tasks.

Example:

Input:
tasks = ["A","A","A","B","B","B"]
n = 2

Output: 8

One valid schedule is:

A B idle A B idle A B

The total is eight intervals.

Step 1: Why Is This a Greedy Problem?

Suppose task A occurs three times and task B also occurs three times.

If we execute all the A tasks together, we violate the cooldown requirement.

Instead, we should prioritize the most frequent tasks and distribute their occurrences across the schedule.

The key observation is:

The task that occurs most frequently determines how much space the schedule may need.

Other tasks can often fill the cooldown gaps.

Step 2: Calculate the Frequency

For the example:

A = 3
B = 3

The maximum frequency is:

maxFreq = 3

The number of tasks that share this maximum frequency is:

countMax = 2

We can calculate the minimum schedule length using:

intervals=(maxFreq−1)(n+1)+countMax\text{intervals} = (\text{maxFreq}-1)(n+1)+\text{countMax}

Substituting our values:

(3−1)(2+1)+2(3–1)(2+1)+2 =2×3+2=8=2\times3+2=8

Therefore, the answer is 8.

Step 3: Understand the Formula

Consider the most frequent task, A.

It appears three times, so we have two gaps between its occurrences:

A _ _ A _ _ A

Each gap must contain at least n = 2 intervals.

The first two occurrences create the repeating blocks:

A _ _
A _ _
A

The number of complete blocks before the final occurrence is:

maxFreq - 1

Each block needs:

n + 1

intervals: one task followed by n cooldown intervals.

Finally, we add countMax because all tasks tied for the maximum frequency can occupy the final block.

This gives us:

(maxFreq−1)(n+1)+countMax(\text{maxFreq}-1)(n+1)+\text{countMax}

However, this formula is not always the final answer.

If there are many different tasks and the CPU can execute them without needing idle intervals, the total number of tasks may be larger than this formula.

Therefore, the complete answer is:

max⁡(N, (maxFreq−1)(n+1)+countMax)\boxed{ \max\left( N,\, (\text{maxFreq}-1)(n+1)+\text{countMax} \right) }

Here, NN represents the total number of tasks.

Step 4: C++ Solution

Press enter or click to view image in full size

Step 5: Dry Run

For:

tasks = ["A","A","A","B","B","B"]
n = 2

Frequency array:

A = 3
B = 3

After sorting, the maximum frequency is 3.

maxFreq = 3
countMax = 2

Calculate:

result = (3 - 1) * (2 + 1) + 2
       = 2 * 3 + 2
       = 8

Total number of tasks:

tasks.size() = 6

Finally:

max(6, 8) = 8

Answer:

8

What If the Cooldown Is Zero?

If n = 0, there is no restriction on repeating tasks. The minimum number of intervals is simply the number of tasks.

The max() in our formula handles this case too.

Complexity Analysis

• Time Complexity: O(N + 26 log 26), which simplifies to O(N), because there are only 26 possible task types.
• Space Complexity: O(1) auxiliary space, because the frequency array has a fixed size of 26.

Key Takeaway

The important lesson from Task Scheduler is that we do not always need to simulate every interval.

By counting frequencies and identifying the most frequent task, we can derive a mathematical formula for the optimal schedule.

3. LeetCode 135 — Candy

Difficulty: Hard

Pattern: Greedy + Two-Pass Traversal

Problem Statement

There are n children standing in a line. Each child has a rating.

We must distribute candies according to two rules:

1. Every child must receive at least one candy.
2. A child with a higher rating than an adjacent child must receive more candies than that neighbor.

Our objective is to minimize the total number of candies distributed.

Example:

Input:
ratings = [1, 0, 2]

Output: 5

One valid distribution is:

Ratings: [1, 0, 2]
Candies: [2, 1, 2]

Total:

2 + 1 + 2 = 5

Step 1: Start With One Candy Per Child

Every child must receive at least one candy.

Therefore, our initial distribution is:

Ratings: [1, 0, 2]
Candies: [1, 1, 1]

Now we must adjust the candies to satisfy the rating conditions while keeping the total as small as possible.

Step 2: Why Is One Pass Not Enough?

Consider:

ratings = [1, 2, 3, 4]

A child with a higher rating than their left neighbor must receive more candy.

The distribution must become:

[1, 2, 3, 4]

Now consider the reverse:

ratings = [4, 3, 2, 1]

The distribution must be:

[4, 3, 2, 1]

A left-to-right pass handles increasing ratings, but it cannot fully handle decreasing sequences.

That is why we need two passes.

• Left to right: satisfy the condition with the left neighbor.
• Right to left: satisfy the condition with the right neighbor.

Step 3: First Pass — Left to Right

Initialize:

vector<int> candy(n, 1);

Now compare each child with the child immediately to their left.

If the current rating is higher, give the current child one more candy than the previous child.

for (int i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
        candy[i] = candy[i - 1] + 1;
    }
}

For:

ratings = [1, 0, 2]

The ratings increase only from 0 to 2.

After the first pass:

Candies = [1, 1, 2]

This satisfies the left-neighbor condition, but we still need to check the right-neighbor condition.

Step 4: Second Pass — Right to Left

Now move from right to left.

If a child has a higher rating than the child to their right, they must receive more candies.

However, we must not reduce the candy count already assigned during the first pass.

Therefore, we use:

for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = max(candy[i], candy[i + 1] + 1);
    }
}

Why max()?

Suppose the first pass has already assigned three candies to a child. The second pass might require only two.

We cannot reduce the count to two, because that could violate the condition with the left neighbor.

So we keep whichever value is larger:

max(currentCandies, rightNeighborCandies + 1)

After the second pass, our example becomes:

Ratings: [1, 0, 2]
Candies: [2, 1, 2]

The total is:

2 + 1 + 2 = 5

Step 5: C++ Solution

Press enter or click to view image in full size

Step 6: Dry Run

Let’s use a more interesting example:

ratings = [1, 2, 2]

Initially:

candies = [1, 1, 1]

After the left-to-right pass:

• Rating 2 is higher than rating 1, so the second child receives two candies.
• The third child has the same rating as the second child, so no increase is needed.

candies = [1, 2, 1]

During the right-to-left pass:

• The third child’s rating is not higher than the second child’s rating.
• No further adjustment is necessary.

Final distribution:

[1, 2, 1]

Total:

1 + 2 + 1 = 4

Notice that equal ratings do not require different candy counts. The requirement applies only when one child’s rating is strictly greater than an adjacent child’s rating.

Complexity Analysis

• Time Complexity: O(n), because we make two passes through the ratings and one pass to calculate the total.
• Space Complexity: O(n), because we maintain a candy array.

Key Takeaway

The Candy problem teaches us that a greedy algorithm may need multiple passes when a decision depends on constraints in both directions.

The first pass handles left-side relationships, and the second pass fixes right-side relationships without undoing previous requirements.

What These Three Problems Taught Me

These problems strengthened my understanding of three different patterns.

ProblemMain PatternCore Insight

LC 316 — Remove Duplicate LettersMonotonic Stack + GreedyRemove a larger character only when it can safely appear again later.

LC 621 — Task SchedulerFrequency Counting + GreedyThe most frequent tasks determine the minimum schedule length.

LC 135 — CandyTwo-Pass GreedySatisfy constraints from both directions without reducing previously required candy counts.

Final Thoughts

One of the most important lessons I am learning through DSA is that different problems require different ways of thinking.

• Stacks help us maintain an optimal partial answer.
• Frequency counting helps us identify the elements that dominate a problem.
• Multiple greedy passes help us satisfy constraints that depend on both sides of an element.

Instead of memorizing solutions, I am focusing on understanding the reasoning behind them, identifying the correct pattern, and knowing why the algorithm works.

The goal is not just to solve more problems. It is to become better at recognizing the right approach when facing a completely new problem.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#GreedyAllocation #Scheduling #GreedyAlgorithm #DSA #CodingInterview #EnjoyProblems