While learning Data Structures and Algorithms, I recently started revising Trie (Prefix Tree), a tree-based data structure mainly used for storing and searching strings efficiently.

Unlike arrays, linked lists, or binary search trees, Trie is specifically designed to handle strings and their prefixes.

For example, consider these words:

• apple
• app
• application
• apt
• bat

Instead of storing these words independently, Trie stores their characters in a tree structure, allowing words with common prefixes to share the same path.

This makes Trie particularly useful in applications such as:

• Autocomplete and search suggestions.
• Dictionary implementations.
• Prefix-based searching.
• Spell checking.
• Word searching.

Let’s understand how it works.

1. What is Trie?

A Trie (Prefix Tree) is a tree-based data structure in which each node represents a character, and the path from the root to a node represents a prefix or a complete word.

The important idea behind Trie is that words having common prefixes share the same nodes.

For example, consider:

apple, app, apt, bat

Their Trie representation looks like this:

                  Root
                 /    \
                a      b
                |      |
                p      a
               / \     |
              p   t    t
              |
              l
              |
              e

Here:

• apple and app share the prefix app.
• app and apt share the prefix ap.
• bat follows a separate path.
• Each word-ending node is marked using a boolean variable called isEnd.

Important: Reaching a node does not necessarily mean that a complete word exists. We need isEnd = true to identify a complete word.

2. Trie Node Structure

In a standard Trie implementation for lowercase English letters, each node contains:

1. children[26]: An array of pointers representing the 26 possible lowercase English characters.
2. isEnd: A boolean variable indicating whether a complete word ends at that node.

class Node {
public:
    Node* children[26];
    bool isEnd;

    Node() {
        for(int i = 0; i < 26; i++) {
            children[i] = NULL;
        }

        isEnd = false;
    }
};

Why do we use children[26]?

We map every lowercase English character to an index:

int idx = ch - 'a';

For example:

• a → 0
• b → 1
• c → 2
• z → 25

This allows us to access the next character directly in O(1) time.

3. Important Trie Operations

There are three fundamental operations that we should understand.

A. Insert()

The insert operation adds a word into the Trie.

Approach:

1. Start from the root node.
2. Traverse every character of the word.
3. Calculate its index using ch - 'a'.
4. If the corresponding child does not exist, create a new node.
5. Move to that child.
6. After processing all characters, mark the current node as isEnd = true.

void insert(string word) {
    Node* curr = root;

    for(char ch : word) {
        int idx = ch - 'a';

        if(curr->children[idx] == NULL) {
            curr->children[idx] = new Node();
        }

        curr = curr->children[idx];
    }

    curr->isEnd = true;
}

B. Search()

The search operation checks whether a complete word exists in the Trie.

Approach:

1. Start from the root.
2. Traverse each character.
3. If any required child does not exist, return false.
4. Otherwise, continue moving through the Trie.
5. After processing the complete word, check isEnd.

bool search(string word) {
    Node* curr = root;

    for(char ch : word) {
        int idx = ch - 'a';

        if(curr->children[idx] == NULL) {
            return false;
        }

        curr = curr->children[idx];
    }

    return curr->isEnd;
}

Important: We check isEnd because a prefix can exist without being a complete word.

C. StartsWith()

This operation checks whether any word in the Trie starts with a given prefix.

Unlike search, it does not require the last node to have isEnd = true.

bool startsWith(string prefix) {
    Node* curr = root;

    for(char ch : prefix) {
        int idx = ch - 'a';

        if(curr->children[idx] == NULL) {
            return false;
        }

        curr = curr->children[idx];
    }

    return true;
}

4. Time and Space Complexity

Let L represent the length of the given word or prefix.

OperationTime ComplexityInsertO(L)SearchO(L)StartsWithO(L)

Space Complexity: O(N × L) in the worst case, where N is the number of inserted words and L is their maximum length, assuming a fixed 26-character alphabet.

Trie is efficient for prefix-based operations because we only traverse the characters of the given string instead of checking every stored word.

5. LeetCode Problems I Solved

After understanding the basic Trie implementation, I applied the concept to three LeetCode problems. Each problem introduced a different application of Trie.

Problem 1: LC 208 — Implement Trie (Prefix Tree)

Difficulty: Medium

What does the problem ask?

We need to design a Trie data structure that supports three operations:

1. insert(word): Insert a word into the Trie.
2. search(word): Check whether the complete word exists in the Trie.
3. startsWith(prefix): Check whether any previously inserted word starts with the given prefix.

For example:

Trie trie;

trie.insert("apple");

trie.search("apple");     // true
trie.search("app");       // false
trie.startsWith("app");   // true

trie.insert("app");

trie.search("app");       // true

Notice the difference between search() and startsWith().

Although "app" is a prefix of "apple", it is not initially a complete word in the Trie. Therefore, search("app") returns false, while startsWith("app") returns true.

Approach: Basic Trie Implementation

I implemented a custom Node class containing:

• An array of 26 child pointers.
• A boolean isEnd to identify the end of a complete word.

I maintained a root pointer and implemented all three operations using iterative traversal.

The insertion operation creates nodes when they do not exist, while searching follows the existing character paths.

Key Learning: Understanding the Trie node structure, character mapping, and the importance of the isEnd flag.

LeetCode 208 — Implement Trie

Problem 2: LC 211 — Design Add and Search Words Data Structure

Difficulty: Medium

What does the problem ask?

We need to design a data structure that supports two operations:

1. addWord(word): Add a word to the data structure.
2. search(word): Check whether a word exists in the data structure.

However, there is an additional condition: the search operation supports the . character as a wildcard.

The . character can represent any single character.

For example:

addWord("bad");
addWord("dad");
addWord("mad");

search("pad");  // false
search("bad");  // true
search(".ad");  // true
search("b..");  // true

Here:

• "pad" returns false because no matching word exists.
• "bad" returns true because the exact word exists.
• ".ad" returns true because . can represent b, d, or m.
• "b.." returns true because the two dots can represent a and d.

Approach: Trie + DFS + Backtracking

The insertion operation works exactly like the basic Trie implementation in LC 208.

The main challenge is handling the wildcard character during searching.

We handle two cases:

Case 1: Current character is not .

• Calculate the character index.
• Check whether the corresponding child exists.
• If it does not exist, return false.
• Otherwise, recursively search the next character.

Case 2: Current character is .

Since the dot can represent any character, we cannot follow just one child.

Instead, we explore all existing children using DFS.

If any recursive path successfully matches the remaining characters, we return true.

Once we process the entire search word, we check whether the current node has isEnd = true.

Key Learning: This problem taught me how to combine Trie with DFS and Backtracking to handle wildcard-based searching.

LeetCode 211 — Design Add and Search Words Data Structure

Problem 3: LC 1268 — Search Suggestions System

Difficulty: Medium

What does the problem ask?

We are given:

• An array of product names.
• A string called searchWord.

We need to build a search suggestion system.

As the user types each character of the search word, we must display up to three product suggestions that match the current prefix.

The suggestions must be in lexicographical (dictionary) order.

For example:

products = {
    "mobile",
    "mouse",
    "moneypot",
    "monitor",
    "mousepad"
};

searchWord = "mouse";

The expected output is:

[
    ["mobile", "moneypot", "monitor"],
    ["mobile", "moneypot", "monitor"],
    ["mouse", "mousepad"],
    ["mouse", "mousepad"],
    ["mouse", "mousepad"]
]

Approach: Trie + Sorting + Suggestions

I followed these steps:

1. Sort all products lexicographically.
2. Insert every product into the Trie.
3. Each Trie node maintains a list of at most three suggestions.
4. During insertion, add the current product to the suggestion list of every node along its path, provided the list contains fewer than three products.
5. Since products are inserted in sorted order, the first three stored products are already the lexicographically smallest suggestions.
6. Traverse the Trie according to the search word, character by character.
7. After reaching each prefix node, return its stored suggestions.

If a character path does not exist, return an empty list for that prefix and all remaining prefixes.

Key Learning: This problem demonstrated how Trie can be extended to build an autocomplete system by storing useful information at every prefix node.

LeetCode 1268 — Search Suggestions System

Final Takeaway

These three problems helped me understand Trie from three different perspectives:

• LC 208: How to implement and operate a Trie.
• LC 211: How to handle wildcard characters using DFS and Backtracking.
• LC 1268: How to use Trie for real-world autocomplete and search suggestions.

This revision reinforced an important DSA lesson: learning a data structure is not just about understanding its implementation, but also about recognizing how to adapt it to solve different problems.

6. What I Learned from These Three Problems

These three problems helped me understand how the same Trie data structure can be adapted to solve different problems.

The interesting part is that the underlying Trie structure remains almost the same, but the searching logic changes according to the problem requirements.

Conclusion

Trie is one of the important data structures for string and prefix-based problems.

Initially, understanding the node structure, child pointers, and isEnd flag is essential. Once these fundamentals are clear, we can extend Trie with DFS, Backtracking, Sorting, and other techniques to solve more complex problems.

My biggest takeaway from revising Trie is that understanding the structure is only the first step; learning how to adapt it to different problem requirements is what makes it powerful.

👋 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

#Tries #Leetcode #DSA #CodingInterview #EnjoyProblems

While revising Data Structures and Algorithms, I decided to focus on Hashing and understand how different hash-based data structures work.

Before this revision, I had already encountered hash maps and sets in several DSA problems. However, I wanted to understand them more deeply, especially the differences between ordered and unordered containers, their internal working, and when to use each one.

During this revision, I explored four important problems:

• LeetCode 128 — Longest Consecutive Sequence
• LeetCode 560 — Subarray Sum Equals K
• LeetCode 438 — Find All Anagrams in a String
• LeetCode 146 — LRU Cache

These problems demonstrate how hashing can optimize solutions and reduce unnecessary operations.

Let’s understand everything step by step.

1. What Is Hashing?

Hashing is a technique used to store and retrieve data efficiently.

It uses a hash function to convert a key into an index (or hash value), which helps determine where the corresponding data should be stored.

Consider a simple example:

Suppose we have the following values:

10, 20, 30, 40, 50

If we want to check whether a particular value exists, searching through an array requires checking elements one by one.

In the worst case, this takes O(n) time.

With hashing, we can calculate a location using a hash function and access the corresponding data much faster.

For example:

hash(10) = 10 % 10 = 0
hash(20) = 20 % 10 = 0
hash(30) = 30 % 10 = 0

This is a simplified hash function, but it demonstrates an important concept.

How Does Hashing Work Internally?

Hashing generally involves three important components:

1. Key

The value that we want to store or search.

2. Hash Function

A function that converts the key into a hash value.

3. Bucket

A storage location in the hash table where elements are organized.

The hash function determines which bucket should be used for a particular key.

What Is a Hash Collision?

A collision occurs when two different keys generate the same hash value.

For example:

hash(10) = 10 % 10 = 0
hash(20) = 20 % 10 = 0

Both values map to bucket 0.

This is called a hash collision.

Hash tables handle collisions using techniques such as:

• Separate Chaining: Multiple elements can be stored in the same bucket, commonly using linked structures.
• Open Addressing: Another available position is searched when a collision occurs.

C++ unordered containers use hash tables and implement collision handling internally.

What Is a Load Factor?

Load factor tells us how full a hash table is.

Formula:

Load Factor = Number of Elements / Number of Buckets

For example:

If a hash table contains 8 elements and 10 buckets:

Load Factor = 8 / 10 = 0.8

When the load factor becomes too high, the hash table may rehash.

Rehashing means increasing or changing the bucket arrangement and redistributing existing elements.

This helps maintain efficient operations.

2. Ordered vs Unordered Containers in C++

C++ provides four important STL containers that are useful when solving hashing-related problems.

A. map

map stores data in sorted order based on its keys.

Internally, it is generally implemented using a Red-Black Tree (a self-balancing binary search tree).

Example:

map<int, string> mp;

mp[3] = "Three";
mp[1] = "One";
mp[2] = "Two";

Output:

1 One
2 Two
3 Three

Even though we inserted 3, 1, and 2, the keys are automatically sorted.

Time Complexity:

OperationComplexity

Insert O(log n)

Search O(log n)

Delete O(log n)

Access by key O(log n)

B. unordered_map

unordered_map stores key-value pairs without maintaining sorted order.

It uses a hash table internally.

Example:

unordered_map<int, string> mp;

mp[3] = "Three";
mp[1] = "One";
mp[2] = "Two";

The iteration order is not guaranteed to be sorted.

Time Complexity:

Operation = Average : Worst

Insert = O(1) : O(n)

Search = O(1) : O(n)

Delete = O(1) : O(n)

The average O(1) complexity makes unordered_map very useful in DSA problems.

C. set

set stores unique elements in sorted order.

Example:

set<int> st;

st.insert(30);
st.insert(10);
st.insert(20);
st.insert(10);

Output:

10 20 30

Duplicate elements are automatically removed.

Time Complexity: Insert, search, and delete take O(log n).

D. unordered_set

unordered_set stores unique elements without maintaining sorted order.

Example:

unordered_set<int> st;

st.insert(30);
st.insert(10);
st.insert(20);
st.insert(10);

It stores only three unique elements.

Time Complexity:

• Insert: Average O(1)
• Search: Average O(1)
• Delete: Average O(1)

My understanding:

• Use map when sorted keys are required.
• Use unordered_map when fast key-value lookup is required.
• Use set when unique sorted elements are required.
• Use unordered_set when unique elements and fast lookup are required.

3. Important STL Functions

Before moving to the problems, let’s understand some frequently used functions.

unordered_map / map

unordered_map<int, int> mp;

// Insert or update
mp[10] = 5;

// Insert without overwriting an existing key
mp.insert({20, 10});

// Search
mp.find(10);

// Check existence
mp.count(10);

// Check whether key exists (C++20)
mp.contains(10);

// Remove
mp.erase(10);

// Number of elements
mp.size();

// Check whether empty
mp.empty();

// Remove everything
mp.clear();

Important difference:

mp[10]++;

If key 10 does not exist, it is automatically created with a default value of 0 and then incremented.

Whereas:

mp.find(10);

Only searches for the key. It does not insert anything.

set / unordered_set

unordered_set<int> st;

// Insert
st.insert(10);

// Search
st.find(10);

// Check existence
st.count(10);

// Check existence (C++20)
st.contains(10);

// Remove
st.erase(10);

// Number of elements
st.size();

// Check empty
st.empty();

// Remove all elements
st.clear();

Traversing Containers

for(auto it : mp) {
    cout << it.first << " " << it.second << endl;
}

For a set:

for(auto it : st) {
    cout << it << " ";
}

One important point: map and set maintain sorted order, whereas unordered containers do not guarantee any particular iteration order.

4. LeetCode 128 — Longest Consecutive Sequence

Problem: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Problem Link

Example

Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4

Explanation:

The longest consecutive sequence is:

1 → 2 → 3 → 4

Therefore, the answer is 4.

Approach: Using unordered_set

A straightforward approach would be sorting the array.

However, sorting takes O(n log n) time.

We can optimize this using unordered_set.

Step 1: Insert all elements into an unordered_set.

This removes duplicates and provides average O(1) lookup.

Step 2: Iterate through the set.

For every number, check whether its previous number (num - 1) exists.

• If it exists, the current number is not the beginning of a sequence.
• If it doesn’t exist, we have found the starting point of a sequence.

Step 3: Starting from that number, keep checking whether the next consecutive number exists.

Step 4: Update the maximum sequence length.

Dry Run

Input:

[100, 4, 200, 1, 3, 2]

After inserting elements:

{100, 4, 200, 1, 3, 2}

NumberPrevious Exists?Action100NoSequence length = 14Yes (3)Skip200NoSequence length = 11NoCheck 2, 3, 43Yes (2)Skip2Yes (1)Skip

The longest sequence is:

1 → 2 → 3 → 4

Answer = 4.

Time Complexity: O(n) average.

Space Complexity: O(n).

The important optimization is that we only start counting when we find the beginning of a sequence.

5. LeetCode 560 — Subarray Sum Equals K

Problem: Given an integer array and an integer k, return the total number of continuous subarrays whose sum equals k.

Problem Link

Example

Input: nums = [1, 1, 1], k = 2

Output: 2

Explanation:

There are two subarrays:

[1, 1] and [1, 1]

Both have a sum equal to 2.

Approach: Prefix Sum + unordered_map

This problem introduces an important hashing pattern: Prefix Sum + Hash Map.

First, understand prefix sum.

A prefix sum represents the sum of elements from the beginning of an array up to the current index.

For example:

nums = [1, 2, 3, 4]

Prefix Sum = [1, 3, 6, 10]

Suppose:

prefixSum = 6

We want to find a previous prefix sum such that:

prefixSum - previousPrefixSum = k

Rearranging:

previousPrefixSum = prefixSum - k

Therefore, whenever we encounter a prefix sum that has a previous occurrence of prefixSum - k, we have found a subarray with sum k.

This is where unordered_map helps us.

Algorithm

1. Initialize prefixSum = 0 and count = 0.
2. Create an unordered_map to store prefix sums and their frequencies.
3. Insert mp[0] = 1 to handle subarrays starting from index 0.
4. Traverse the array and update the prefix sum.
5. Check whether prefixSum - k exists in the map.
6. If it exists, add its frequency to the answer.
7. Store the current prefix sum frequency.

Dry Run

Input:

nums = [1, 1, 1]
k = 2

Initially:

mp = {0: 1}
prefixSum = 0
count = 0

ElementPrefix SumprefixSum — kCount11–1012011312

Final Answer = 2.

Why Do We Initialize mp[0] = 1?

This is one of the most important concepts in this problem.

Consider:

nums = [2, 3]
k = 5

When we reach the second element:

prefixSum = 5

Now:

prefixSum - k = 5 - 5 = 0

If we initialize mp[0] = 1, we can count the entire subarray [2, 3].

Without this initialization, we would miss subarrays starting from index 0.

Time Complexity: O(n) average.

Space Complexity: O(n).

The key learning is that a hash map can store the frequency of previous prefix sums, allowing us to count subarrays efficiently.

6. LeetCode 438 — Find All Anagrams in a String

Problem: Given two strings s and p, return all the starting indices of p’s anagrams in s.

Problem Link

Example

Input:
s = "cbaebabacd"
p = "abc"

Output: [0, 6]

Explanation:

The substrings starting at indices 0 and 6 are:

• cba
• bac

Both are anagrams of abc.

Approach: Sliding Window + Frequency Array

An anagram contains exactly the same characters with the same frequencies, but possibly in a different order.

For example:

abc and bca

Both contain:

a = 1
b = 1
c = 1

We can use a frequency array to store character counts.

Since the problem contains lowercase English letters, we only need an array of size 26.

Step 1: Calculate the frequency of characters in p.

Step 2: Create a window of size p.length() in string s.

Step 3: Calculate the frequency of characters inside the current window.

Step 4: Compare both frequency arrays.

If they are equal, store the starting index.

Step 5: Slide the window by removing the outgoing character and adding the incoming character.

Dry Run

s = "cbaebabacd"
p = "abc"

The window size is 3.

WindowAnagram?Starting IndexcbaYes0baeNo-aebNo-ebaNo-babNo-abaNo-bacYes6acdNo-

Answer:

[0, 6]

Time Complexity: O(n + m + 26), effectively O(n + m).

Space Complexity: O(26), effectively O(1).

Important Learning

Initially, I had also considered generating every substring and sorting it to check whether it was an anagram.

However, that approach performs unnecessary sorting operations.

Using a frequency array with a sliding window avoids repeatedly processing the entire substring.

This problem demonstrates how hashing-style frequency counting and sliding window can work together.

7. LeetCode 146 — LRU Cache

Problem: Design a data structure that follows the Least Recently Used (LRU) cache policy.

Problem Link

This problem is slightly different from the previous three.

Here, we need to design a data structure rather than simply solve an array or string problem.

What Is an LRU Cache?

LRU stands for Least Recently Used.

It is a cache replacement policy in which the least recently accessed element is removed when the cache reaches its capacity and a new element needs to be inserted.

Consider a cache with capacity 2.

Operations:

put(1, 10)
put(2, 20)
get(1)
put(3, 30)

Let’s understand what happens.

1. Insert key 1.
2. Insert key 2.
3. Access key 1, making it the most recently used.
4. Insert key 3.

Now the cache is full.

Key 2 is removed because it is the least recently used.

The remaining cache contains keys 1 and 3.

Which Data Structures Do We Need?

To implement an LRU Cache efficiently, we combine two data structures:

1. unordered_map

Used to find a key quickly.

Average lookup time: O(1).

2. Doubly Linked List

Used to maintain the order of recently accessed elements.

A doubly linked list allows us to remove and move a node in O(1) time when we already have its address.

We maintain:

• Most recently used element at the front.
• Least recently used element at the back.

Why Not Use Only unordered_map?

An unordered_map provides fast searching, but it does not maintain the order in which elements were recently accessed.

Therefore, we need a doubly linked list to track usage order.

Understanding the Operations

get(key)

• Search for the key in unordered_map.
• If it doesn’t exist, return -1.
• Otherwise, move the node to the front.
• Return its value.

put(key, value)

• If the key already exists, update its value and move it to the front.
• Otherwise, check whether the cache is full.
• If full, remove the last node from the linked list and its key from the map.
• Insert the new node at the front.

Time Complexity

Operation Complexity

get() O(1)

averageput() O(1)

averageDeletenode O(1)

Insertnode O(1)

Space Complexity: O(capacity).

Important Learning

This problem demonstrates something important about DSA:

Sometimes, a single data structure is not enough to achieve the required time complexity.

By combining an unordered_map and a doubly linked list, we can achieve average O(1) time for both get and put operations.

This is one of the most useful applications of hashing in system design and real-world caching mechanisms.

8. What I Learned From These Four Problems

After revising hashing and solving these problems, I understood that hashing is not limited to simply checking whether an element exists.

It can be combined with other patterns to solve more complex problems.

Here are the major concepts I learned:

ProblemMain ConceptData StructureLC 128Consecutive Sequenceunordered_setLC 560Prefix Sum + Frequencyunordered_mapLC 438Sliding Window + Frequency CountingFrequency ArrayLC 146LRU Cacheunordered_map + Doubly Linked List

Some important takeaways:

1. Hashing: Provides efficient average-case searching, insertion, and deletion.
2. unordered_map: Useful for storing frequencies and key-value relationships.
3. unordered_set: Useful for maintaining unique elements and checking existence.
4. Prefix Sum + Hash Map: Helps solve subarray sum problems, especially when negative numbers are present.
5. Sliding Window + Frequency Counting: Helps solve anagram and character-frequency problems.
6. Hash Map + Doubly Linked List: Helps build efficient data structures such as LRU Cache.

9. Final Thoughts

Hashing is one of the most important concepts in DSA because it helps reduce unnecessary searching and makes many solutions more efficient.

Before this revision, I had already used maps and sets in multiple problems, but I wanted to understand their differences, internal working, and practical applications more clearly.

These four problems helped me connect hashing with different DSA patterns, including prefix sums, sliding windows, and linked lists.

My biggest takeaway is that learning a data structure is not just about knowing its functions. It is about understanding when and how to combine it with other data structures to solve problems efficiently.

👋 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

#Hashing #Leetcode #DSA #CodingInterview #EnjoyProblems

Today, I solved LeetCode 871 — Minimum Number of Refueling Stops, and it helped me understand how Greedy Algorithms and Heaps work together to solve an optimization problem.

At first, the problem looks like a simple journey-planning question. However, the real challenge is deciding when to refuel and which station’s fuel to choose so that we reach our destination with the minimum number of stops.

Let’s break down the intuition, algorithm, and implementation.

1. Understanding the Problem

Imagine that you are driving a car toward a destination.

You are given:

• target: The distance to your destination.
• startFuel: The amount of fuel available initially.
• stations: An array where each station contains its position and the amount of fuel it provides.

Your task is to reach the destination using the minimum possible number of refueling stops.

For example:

target = 100;
startFuel = 10;

stations = {
    {10, 60},
    {20, 30},
    {30, 30},
    {60, 40}
};

Each pair represents {position, fuel}.

For example, {10, 60} means a petrol station is located 10 units from the starting point and provides 60 units of fuel.

The answer is 2, because we can reach the destination with only two refueling stops.

2. Real-Life Analogy: Planning a Long Road Trip

Imagine you are driving a car with limited fuel.

You encounter several petrol stations along the highway. Some provide 20 litres, some provide 40 litres, and others provide 60 litres.

Would you stop at every petrol station?

Not necessarily!

Instead, you can keep moving while your current fuel is sufficient. If you later discover that you cannot reach the next destination, you can use the fuel available from a station you have already passed.

The smart strategy is to choose the station that provides the maximum available fuel.

This is the intuition behind combining Greedy and Max Heap.

3. Why Do We Need a Greedy Algorithm?

A Greedy Algorithm makes a locally optimal choice at each step in the hope of achieving a globally optimal solution.

In this problem, we want to minimize the number of refueling stops.

Whenever our fuel becomes insufficient, we choose the largest available fuel amount from the stations we have already reached.

Why?

Because a larger fuel amount can help us travel farther with the same number of stops.

We do not refuel unnecessarily at every station. Instead, we postpone the decision until additional fuel is needed.

Important: We only consider stations that we can reach. We cannot use fuel from a station that is still ahead of us.

4. Why Do We Need a Max Heap?

A Max Heap allows us to retrieve the largest available fuel amount efficiently.

In C++, the default priority_queue<int> is a Max Heap.

priority_queue<int> pq;

pq.push(60);
pq.push(30);
pq.push(40);

Now:

pq.top();  // 60

The largest value is always available at the top.

The key operations are:

• pq.push(fuel): Add fuel from a reachable station.
• pq.top(): Access the largest available fuel amount.
• pq.pop(): Remove that amount after using it.

Both insertion and removal take (O(\log n)) time, while accessing the top takes (O(1)) time.

The heap helps us avoid repeatedly searching through all previously reached stations to find the one with the most fuel.

Understanding the Important Variables

fuel — Current available fuel

It tracks how much fuel remains after travelling to the current position.

prev — Previous position

It helps calculate the distance travelled between consecutive stations.

pq — Max Heap

It stores the fuel amounts of stations we have already reached but have not yet selected for refueling.

ans — Number of refueling stops

It increases only when we actually take fuel from the heap.

The Most Important Logic

Step 1: Calculate the distance

fuel -= (pos - prev);

Suppose the previous position is 20 and the next position is 60.

The distance travelled is:

[
60–20 = 40
]

If we had 50 units of fuel, we would have 10 remaining.

Step 2: Check whether the fuel is negative

while (fuel < 0)

Negative fuel means that our current fuel is insufficient to reach the current position.

We must refuel before proceeding.

Step 3: Choose the maximum available fuel

if (pq.empty()) {
    return -1;
}

fuel += pq.top();
pq.pop();
ans++;

If the heap is empty, no previously reached station can provide additional fuel, so the destination is unreachable.

Otherwise, we take the maximum available fuel, remove it from the heap, and increment our stop count.

The while loop is important because we may need more than one previously available station's fuel to reach the current position.

Step 4: Add the current station

if (i < stations.size()) {
    pq.push(stations[i][1]);
}

Once we reach a station, its fuel becomes available for future use.

Notice that adding fuel to the heap does not mean that we have refueled. It only means that the station is now an available option.

We count a stop only when we take its fuel from the heap.

Dry Run

Consider the same example:

target = 100;
startFuel = 10;

stations = {
    {10, 60},
    {20, 30},
    {30, 30},
    {60, 40}
};

At the destination, the remaining fuel is:

[
10–40 + 40 = 10
]

We successfully reach the destination with 2 refueling stops.

9. Time and Space Complexity

Let (n) be the number of fuel stations.

Time Complexity: (O(n\log n))

Each station’s fuel is inserted into the heap at most once and removed at most once. Each heap insertion or removal takes (O(\log n)) time.

Space Complexity: (O(n))

In the worst case, the heap can contain fuel amounts from all (n) stations.

10. What I Learned Today

Solving this problem strengthened my understanding of three important ideas:

1. Greedy: Make a strategic choice when additional fuel is required.
2. Max Heap: Efficiently select the largest available fuel amount.
3. Delayed decision-making: Keep available options in the heap and commit to a refueling stop only when necessary.

The most important lesson is that a heap is not just a data structure for finding maximum or minimum values. When combined with a greedy strategy, it can help solve optimization problems efficiently.

Conclusion

LeetCode 871 was a great exercise in understanding how two concepts can work together to produce an efficient solution.

My key takeaway:

Greedy decides when a choice is necessary, and the Max Heap helps us choose the best available option.

👋 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

#HeapWithGreedy #RefuelingStops #DSA #CodingInterview #EnjoyProblems

While solving LeetCode problems, I realized something interesting: a heap is not just a data structure for finding the largest or smallest element. It becomes much more powerful when we use it to solve a specific problem efficiently.

Recently, I solved two important heap problems:

• LeetCode 295 — Find Median from Data Stream
• LeetCode 23 — Merge k Sorted Lists

At first, these problems look different. One asks us to find a median as numbers arrive, while the other asks us to merge multiple sorted linked lists.

However, both problems share the same fundamental idea:

Keep the most useful elements accessible so that we do not have to search through all the data repeatedly.

Let’s understand both problems through real-life analogies, C++ code, and the reasoning behind the heap operations.

1. Heap Fundamentals: Max Heap vs. Min Heap

Before solving the problems, let’s quickly revise two types of heaps.

Max Heap

In a Max Heap, the largest element is always available at the top.

priority_queue<int> maxHeap;

For example, if we insert 10, 4, 20, 7, then:

Top = 20

We can access the largest element in O(1) time.

Min Heap

In a Min Heap, the smallest element is always available at the top.

priority_queue<int, vector<int>, greater<int>> minHeap;

For the same numbers:

Top = 4

We can access the smallest element in O(1) time.

The important difference is not how we insert numbers, but which element we can access immediately.

This distinction becomes especially useful in the following two problems.

2. LeetCode 295 — Find Median from Data Stream

Problem: Design a data structure that supports adding numbers one at a time and finding the median of all numbers added so far.

Real-Life Analogy: Dividing a Classroom into Two Groups

Imagine a classroom where students arrive one by one, and we need to find the middle height of all students after every arrival.

We could sort all students every time someone new arrives. However, repeatedly sorting the entire collection is inefficient.

Instead, let’s divide the students into two groups:

• Left group: The shorter half of the students.
• Right group: The taller half of the students.

We only need two students to find the middle point:

• The tallest student in the left group.
• The shortest student in the right group.

This is exactly where using a Max Heap and a Min Heap together becomes powerful.

Why Do We Need Both Max Heap and Min Heap?

We use:

priority_queue<int> left;
priority_queue<int, vector<int>, greater<int>> right;

The left heap is a Max Heap that stores the smaller half of the numbers.

The right heap is a Min Heap that stores the larger half of the numbers.

Conceptually:

LEFT HALF                 RIGHT HALF

         Max Heap                    Min Heap

       Largest of left             Smallest of right
              |                           |
            left.top()                 right.top()

The two heaps maintain two important rules:

1. Every element in left must be less than or equal to every element in right.
2. The size of left must equal the size of right, or exceed it by exactly one.

These rules ensure that the middle element or middle two elements are always accessible.

Understanding addNum()

Step 1: Insert into the left heap

left.push(num);

We initially insert the new number into the Max Heap.

Step 2: Move the largest left element into the right heap

right.push(left.top());
left.pop();

Because left is a Max Heap, its top is the largest element in the left group.

Moving this element to the Min Heap helps maintain the ordering between the two groups.

Step 3: Balance the heaps

if (right.size() > left.size()) {
    left.push(right.top());
    right.pop();
}

If the right heap becomes larger than the left heap, we move the smallest element from the right heap back to the left.

After balancing, the left heap contains either the same number of elements as the right heap or exactly one more.

Understanding findMedian()

There are two possible situations.

Case 1: The left heap has one extra element.

The total number of elements is odd, so the median is:

return left.top();

Case 2: Both heaps have equal sizes.

The total number of elements is even, so the median is the average of the two middle elements:

return ((double)left.top() + right.top()) / 2.0;

For example, if the numbers are 1, 3, 5, 7, the left heap's top is 3 and the right heap's top is 5.

Therefore:

Median = (3 + 5) / 2 = 4

Complexity Analysis

OperationTime ComplexityaddNum()O(log n)findMedian()O(1)SpaceO(n)

Key takeaway: Using a Max Heap and a Min Heap together allows us to maintain the middle of a continuously changing dataset without sorting all the numbers every time.

3. LeetCode 23 — Merge k Sorted Lists

Problem: Given an array of k sorted linked lists, merge them into one sorted linked list.

Real-Life Analogy: Merging Multiple Sorted Queues

Imagine three queues at a ticket counter. Each queue is already arranged in increasing order of ticket numbers.

Queue 1: 1 → 4 → 7
Queue 2: 2 → 5 → 8
Queue 3: 3 → 6 → 9

We need to combine these queues into one sorted sequence.

We could examine every remaining element across all queues repeatedly to find the smallest one. However, that would require unnecessary comparisons.

Instead, let’s compare only the first available element from each queue.

Initially, these elements are:

Queue 1 → 1
Queue 2 → 2
Queue 3 → 3

The smallest element is 1. We take it, add it to the merged list, and then consider the next element from Queue 1, which is 4.

Now our available candidates are 2, 3, 4.

We repeat this process until all lists are merged.

This is exactly how a Min Heap helps us solve LC 23 efficiently.

Why Do We Need a Min Heap?

We only need the smallest available node across the lists at each step.

Therefore, we use:

priority_queue<ListNode*, vector<ListNode*>, Compare> pq;

Here:

• ListNode* stores pointers to linked-list nodes.
• vector<ListNode*> provides the heap's underlying storage.
• Compare makes the smallest node value appear at the top.

Unlike LC 295, we don’t need both a Max Heap and a Min Heap here. A single Min Heap is sufficient because our goal is always to find the smallest available node.

Custom Comparator Explained

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

Suppose:

a->val = 8
b->val = 3

The comparison:

return a->val > b->val;

evaluates to true.

This gives the smaller value higher priority in our Min Heap, so the node containing 3 comes before the node containing 8.

The comparator determines the heap’s ordering based on node values, rather than pointer addresses.

Understanding the Algorithm

Step 1: Insert the first node of every list

for (auto list : lists) {
    if (list != nullptr) {
        pq.push(list);
    }
}

Notice something important: we do not insert every node into the heap at the beginning.

We insert only the first node of each non-empty list because it is the smallest available element in that list.

Step 2: Extract the smallest node

ListNode* node = pq.top();
pq.pop();

The Min Heap gives us the smallest available node.

Step 3: Connect it to the merged list

tail->next = node;
tail = tail->next;

We connect the existing node to our result.

We are reusing the linked-list nodes, not creating a new node for every value.

The dummy node provides a convenient starting point, and tail tracks the last node in the merged list.

Step 4: Insert the next node from the same list

if (node->next != nullptr) {
    pq.push(node->next);
}

After selecting a node, we insert its next node into the heap if one exists.

We repeat the process until the heap becomes empty.

Complexity Analysis

Let N be the total number of nodes across all lists, and k be the number of lists.

OperationComplexityInitial heap constructionO(k log k)Processing all nodesO(N log k)Overall timeO(N log k)Auxiliary heap spaceO(k)

The merged list reuses the original nodes, so the algorithm does not need an additional O(N) collection of output nodes.

Key takeaway: The Min Heap lets us select the smallest available node efficiently, while linked-list pointers allow us to build the final sorted list without recreating every node.

Final Takeaways

Solving these two problems helped me understand that mastering heaps is not just about knowing priority_queue syntax.

It is about identifying the element that matters at each step and keeping it accessible.

• LC 295: A Max Heap and a Min Heap work together to maintain the median efficiently.
• LC 23: A Min Heap works with linked-list pointers to merge multiple sorted lists efficiently.
• Custom comparators: They let us control how complex elements, such as linked-list nodes, are prioritized.
• The bigger pattern: Use a heap when repeatedly finding the next smallest, largest, or otherwise highest-priority element would be expensive with a simple unsorted collection.

These problems demonstrate two valuable applications of heaps: maintaining a moving boundary in a data stream and efficiently merging multiple sorted sequences.

👋 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

#Median #SortedList #Heap #DSA #CodingInterview #EnjoyProblems

• LC 692 — Top K Frequent Words
• LC 347 — Top K Frequent Elements
• LC 973 — K Closest Points to Origin

All three use heaps, but each problem teaches a different way to prioritize elements.

Let’s understand them with real-life analogies, C++ code, and the patterns behind them.

1. LC 692 — Top K Frequent Words

Pattern: Hashing + Max Heap + Custom Comparato

Understanding the problem

Given an array of words and an integer k, return the k most frequent words.

If two words have the same frequency, the lexicographically smaller word must come first.

Example:

words = {"i", "love", "leetcode", "i", "love", "coding"};
k = 2;

Output:

{"i", "love"}

Both i and love appear twice. Since i comes before love alphabetically, it ranks first.

Real-life analogy: A popularity ranking system

Imagine a teacher wants to identify the two most popular students based on votes.

• More votes mean a higher rank.
• If two students receive the same votes, their names are ranked alphabetically.

We need a system that follows both rules automatically. That’s exactly what a heap with a custom comparator can do.

Step 1: Count word frequencies

map<string, int> mp;

for (auto word : words) {
    mp[word]++;
}

The map stores each unique word and its frequency.

WordFrequencycoding1i2leetcode1love2

Step 2: Understand the custom comparator

We store each entry as:

{frequency, word}

The comparator must enforce two rules:

1. Higher frequency gets higher priority.
2. If frequencies are equal, the alphabetically smaller word gets higher priority.

struct Compare {
    bool operator()(const pair<int, string>& a,
                    const pair<int, string>& b) {
        if (a.first == b.first) {
            return a.second > b.second;
        }

        return a.first < b.first;
    }
};

How does it work?

Case A: Different frequencies

a = {2, "apple"};
b = {5, "banana"};

return a.first < b.first;  // true

The lower-frequency entry has lower priority, so the word with frequency 5 ranks higher.

Case B: Equal frequencies

a = {3, "mango"};
b = {3, "apple"};

return a.second > b.second;  // true

mango comes after apple alphabetically, so mango gets lower priority.

Remember: in a C++ priority_queue, returning true means the first entry has lower priority than the second. This is why the comparison rules may initially feel opposite to what we expect.

Step 3: Create the heap

priority_queue<
    pair<int, string>,
    vector<pair<int, string>>,
    Compare
> pq;

The three template arguments mean:

• pair<int, string>: what we store.
• vector<pair<int, string>>: the underlying container.
• Compare: the rule that decides priority.

Now insert every frequency-word pair:

for (auto it : mp) {
    pq.push({it.second, it.first});
}

Extract the top k words:

vector<string> ans;

for (int i = 0; i < k; i++) {
    ans.push_back(pq.top().second);
    pq.pop();
}

return ans;

The heap returns i first and love second.

Complexity: With n total words and m unique words, the time complexity is O(n log m + m log m + k log m), and auxiliary space is O(m).

Key takeaway

LC 692 taught me that a heap is not just about finding the largest or smallest element. A custom comparator lets us define exactly what “highest priority” means.

2. LC 347 — Top K Frequent Elements

Pattern: Hashing + Max Heap

Understanding the problem

Given an integer array, return the k most frequent elements.

Example:

nums = {1, 1, 1, 2, 2, 3};
k = 2;

Output:

{1, 2}

Real-life analogy: A product sales leaderboard

Imagine an online store wants to find its two best-selling products.

• Product 1 sold 3 units.
• Product 2 sold 2 units.
• Product 3 sold 1 unit.

Instead of manually sorting every product, we can count sales and use a max heap to retrieve the highest-frequency products first.

How it works

Step 1: Count each number’s frequency.

Step 2: Insert {frequency, element} into the max heap.

Step 3: Pop the heap k times and collect each element.

Because the default priority_queue<pair<int,int>> compares the first value first, the highest frequency appears at the top. If frequencies tie, the larger integer appears first, which is acceptable because LC 347 does not require a particular output order.

Complexity: With m unique numbers, the time complexity is O(n log m + m log m + k log m), with O(m) auxiliary space.

Key takeaway

LC 347 helped me understand the classic frequency counting + max heap pattern.

3. LC 973 — K Closest Points to Origin

Pattern: Distance Calculation + Min Heap

Understanding the problem

Given points on a 2D plane, return the k points closest to the origin (0,0).

Example:

points = {{1,3}, {-2,2}, {5,8}, {0,1}};
k = 2;

Output can be:

{{0,1}, {-2,2}}

Real-life analogy: Finding the nearest delivery locations

Imagine a delivery service operating from a warehouse at (0,0).

There are many delivery locations, and the service needs to identify the two closest ones.

We calculate each location’s distance from the warehouse and use a min heap to retrieve the closest locations first.

Step 1: Calculate squared distance

The Euclidean distance is:

[
d=\sqrt{x²+y²}
]

For comparison, we can use squared distance instead:

[
d²=x²+y²
]

The square root is unnecessary because squaring preserves the order of nonnegative distances.

How it works

Step 1: Calculate the squared distance of every point.

Step 2: Store {distance, index} in a min heap.

Step 3: Extract the smallest k distances and use their indices to retrieve the original points.

The greater<pair<int,int>> comparator creates a min heap. The smallest distance appears at the top.

Complexity: For n points, inserting all points and extracting k takes O(n log n + k log n) time and O(n) auxiliary space.

Key takeaway

LC 973 taught me that heaps can prioritize elements based on a calculated property, not just their original values.

4. What these three problems taught me

ProblemCore patternPriority rule

LC 692Frequency + Custom HeapHighest frequency; alphabetical tie-break

LC 347Frequency + Max HeapHighest frequency

LC 973Distance + Min HeapSmallest distance

5. Final revision notes

• Max heap: By default, the largest value comes first.
• Min heap: Use greater<T> to prioritize the smallest value.
• Frequency problems: Count occurrences first, then prioritize by frequency.
• Custom comparator: Useful when the problem has multiple ranking rules.
• Distance problems: Calculate the relevant distance or score, then use a heap to retrieve the best candidates.
• Optimization: When k is much smaller than the number of unique elements, a heap limited to size k can reduce the heap-related work to O(m log k) after frequency counting.

Solving these three problems helped me understand that the most important part of a heap problem is not just choosing a min heap or max heap — it’s deciding what priority each element should have.

👋 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

#TopK #Heap #Leetcode #DSA #CodingInterview #EnjoyProblems

Today, I started revising the Heap data structure in DSA. I revised the fundamentals and solved three important LeetCode problems:

Last Stone Weight (1046),

Kth Largest Element in a Stream (703),

Kth Largest Element in an Array (215).

One of the best moments was solving LeetCode 215 in under 5 minutes during revision. It reminded me how understanding a pattern makes problem-solving much faster.

In this article, I’ll explain Heap fundamentals, followed by the approach and key learnings from each problem.

1. What Is a Heap?

A Heap is a Complete Binary Tree that follows a specific ordering property, called the Heap Property.

A Complete Binary Tree is a tree in which every level is completely filled except possibly the last level, which is filled from left to right.

There are two main types of heaps.

Min Heap

In a Min Heap, the parent node is always smaller than or equal to its children.

Example:

        10
       /  \
      20   15
     / \
    30  40

The smallest element, 10, is at the root.

Max Heap

In a Max Heap, the parent node is always greater than or equal to its children.

Example:

        50
       /  \
      30   40
     / \
    10  20

The largest element, 50, is at the root.

Important: A Heap is not a completely sorted tree. Only the parent-child ordering property is guaranteed.

2. Heap in C++ Using priority_queue

C++ provides a built-in priority_queue that makes heap operations convenient.

Max Heap

priority_queue<int> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top();  // 30

By default, priority_queue implements a Max Heap, so the largest element is available at the top.

Min Heap

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top();  // 10

Using greater<int> creates a Min Heap, so the smallest element is available at the top.

Time Complexity

OperationComplexityInsert (push)O(log n)Access top (top)O(1)Remove top (pop)O(log n)

Heaps are especially useful when we repeatedly need the smallest or largest element without sorting the entire collection.

3. LeetCode 1046 — Last Stone Weight

Approach: Max Heap

We are given stones with different weights. In each operation, we select the two heaviest stones and smash them together.

• If both stones have the same weight, both are destroyed.
• If their weights differ, the remaining stone has the difference in weight.
• We repeat until at most one stone remains.

Since we always need the two heaviest stones, a Max Heap is the perfect choice.

Real-Life Analogy: A Boxing Match Between the Two Strongest Players

Imagine a competition in which players have different strength levels.

In every round, the two strongest players compete:

• If both have equal strength, both are eliminated.
• If one is stronger, the weaker player is eliminated, and the stronger player loses strength equal to the weaker player’s strength.
• The remaining player returns to the competition.

We repeat this process until at most one player remains.

This is exactly the idea behind Last Stone Weight.

Since we always need the two heaviest stones, a Max Heap is the right choice.

Example

stones = [2, 7, 4, 1, 8, 1]

Initially, the heaviest stones are 8 and 7.

Round 1:

8 vs 7 → Remaining weight = 1

The remaining stone weighs 1.

Now the stones effectively become:

[2, 4, 1, 1, 1]

Round 2:

4 vs 2 → Remaining weight = 2

Remaining stones:

[2, 1, 1, 1]

Round 3:

2 vs 1 → Remaining weight = 1

Remaining stones:

[1, 1, 1]

Round 4:

1 vs 1 → Both destroyed

One stone of weight 1 remains.

Final Answer: 1

Dry Run

Suppose:

stones = [2, 7, 4, 1, 8, 1]

The two heaviest stones are selected in each round.

OperationResult8 and 714 and 222 and 111 and 1Both destroyed

The remaining stone has weight 1.

Complexity

• Time: O(n log n)
• Space: O(n)

Key learning: When a problem repeatedly asks for the maximum element, think of a Max Heap.

4. LeetCode 703 — Kth Largest Element in a Stream

Approach: Min Heap of Size K

We need to find the Kth largest element as new numbers arrive in a stream.

Instead of storing every element in a sorted collection, we maintain a Min Heap containing only the K largest elements seen so far.

The smallest element among those K elements will be the Kth largest overall.

Real-Life Analogy: Maintaining the Top 3 Students in a School

Imagine a school where students keep receiving new exam scores.

You don’t need the complete ranking of every student. You only need to know the third-highest score at any moment.

Suppose the scores arriving are:

4, 5, 8, 2

And we need the third-largest score, so k = 3.

The three highest scores are:

4, 5, 8

The third-largest score is 4.

Now a new student arrives with a score of 10.

The three highest scores become:

5, 8, 10

The third-largest score is now 5.

Notice that we don’t need to maintain every score in sorted order. We only need the top three.

Why Use a Min Heap?

We maintain a Min Heap of size k.

Think of it as a leaderboard that can hold only three students.

Whenever a new score arrives:

1. Add the score to the heap.
2. If more than three scores are present, remove the smallest.
3. The top of the heap is the third-largest score.

Why Min Heap? Because the smallest score among the top three is exactly the third-largest overall.

Dry Run

Suppose k = 3 and the stream is:

[4, 5, 8, 2]

After processing these numbers, the three largest elements are 4, 5, 8.

The Min Heap’s top is 4, which is the third-largest element.

Now, a new value 10 arrives.

Before: [4, 5, 8]
Add: 10
Remove smallest: 4

After: [5, 8, 10]

The third-largest element is now 5.

Complexity

• Initialization: O(n log k) with repeated insertion.
• Each add() operation: O(log k)
• Auxiliary space: O(k)

Key learning: When the input keeps changing and you need the Kth largest element, maintain a Min Heap of size K.

5. LeetCode 215 — Kth Largest Element in an Array

Approach: Min Heap of Size K

This problem looks similar to LeetCode 703, but there is an important difference: here, the entire array is available at once.

We need to return the Kth largest element without necessarily sorting the entire array.

The same pattern works:

1. Insert each number into a Min Heap.
2. If the heap size exceeds K, remove the smallest element.
3. After processing every number, the heap contains the K largest elements.
4. The top element is the Kth largest.

Real-Life Analogy: Finding the Second-Highest Bid in an Auction

Imagine an auction with bids:

[3, 2, 1, 5, 6, 4]

You need to find the second-highest bid.

One approach would be to sort every bid and then select the second element.

But do you really need to sort every bid if you only care about the top two?

No!

We can maintain just the two highest bids using a Min Heap of size 2.

Step-by-Step Example

Here, k = 2.

Initially, the heap is empty.

Bid 1: 3

Heap: [3]

Bid 2: 2

Heap: [2, 3]

We have the two largest bids so far. The smallest of them is 2.

Bid 3: 1

Insert 1 → [1, 3, 2]
Remove the smallest → [2, 3]

The bid 1 is too small to remain in the top two.

Bid 4: 5

Insert 5 → [2, 3, 5]
Remove the smallest → [3, 5]

Bid 5: 6

Insert 6 → [3, 5, 6]
Remove the smallest → [5, 6]

Bid 6: 4

Insert 4 → [4, 5, 6]
Remove the smallest → [5, 6]

The final two largest bids are 5 and 6.

The smallest of these two is 5, so the second-largest bid is 5.

Final Answer: 5

Complexity

• Time: O(n log k)
• Auxiliary space: O(k)

My Revision Milestone

I solved this problem in under 5 minutes during my Heap revision.

For me, the important part wasn’t just writing the code quickly. It was recognizing the pattern immediately:

Kth Largest → Min Heap of Size K.

When the pattern becomes familiar, the solution becomes much more straightforward.

Quick Revision Rules

• Need the maximum repeatedly? Use a Max Heap.
• Need the minimum repeatedly? Use a Min Heap.
• Need the K largest elements? Use a Min Heap of size K.
• Need the K smallest elements? Use a Max Heap of size K.
• Need to process incoming values? Consider maintaining a bounded heap.

Conclusion

Revising Heap today reinforced an important lesson: DSA is not just about memorizing solutions; it’s about recognizing patterns.

Starting with Heap fundamentals and applying them to three LeetCode problems helped me connect the concepts with real interview-style questions.

I’ll continue practicing more Heap patterns, including Top K Frequent Elements, K Closest Points, Merge K Sorted Lists, and Median from Data Stream.

One step at a time, one pattern at a time. 🚀

👋 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

#BasicsOfHeap #DSA #CodingInterview #EnjoyProblems

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.

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

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

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

In this phase, I solved four problems:

• LeetCode 881 — Boats to Save People
• LeetCode 1029 — Two City Scheduling
• LeetCode 406 — Queue Reconstruction by Height
• LeetCode 646 — Maximum Length of Pair Chain

These problems may look completely different, but they teach four very useful Greedy patterns:

Sort + Two Pointers
Sort by Difference
Greedy Reconstruction
Earliest Ending / Interval Scheduling

The main goal of this phase was not just to solve these four problems, but to understand why a particular greedy choice works.

1. LeetCode 881 — Boats to Save People

Problem

We are given an array people, where people[i] represents the weight of a person.

We also have a boat with a maximum weight limit.

Each boat can carry at most two people.

We need to find the minimum number of boats required to rescue everyone.

Example

people = [3, 2, 2, 1]
limit = 3

We can arrange them as:

1 + 2 = 3
3
2

So the answer is:

3 boats

The Greedy Idea

At first, we might try many combinations.

But there is a simple observation:

If the heaviest person can go with the lightest person, we should pair them.

Why?

Because the heaviest person is the hardest person to accommodate.

So we sort the array:

[1, 2, 2, 3]

Then use two pointers:

left  → lightest
right → heaviest

Now check:

people[left] + people[right]

If their total weight is within the limit:

left + right <= limit

we put both in one boat.

Otherwise, the heaviest person must go alone.

Example

[1, 2, 2, 3]
limit = 3

Step 1

1 + 3 = 4

Too heavy.

So 3 must go alone.

Boat 1 → [3]

Move right.

Step 2

Now:

1 + 2 = 3

They can share.

Boat 2 → [1,2]

Move both pointers.

Step 3

Remaining:

[2]

So:

Boat 3 → [2]

Answer:

3

Pattern

Sort + Two Pointers

The general template is:

Sort
 ↓
left = 0
right = n - 1
 ↓
Check smallest + largest
 ↓
If possible → use them together
Otherwise → largest goes alone

Key Greedy Decision

Always try to accommodate the heaviest person with the lightest person.

This problem is a good example of how sorting + two pointers can turn a complicated pairing problem into a simple greedy process.

2. LeetCode 1029 — Two City Scheduling

Problem

We have 2n people.

Every person can go to either:

• City A
• City B

Each person has a different cost for both cities.

We need to send exactly:

n people → City A
n people → City B

while minimizing the total cost.

Example

Suppose:

[10, 20]
[30, 200]
[400, 50]
[30, 20]

For each person:

Person 1 → A = 10,  B = 20
Person 2 → A = 30,  B = 200
Person 3 → A = 400, B = 50
Person 4 → A = 30,  B = 20

We need:

2 people → A
2 people → B

The Important Observation

Instead of looking at the costs separately, calculate:

A - B

For example:

Person 1:
10 - 20 = -10

Person 2:
30 - 200 = -170

Person 3:
400 - 50 = 350

Person 4:
30 - 20 = 10

Now the difference tells us something useful.

Negative difference

A - B < 0

means City A is cheaper.

Positive difference

A - B > 0

means City B is cheaper.

So we sort people based on this difference.

Why Does Sorting by Difference Work?

Suppose someone’s difference is:

-170

That means sending them to A instead of B saves a lot of money.

While someone with:

350

strongly prefers B.

Therefore, we want the people with the smallest differences to go to A.

And the people with the largest differences to go to B.

Pattern

Sort by Cost Difference

difference = costA - costB

Then:

First n people → City A
Remaining n people → City B

This works because the sorted difference tells us which assignment gives us the biggest advantage.

Key Lesson

This problem teaches an important Greedy technique:

Sometimes we should not sort using the original values.
We should sort using the difference between two choices.

Whenever a problem gives you:

Choice A → cost/value
Choice B → cost/value

you should think:

What happens if I choose A instead of B?

That difference can become the greedy criterion.

3. LeetCode 406 — Queue Reconstruction by Height

This problem is slightly different from the previous two.

Here, we don’t just select people.

We have to construct the final answer.

Problem

Each person is represented as:

[h, k]

where:

h = height
k = number of people in front of them who have height >= h

We need to reconstruct the queue.

Example

Suppose we have:

[7,0]
[4,4]
[7,1]
[5,0]
[6,1]
[5,2]

We need to arrange them so that every person’s k condition is satisfied.

At first, this looks difficult because inserting one person can affect the conditions of other people.

The Greedy Trick

We sort people by:

First:

Higher height first.

If heights are equal:

Smaller k first.

So:

[7,0]
[7,1]
[6,1]
[5,0]
[5,2]
[4,4]

Then we insert each person at index k.

Why Taller People First?

This is the most important part of the problem.

Suppose we have already placed taller people.

Now we insert a shorter person.

That shorter person cannot affect the k count of taller people, because the taller people only care about people who are at least as tall as themselves.

Therefore:

Place taller people first, then insert shorter people.

This makes the problem much easier.

Step-by-Step

Start:

[]

Insert:

[7,0]

Queue:

[7,0]

Next:

[7,1]

Insert at index 1:

[7,0] [7,1]

Next:

[6,1]

Insert at index 1:

[7,0] [6,1] [7,1]

Continue doing the same for every person.

The final queue becomes:

[5,0]
[7,0]
[5,2]
[6,1]
[4,4]
[7,1]

Pattern

Custom Sorting + Insertion

The general idea is:

Sort by a property
       ↓
Process important elements first
       ↓
Insert each element at its required position

The important observation is:

The larger elements should be fixed first because smaller elements cannot invalidate their conditions.

Key Lesson

This problem teaches a very useful Greedy concept:

Greedy Reconstruction

Sometimes the answer isn’t found by simply selecting elements.

Instead:

Choose the correct processing order
        ↓
Build the answer step-by-step

This pattern appears in many interview problems where we need to construct a valid arrangement.

4. LeetCode 646 — Maximum Length of Pair Chain

Now we come to another important Greedy pattern.

This problem is closely related to Interval Scheduling.

Problem

We are given pairs:

[a, b]

We can put pair [c,d] after [a,b] if:

b < c

We need to find the maximum number of pairs that can form a chain.

Example

pairs =
[[1,2],
 [2,3],
 [3,4]]

We can choose:

[1,2] → [3,4]

because:

2 < 3

So the answer is:

2

The Greedy Idea

Suppose we have two possible pairs:

[1,10]
[2,3]

Which one should we choose?

At first, [1,10] starts earlier.

But choosing it is bad because it ends at 10.

Choosing:

[2,3]

ends much earlier.

That leaves more space for future pairs.

Therefore:

Always prefer the pair that finishes earliest.

Example

Consider:

[1,2]
[2,3]
[3,4]
[5,6]

Sort by ending value:

[1,2]
[2,3]
[3,4]
[5,6]

Start with:

end = -∞

Choose:

[1,2]

Now:

end = 2
count = 1

Next:

[2,3]

Condition:

2 < 2

False.

So skip it.

Next:

[3,4]

2 < 3

True.

Choose it:

end = 4
count = 2

Next:

[5,6]

4 < 5

True.

Choose it:

count = 3

Answer:

3

Pattern

Earliest Ending

The general pattern is:

Sort by ending point
        ↓
Choose the pair that finishes earliest
        ↓
Skip overlapping pairs
        ↓
Continue

Why?

Because:

The earlier we finish, the more choices we have for the future.

This is the same fundamental idea used in the classic Activity Selection / Interval Scheduling problem.

🔥 How to Identify These Patterns in Interviews?

When you see a new Greedy problem, don’t immediately start coding.

First ask:

1. Can sorting simplify the problem?

If yes, try:

Sort → Greedy

2. Are we pairing smallest and largest elements?

Think:

Two Pointers

Like:

LC 881

3. Are there two choices with different costs?

Try calculating:

costA - costB

Like:

LC 1029

4. Do we need to construct an arrangement?

Think:

Sort → Process in the correct order → Insert

Like:

LC 406

5. Are we selecting non-overlapping intervals/pairs?

Think:

Sort by ending point

Like:

LC 646

🚀 Final Takeaway

The biggest lesson from Phase 4 was:

Greedy is about finding the right ordering and making a choice that leaves the best possible future.

The four problems taught me four different ways to do that:

LC 881
↓
Use two pointers to make the best pairing

LC 1029
↓
Use differences to compare choices

LC 406
↓
Construct the answer in a safe greedy order

LC 646
↓
Finish as early as possible to maximize future choices

So whenever I see a Greedy problem now, my first questions are:

Can I sort it?

What should I sort by?

What local choice gives me the best future?

Can I prove that this choice doesn't hurt the remaining options?

That mindset is much more important than memorizing individual Greedy solutions.

Problems Covered

🔹 LC 881 — Boats to Save People
🔹 LC 1029 — Two City Scheduling
🔹 LC 406 — Queue Reconstruction by Height
🔹 LC 646 — Maximum Length of Pair Chain

👋 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

#TwoPointers #Differences #GreedyReconstruction #Greedy Algorithms #DSA #CodingInterview #EnjoyProblems

• LC 55 — Jump Game
• LC 45 — Jump Game II
• LC 134 — Gas Station
• LC 763 — Partition Labels

At first, these problems look completely different.

One is about jumping, one is about minimum jumps, one is about a circular gas route, and one is about splitting a string.

But they share an important idea:

Instead of exploring every possibility, maintain the best boundary/reachable state and make a greedy decision when the current boundary is exhausted or becomes invalid.

This is the Reachability & Greedy Boundaries pattern.

🧠 What is Reachability & Greedy Boundaries?

In many greedy problems, we don’t need to know every possible path.

We only need to maintain something like:

• How far can I reach?
• What is the current valid range?
• Where can the next boundary be?
• When should I discard the current candidate?

The important thing is that we continuously maintain the best possible boundary.

For example:

Current Range
[0 ----------- farthest]
                  ↑
            best reachable point

As we process more elements, we expand this boundary.

If the current boundary becomes impossible or fully explored, we make a greedy decision.

1️⃣ LC 55 — Jump Game

Problem

You are given an array where:

nums[i] = maximum jump length from index i

You need to determine whether you can reach the last index.

Example:

nums = [2,3,1,1,4]

From index 0:

0 → 1 or 2

From index 1:

1 → 2, 3 or 4

So we can reach the last index.

Answer:

true

💡 Greedy Idea

We don’t need to try every jump.

We simply maintain:

farthest

which represents the farthest index we can currently reach.

farthest = max(farthest, i + nums[i]);

At every index:

Current index + maximum jump

gives us a possible new boundary.

Example:

[2, 3, 1, 1, 4]
 ↑
 i = 0

farthest = 0 + 2 = 2

At index 1:

farthest = max(2, 1 + 3)
         = 4

Now the last index is reachable.

Core Pattern

Maintain the farthest reachable position.

This is a reachability problem.

Complexity

Time:  O(n)
Space: O(1)

2️⃣ LC 45 — Jump Game II

LC 55 asks:

Can I reach the end?

LC 45 asks a harder question:

What is the minimum number of jumps required to reach the end?

Example:

nums = [2,3,1,1,4]

Answer:

2

Because:

0 → 1 → 4

💡 Greedy Idea — Reachable Range

Here we maintain two important boundaries:

currEnd
farthest

currEnd

The farthest position reachable using the current number of jumps.

farthest

The farthest position we can reach using one more jump from the current range.

Example:

[2, 3, 1, 1, 4]
 0  1  2  3  4

Initially:

currEnd = 0
farthest = 0
jump = 0

At index 0:

farthest = 2

We have reached the end of our current range:

i == currEnd

So we must take another jump:

jump = 1
currEnd = farthest

Now:

Current reachable range:

[0 ----- 2]

We explore indices 1 and 2.

At index 1:

1 + nums[1]
= 1 + 3
= 4

So:

farthest = 4

When we reach index 2:

i == currEnd

we take the second jump.

jump = 2
currEnd = 4

We reached the destination.

🔑 Important Insight

We don’t increment jump at every index.

We increment it only when:

i == currEnd

because that means:

“I have completely explored everything reachable with my current number of jumps. Now I need to use the next jump.”

Core Pattern

Current boundary
        ↓
Explore entire range
        ↓
Find farthest next boundary
        ↓
Take one greedy jump
        ↓
Repeat

Complexity

Time:  O(n)
Space: O(1)

3️⃣ LC 134 — Gas Station

This problem looks completely different.

You have:

gas[i]  → gas available at station i
cost[i] → gas required to reach next station

You need to find a starting station from which you can complete the circular route.

💡 Convert the Problem

Instead of thinking separately about gas and cost, calculate:

gas[i] - cost[i]

This represents the net gain/loss at station i.

Example:

gas  =  [2, 3, 4]
cost =  [3, 4, 2]

net  = [-1,-1,+2]

Now the problem becomes:

Can we choose a starting point
such that the running balance never becomes negative?

🔥 Greedy Boundary Idea

We maintain:

currGas

This represents the current balance from our selected starting point.

Whenever:

currGas < 0

our current starting point cannot work.

So we discard it and move the starting point:

start = i + 1;
currGas = 0;

We don’t go back and test every previous station.

That’s the greedy part.

Why Can We Skip Previous Candidates?

Suppose starting from:

start

we eventually reach index i and:

currGas < 0

Then the current starting point fails.

More importantly, the stations between start and i cannot become a valid starting point either, because the accumulated balance from those candidates to i will also be insufficient under the same prefix-boundary argument.

Therefore we can safely jump to:

i + 1

This eliminates unnecessary checking.

currGas vs totalGas

This was an important part of this problem.

currGas

Used for local feasibility:

Can my current starting point survive?

totalGas

Used for global feasibility:

Is there enough gas overall?

If:

totalGas < 0

then:

Total gas < Total cost

So completing the circuit is impossible from any starting point.

Core Pattern

Running balance
      ↓
If balance becomes negative
      ↓
Current candidate fails
      ↓
Move boundary to next candidate

This is another form of greedy boundary movement.

Complexity

Time:  O(n)
Space: O(1)

4️⃣ LC 763 — Partition Labels

This problem changes the type of boundary.

Instead of an array of jumps, now we are dealing with a string.

Problem

Split the string into as many parts as possible such that:

Every character appears in at most one partition.

Example:

s = "ababcc"

We can split:

"abab" | "cc"

But:

"aba" | "bcc"

is invalid because b appears in both parts.

💡 Greedy Idea — Last Occurrence Boundary

First, store the last occurrence of every character.

For example:

s = "ababcc"

a → 2
b → 3
c → 5

Now start from index 0.

Character:

'a'

Its last occurrence is:

2

So initially:

boundary = 2

But while processing the partition, we may encounter another character whose last occurrence lies farther away.

At index 1:

b → last occurrence = 3

So boundary becomes:

boundary = 3

Now the partition must extend to index 3.

We get:

"abab"

At index 3:

i == boundary

So we can safely close the partition.

Then start the next partition:

"cc"

Final answer:

[4, 2]

🔥 The Important Greedy Boundary

The boundary keeps expanding:

a → boundary = 2

b → boundary = 3

...

We only close the partition when:

currentIndex == boundary

Because at that point, every character seen inside the partition has its last occurrence inside the partition.

Therefore, no character needs to appear in the next partition.

🚀 The Pattern

Step 1 — Maintain the Best Boundary

Ask:

“What is the farthest / latest / valid boundary I can currently guarantee?”

Examples:

LC 55  → farthest reachable index
LC 45  → farthest next range
LC 134 → valid starting boundary
LC 763 → last occurrence boundary

Step 2 — Expand or Move the Boundary

As you process the input, update the boundary.

farthest = max(farthest, i + nums[i]);

or:

end = max(end, lastOccurrence[s[i] - 'a']);

or move the candidate:

start = i + 1;

Step 3 — Make a Greedy Decision at the Boundary

When the current range/boundary is exhausted:

LC 45  → take another jump
LC 763 → close the partition

When the current candidate becomes invalid:

LC 134 → discard candidate

🎯 What I Learned

The biggest lesson from these problems is:

Greedy is often about maintaining the right boundary rather than exploring every possibility.

Instead of:

Try everything
    ↓
Compare everything
    ↓
Choose best

we try to maintain:

Best current state
       ↓
Expand boundary
       ↓
Detect when decision is forced
       ↓
Make greedy decision

That is what makes these solutions efficient.

📌 Problems Covered

LC 55 — Jump Game

Pattern: Farthest Reachability

LC 45 — Jump Game II

Pattern: Greedy Frontier / Minimum Jumps

LC 134 — Gas Station

Pattern: Running Balance + Candidate Reset

LC 763 — Partition Labels

Pattern: Last Occurrence + Greedy Partition Boundary

🚀 Greedy Progress

With these four problems, I have covered an important Greedy concept:

Reachability + Boundary Management

The goal is not just to solve individual problems, but to recognize the underlying pattern and apply it to new problems.

👋 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

#ReachabilityBoundaries #GreedyBoundaries #GreedyPattern #DSA #CodingInterview #EnjoyProblems

At first, intervals looked like a simple 2D array problem, but while solving them, I realized that the main challenge is understanding how to sort intervals and what decision to make after sorting.

I recently solved:

• 🔹 LeetCode 452 — Minimum Number of Arrows to Burst Balloons
• 🔹 LeetCode 57 — Insert Interval

These problems helped me understand two important interval patterns:

1. Interval Scheduling
2. Overlapping Intervals

🧠 1. Interval Scheduling

Interval Scheduling problems usually involve intervals like:

[start, end]

The important question is often:

“Which interval should I choose first so that I can make the best possible decisions for the remaining intervals?”

A very common greedy idea is:

👉 Sort intervals by their ending point

Why?

Because if I choose the interval that ends earliest, I leave maximum possible space for the remaining intervals.

For example:

[1,3]
[2,5]
[4,6]
[6,8]

If I choose:

[1,3]

I finish early and can potentially choose more intervals afterward.

This is the basic idea behind Interval Scheduling.

General Pattern

Sort intervals by end time
        ↓
Choose the interval that finishes earliest
        ↓
Update the boundary
        ↓
Continue greedily

This pattern appears in problems involving:

• Maximum number of non-overlapping intervals
• Minimum resources
• Selecting compatible intervals
• Removing conflicting intervals
• Finding the best boundary

🎈 2. Overlapping Intervals

The second important pattern is handling overlapping intervals.

Two intervals overlap when their ranges intersect.

For example:

[1,5]
   [3,7]

They overlap because:

3 <= 5

A very useful condition is:

start <= currentEnd

which means the new interval overlaps with the current interval.

If:

start > currentEnd

then there is no overlap.

🔥 Problem 1 — LeetCode 452

Minimum Number of Arrows to Burst Balloons

Problem

We are given balloons represented as intervals:

[x_start, x_end]

A balloon exists from x_start to x_end.

An arrow is shot vertically at some x coordinate.

If:

x_start <= x <= x_end

the arrow bursts that balloon.

The goal is:

Find the minimum number of arrows needed to burst all balloons.

Example

[10,16]
[2,8]
[1,6]
[7,12]

We want to burst all balloons with minimum arrows.

First, sort them by their ending point:

[1,6]
[2,8]
[7,12]
[10,16]

Now look at the first balloon:

[1,6]

If we shoot an arrow at:

x = 6

it bursts:

[1,6]
[2,8]

because both contain 6.

Now:

[7,12]

doesn’t contain 6, so we need another arrow.

Shoot at:

x = 12

This also bursts:

[10,16]

So the answer is:

2

💡 The Greedy Idea

The important observation is:

When intervals overlap, shoot at the smallest possible ending point.

Why?

Suppose we have:

[1,6]
[2,8]

Their common region is:

[2,6]

If we shoot at 6, we burst both.

Now suppose we have:

[1,6]
[2,8]
[4,10]

The common region is:

[4,6]

Again, shooting at 6 works for all three.

So we keep track of the current end boundary.

🔑 Algorithm

Step 1

Sort intervals by their end:

sort(points.begin(), points.end(),
     [](vector<int>& a, vector<int>& b) {
         return a[1] < b[1];
     });

Step 2

Start with one arrow.

int arrows = 1;

The first arrow is placed at:

points[0][1]

Step 3

Check every next interval.

If:

points[i][0] > arrowPosition

then the current arrow cannot burst this balloon.

So we need another arrow.

🧠 Dry Run

Input:

[10,16]
[2,8]
[1,6]
[7,12]

After sorting:

[1,6]
[2,8]
[7,12]
[10,16]

Initially:

arrows = 1
arrowPosition = 6

[2,8]

2 <= 6

Overlap.

Same arrow works.

[7,12]

7 > 6

No overlap.

Need another arrow.

arrows = 2
arrowPosition = 12

[10,16]

10 <= 12

Overlap.

Same arrow works.

Final:

2

🔥 Problem 2 — LeetCode 57

Insert Interval

This problem is slightly different.

Here, we are given:

intervals

which are already:

• sorted by starting point
• non-overlapping

and we have:

newInterval

We need to insert it while maintaining the properties.

Example

intervals =
[1,3]
[6,9]

newInterval =
[2,5]

We need to insert [2,5].

But:

[1,3]
[2,5]

overlap.

So we merge them:

[1,5]

Final answer:

[1,5]
[6,9]

🧠 The Three Parts of Insert Interval

This problem becomes much easier when we divide it into three phases.

Phase 1 — Intervals Completely Before New Interval

Suppose:

[1,2]
[3,5]
        [6,8]

and:

newInterval = [6,8]

If:

intervals[i][1] < newInterval[0]

then the current interval is completely before the new interval.

So simply add it.

result.push_back(intervals[i]);

Phase 2 — Overlapping Intervals

Now we find intervals that overlap with newInterval.

The important condition is:

intervals[i][0] <= newInterval[1]

If this is true, the intervals overlap.

Then merge them:

newInterval[0] =
    min(newInterval[0], intervals[i][0]);

newInterval[1] =
    max(newInterval[1], intervals[i][1]);

Example

Suppose:

newInterval = [2,5]

current = [3,7]

They overlap because:

3 <= 5

Merge:

start = min(2,3) = 2
end = max(5,7) = 7

So:

[2,5] + [3,7]

becomes:

[2,7]

Phase 3 — Intervals Completely After New Interval

Once we find:

current.start > newInterval.end

there is no possibility of further overlap.

So we first insert the merged newInterval:

result.push_back(newInterval);

Then add all remaining intervals.

🧠 Dry Run

Input:

intervals =
[1,3]
[6,9]

newInterval = [2,5]

Phase 1

Check:

[1,3]

Is:

3 < 2

No.

So we don’t add it.

Phase 2

Check:

[1,3]

Does:

1 <= 5

Yes.

So merge:

[2,5]
[1,3]

becomes:

[1,5]

Next:

[6,9]

Check:

6 <= 5

No.

So overlapping part is finished.

Phase 3

Add:

[1,5]

Then add remaining:

[6,9]

Final:

[1,5]
[6,9]

LC 452

We are trying to minimize arrows.

So we maintain the point where the current arrow is placed.

Sort by end
     ↓
Keep arrow at earliest possible end
     ↓
If next interval starts after arrow
     ↓
Need another arrow

LC 57

We are trying to insert one interval correctly.

So we divide the intervals into:

Before
  ↓
Overlapping
  ↓
After

This makes the problem much easier to reason about.

🧩 My Main Learning From These Problems

The biggest thing I learned was that sorting is not just a preprocessing step.

The sorting order determines the greedy strategy.

For interval problems, I now ask:

1️⃣ What does the interval represent?

[start, end]

2️⃣ What should I sort by?

Possibilities:

start
end

3️⃣ What does overlap mean?

Usually:

start <= currentEnd

4️⃣ What boundary should I maintain?

For example:

currentEnd
arrowPosition
newInterval

5️⃣ What greedy decision gives me the most flexibility?

For scheduling problems, an early ending interval often leaves more room for future intervals.

🚀 My Progress

Another pattern added to my Greedy toolkit:

Greedy
   │
   ├── Sorting-based Greedy
   │
   ├── Interval Scheduling ✅
   │
   ├── Overlapping Intervals ✅
   │
   └── More patterns to explore...

These problems made me realize that 2D arrays and intervals aren’t difficult once the right sorting and boundary logic is clear.

I’m continuing to build my Greedy problem-solving skills pattern by pattern, rather than solving problems randomly.

👋 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

#IntervalScheduling #OverlappingIntervals #GreedyAlgorithm #DSA #CodingInterview #EnjoyProblems