Knowledge Guide
Home › DSA

Greedy

Step 17 in the DSA path · 1 concepts · 6 problems

0 / 7 complete

📘 Learn Greedy from zero

Greedy builds a solution by repeatedly taking the choice that looks best right now and never undoing it. It works only when a local optimum is provably part of a global optimum (an exchange argument or a monotonic invariant guarantees no future regret). Trigger: reach for greedy when you can scan the input once, maintain a small running state (a counter, a "last kept" value, a stack-like balance), and at each element make an irreversible decision that can be justified as safe. Canonical problem here: LeetCode 921 — Minimum Add to Make Parentheses Valid on input s = "())(", where we greedily match every ) against an open ( the instant we see it.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Setup & invariant
index : 0   1   2   3
char  : (   )   )   (
        ^
        i

balance = 0   (open '(' waiting to close)
add     = 0   (forced insertions)

We scan left to right keeping two counters. balance = number of ( still open; add = insertions we are forced to make. Invariant: the prefix to the left of i is already made valid using exactly add insertions. We never look back, which is what makes this greedy.

Step 2 — i=0 sees '('
index : 0   1   2   3
char  : (   )   )   (
        ^
        i

balance = 1   <-- incremented
add     = 0

An open paren is always safe to keep: it costs nothing now and may be matched later by a future ). We just push it onto our running balance (balance = 1). No decision to regret — deferring is strictly better than inserting.

Step 3 — i=1 sees ')', balance>0 → match
index : 0   1   2   3
char  : (   )   )   (
        \__/
         matched
            ^
            i

balance = 0   <-- decremented (consumed the '(')
add     = 0

We meet ) with balance = 1 > 0, so a real open paren is available. Greedily match it now (balance--). Matching the nearest open paren is always safe: any valid pairing can be rearranged to pair this ) with an earlier ( without increasing cost (exchange argument).

Step 4 — i=2 sees ')', balance==0 → must insert
index :  0   1   2   3
char  :  (   )   )   (
                 ^
                 i

insert '(' just before index 2:
         (   )  [(]  )   (
                 ^^^
              inserted

balance = 0   (the inserted '(' is immediately matched by this ')')
add     = 1   <-- forced one '(' to the left

Now ) arrives with balance = 0 — no open paren to match. The only repair is to insert a single ( immediately before this ), so add = 1. The inserted ( is consumed at once, leaving balance = 0. This is forced, not a guess: an unmatchable ) can only ever be fixed by adding a ( to its left, so doing it immediately is optimal.

Step 5 — i=3 sees '('
index : 0   1   2   3
char  : (   )   )   (
                    ^
                    i

balance = 1   <-- incremented
add     = 1

Another open paren. Same logic as Step 2: keep it for free and bump balance to 1. We end the scan here, but this ( has nothing after it to close against — it will need handling in the final tally.

Step 6 — End of scan: account for leftovers
index : 0   1   2   3
char  : (   )   )   (
        \__/        ^
        matched   unclosed '('

balance = 1   (1 open '(' never closed)
add     = 1   (1 ')' that needed a '(')

answer = add + balance = 1 + 1 = 2

After the scan, every unmatched ) already cost 1 each (in add), and every still-open ( in balance needs a matching ) appended — 1 each. Total = add + balance = 2.

Step 7 — Verify the fix
original :  (  )      )      (
repaired :  (  )   (  )      (  )
            keep    ^^^^      ^^^^
                  insert (    append )
                 before i=2   at end

Result string "()()()"  -> balanced, length 6
Insertions used  = 2  (1 '(' + 1 ')', matches answer)

Inserting one ( (before index 2) and one ) (at the end) turns ())( into ()()() — a fully balanced string with exactly 2 edits. No sequence of fewer edits can work, because each forced decision was the unique safe move — confirming the greedy result.

Step 8 — Why greedy is provably optimal
Decision table (each row is irreversible):
  see '('            -> balance++          (free, deferrable)
  see ')', bal > 0   -> balance--          (match nearest)
  see ')', bal == 0  -> add++              (only repair)
  end                -> answer = add + balance

No backtracking. One pass. O(n) time, O(1) space.

Each step is locally optimal and never blocks a better future choice: open parens are free to defer, unmatchable closers have exactly one fix. An exchange argument shows any optimal solution can be morphed into ours without extra cost — the hallmark that licenses greedy over DP here.

🎯 Guided practice

  1. Easy — Valid Palindrome II. Given s = "abca", can it become a palindrome by deleting at most one character?

    Step 1: Two pointers i=0, j=len-1; walk inward while s[i]==s[j]. Here s[0]=a==s[3]=a, so advance to i=1, j=2.

    Step 2: Mismatch: s[1]='b' vs s[2]='c'. Spend the one allowed deletion greedily by branching exactly once: either skip s[i] or skip s[j].

    Step 3: Check whether s[i+1..j] = s[2..2] = "c" is a palindrome (a single char — yes) OR s[i..j-1] = s[1..1] = "b" is a palindrome (yes). Either branch succeeds, so return true. (Concretely, deleting index 2 yields "aba"; deleting index 1 yields "aca".)

    Pattern: branch once at the first conflict, then verify each remainder in O(n). Total O(n) time, O(1) space.

  2. Medium — Minimum Add to Make Parentheses Valid. Given s = "())(", find the minimum insertions to balance it.

    Step 1: Single left-to-right scan. Keep open (unmatched () and adds (insertions needed).

    Step 2: ( → open=1. ) → matches, open=0. ) → open is 0, so we must insert a ( now: adds=1, open stays 0. ( → open=1.

    Step 3: End with open=1 unmatched (, each needing a closing ): answer = adds + open = 1 + 1 = 2.

    Why greedy is optimal: fixing a deficit the instant balance goes negative is forced — that ) can never be matched by anything to its right, so deferring the fix can only add cost, never save it. O(n) time, O(1) space. The same running-balance instinct shows up in "Remove Duplicate Letters," but there the right tool is a monotonic stack: while the current letter is smaller than the stack top and that top still appears later in the string, pop the top, then push the current letter (skipping letters already on the stack). That yields the lexicographically smallest result with each letter used exactly once.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic