DEV Community: Vansh Aggarwal

LeetCode Solution: 1323. Maximum 69 Number

Vansh Aggarwal — Sun, 12 Apr 2026 17:30:53 +0000

Maximize Your Number: The "Maximum 69 Number" Challenge Explained!

Hey fellow coders! 👋 Vansh2710 here, ready to dive into another fun LeetCode problem that's perfect for beginners but offers a great lesson in greedy thinking. Today, we're tackling problem 1323: Maximum 69 Number.

Don't let the name scare you! This problem is quite approachable and teaches a fundamental concept in algorithm design. Let's break it down together!

🧐 Problem Explanation: What are we trying to do?

Imagine you have a positive integer, but here's the twist: it only consists of the digits 6 and 9. For example, 9669, 9996, or 66.

Your goal is to make this number as large as possible. You have one special power: you can change at most one digit. This means you can either:

Change a 6 to a 9.
Change a 9 to a 6.
Or, choose not to change anything at all if it makes the number smaller.

After making your single optimal change (or no change), you need to return the largest possible number.

Let's look at an example:

If num = 9669:

Change the first 9 to 6 -> 6669
Change the first 6 to 9 -> 9969 <-- This looks good!
Change the second 6 to 9 -> 9699
Change the last 9 to 6 -> 9666

Comparing all these, 9969 is clearly the maximum.

See? Simple, right? Now, how do we find that "maximum" every time?

🤔 Intuition: The "Aha!" Moment

When you want to make a number as large as possible, what digits do you usually want in it? Larger digits! And where do those larger digits have the most impact? At the leftmost positions (highest place values).

Think about it:

Changing 600 to 900 increases the number by 300.
Changing 006 to 009 increases the number by 3.

The digit furthest to the left (the "most significant" digit) contributes the most to the number's overall value.

So, if we have the power to change at most one digit, and we want to maximize the number, what's the best change we can make?

We definitely don't want to change a 9 to a 6, because 6 is smaller than 9, and that would always make our number smaller.
Therefore, our only useful change is to convert a 6 into a 9.

Now, if there are multiple 6s, which one should we change? To maximize the number, we should change the 6 that is furthest to the left. Why? Because changing 6 to 9 in the hundreds place (6xx to 9xx) makes a much bigger difference than changing it in the ones place (xx6 to xx9).

The "Aha!": To get the maximum number, find the first (leftmost) 6 and change it to a 9. If there are no 6s, the number is already all 9s, so no change is needed.

🪜 Approach: Step-by-Step Logic

Let's translate that intuition into a concrete plan:

Convert to String: It's much easier to manipulate individual digits when the number is a string. If num is an integer, convert it into a string or character array. For example, 9669 becomes "9669".
Iterate and Find: Go through the digits of the string from left to right (from the beginning of the string).
The First '6' is Key: The very first time you find a character '6', that's your target! Change that '6' to a '9'.
One Change Only: Since you can change at most one digit, once you've made this change, you're done! You've found the optimal modification. You can stop iterating.
Convert Back: Convert the modified string back into an integer. This will be your maximum number.
Edge Case (No '6's): What if you iterate through the entire string and never find a '6'? This means the original number was already all 9s (like 9999). In this case, you wouldn't have made any changes, and the original number (now as a string, then converted back to int) is already the maximum.

💻 Code

Let's implement this in C. We'll use sprintf to convert the integer to a string, modify the string, and then atoi to convert it back.

#include <stdio.h>  // Required for sprintf and printf (for testing)
#include <string.h> // Required for strlen
#include <stdlib.h> // Required for atoi

int maximum69Number(int num) {
    // 1. Convert the integer to a string (character array).
    // Constraints: 1 <= num <= 10^4.
    // 10^4 has 5 digits. We need space for 5 digits + null terminator.
    char num_str[6]; 
    sprintf(num_str, "%d", num);

    // 2. Iterate through the string to find the first '6'.
    int len = strlen(num_str);
    for (int i = 0; i < len; i++) {
        // 3. If a '6' is found, change it to '9'.
        if (num_str[i] == '6') {
            num_str[i] = '9';
            // 4. We can only make at most one change, so break after the first optimal change.
            break; 
        }
    }

    // 5. Convert the modified string back to an integer and return.
    return atoi(num_str);
}

⏱️ Time & Space Complexity Analysis

Let N be the number of digits in num. Given the constraint 1 <= num <= 10^4, N will be at most 5 digits.

Time Complexity:
- sprintf(num_str, "%d", num): Converting an integer to a string takes time proportional to the number of digits, O(N).
- strlen(num_str): Calculating string length is O(N).
- The for loop iterates through the string at most N times. In the worst case, we might iterate through all digits (if the '6' is the last digit, or if there are no '6's). So, this is O(N).
- atoi(num_str): Converting a string back to an integer also takes time proportional to its length, O(N).
- Since N is very small and constant (at most 5), the overall time complexity is essentially O(1) (constant time).
Space Complexity:
- We create a character array num_str to store the string representation of num. The size of this array is proportional to the number of digits N.
- Since N is constant (at most 5), the space complexity is also O(1) (constant space).

This solution is highly efficient for the given constraints!

💡 Key Takeaways

Greedy Approach: For maximization problems, a greedy strategy often works. Here, making the locally optimal choice (changing the leftmost 6 to 9) leads to the globally optimal solution.
Digit Manipulation: When you need to work with individual digits of a number, converting it to a string is a common and often convenient technique. Just remember to convert it back!
Place Value Matters: Always remember how place value impacts a number's magnitude. Changes to digits on the left have a much greater effect.

I hope this explanation made the "Maximum 69 Number" problem clear and helped you understand the thought process behind solving it! Happy coding!

Authored by Vansh2710

Published: 2026-04-12 23:00:33

LeetCode Solution: 2264. Largest 3-Same-Digit Number in String

Vansh Aggarwal — Sun, 12 Apr 2026 17:20:39 +0000

Uncovering Triple Trouble: Finding the Largest 'Good' Number in Your String!

Hey everyone! 👋 Vansh here, ready to dive into another fun LeetCode challenge that's perfect for beginners but offers some neat insights. Today, we're tackling problem 2264: "Largest 3-Same-Digit Number in String." Don't let the long name scare you; this one is super approachable and a great way to flex your string manipulation muscles!

The Problem: What's a "Good" Number Anyway?

Imagine you're given a really long number as a string, like "6777133339". Your goal is to find special little segments within this string. We call these segments "good integers" if they meet two simple rules:

Length 3: They must be exactly three characters long.
Same Digit: All three characters must be the exact same digit. Think "777", "333", or even "000".

Your task is to find all such "good integers" and then return the largest one among them. If there are no good integers at all, you should just return an empty string "".

Quick Examples to clarify:

Input: num = "6777133339"
- "777" is a good integer.
- "333" is another good integer.
- Between "777" and "333", "777" is larger. So, the output is "777".
Input: num = "2300019"
- "000" is the only good integer. Output: "000".
Input: num = "42352338"
- No three consecutive identical digits exist. Output: "".

A small but important note: leading zeros are totally fine! "000" is a valid good integer.

Intuition: The "Aha!" Moment 💡

When I first read this problem, my brain immediately went to: "Okay, I need to look for patterns of three identical characters." Since we're dealing with a string, the most straightforward way to do this is to simply slide a window of size 3 across the string.

Imagine a magnifying glass that can only see three characters at a time. You start at the beginning, check those three. Then, you slide it one position to the right, check those three, and so on, until you reach the end of the string.

Every time our magnifying glass shows three identical digits (like [7, 7, 7]), we've found a "good integer." Now, how do we find the largest one? Since we're comparing numbers like "999" vs "888" vs "000", and they're all represented as 3-digit strings, comparing them lexicographically (alphabetically, essentially) will work perfectly! "999" is indeed "greater" than "888" in string comparison. This simplifies things a lot!

Approach: Step-by-Step Logic

Let's break down the strategy into clear, executable steps:

Initialize a best variable: We'll need a way to keep track of the largest good integer we've found so far. Let's start it as an empty string (""). This serves two purposes:
- It acts as a placeholder for when no good integers have been found yet.
- If no good integers are ever found, this "" will be our final return value, as required by the problem.
Iterate through the string: We need to check every possible substring of length 3. If num has N characters, and we're looking at num[i], num[i+1], and num[i+2], then the index i can go from 0 all the way up to N-3. Why N-3? Because if i is N-3, then i+2 would be N-1, which is the last character of the string. We can't go any further than that!
Check for "goodness": Inside our loop, for each i, we'll check if num[i], num[i+1], and num[i+2] are all the same. This means num[i] == num[i+1] AND num[i+1] == num[i+2].
Update best: If we find a "good" integer (i.e., the condition in step 3 is true):
- Extract this 3-character substring. Let's call it currentGood. (e.g., num.substr(i, 3)).
- Compare currentGood with our best good integer found so far. We can use the max() function for strings. best = max(best, currentGood). This will automatically pick the lexicographically (and numerically, in this case) larger string. If best is "", the first currentGood will become best.
Return best: After the loop finishes checking all possible substrings, our best variable will hold the largest good integer, or "" if none were found. Simply return it!

The Code (C++)

Here's the elegant C++ solution embodying this approach:

class Solution {
public:
    string largestGoodInteger(string num) {
        string best = ""; // Initialize an empty string to store the largest good integer found

        // Iterate through the string, stopping 2 characters before the end
        // because we need a substring of length 3 (num[i], num[i+1], num[i+2])
        for (int i = 0; i + 2 < num.size(); i++) {
            // Check if the current character and the next two are identical
            if (num[i] == num[i+1] && num[i] == num[i+2]) {
                // If they are, we found a "good" integer.
                // Extract this 3-digit substring.
                string currentGood = num.substr(i, 3);

                // Compare it with our 'best' found so far.
                // Since 'best' starts empty, the first good integer will be assigned.
                // For subsequent good integers, 'max' will correctly pick the numerically larger one
                // because string comparison works lexicographically (e.g., "999" > "888").
                best = max(best, currentGood);
            }
        }

        // Return the largest good integer found, or "" if none existed.
        return best;
    }
};

Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(N)
- We iterate through the num string exactly once using a for loop.
- Inside the loop, operations like character comparisons (num[i] == num[i+1]) and substr(i, 3) (which extracts a fixed-length 3 substring) take constant time, O(1).
- The max(best, currentGood) operation also compares two fixed-length 3 strings, taking O(1) time.
- Therefore, the total time complexity is directly proportional to the length of the input string num. If N is the length of num, it's O(N). This is excellent!
Space Complexity: O(1)
- We use a few extra variables: best and currentGood.
- Both best and currentGood strings are always of a maximum length of 3. This means the amount of extra memory we use is constant, regardless of how long the input string num is.
- Hence, the space complexity is O(1). This is as good as it gets!

Key Takeaways

This problem, while seemingly simple, reinforces some fundamental programming concepts:

Sliding Window: It's a classic technique for problems that involve inspecting contiguous subsequences or substrings of a fixed size.
String Comparison: For numbers represented as strings of the same length, lexicographical comparison (max or > operators) works perfectly to find the numerically largest value.
Edge Case Handling: Initializing best to "" elegantly handles the case where no "good" integers are found.
Simplicity Wins: Sometimes, the most straightforward approach is also the most optimal. No complex data structures or algorithms needed here!

I hope this walkthrough helped you understand and appreciate this LeetCode problem! Happy coding!

Author Account: Vansh2710
Published: 2026-04-12 22:50:06

LeetCode Solution: 326. Power of Three

Vansh Aggarwal — Thu, 09 Apr 2026 18:13:55 +0000

Cracking the Code: Is It a Power of Three? (LeetCode 326 Deep Dive!) 🤯

Hey there, future coding legends! 👋 Vansh2710 here, ready to tackle another fun LeetCode challenge that might seem simple on the surface but has some neat tricks up its sleeve. Today, we're diving into Problem 326: Power of Three.

This problem is a fantastic way to practice handling edge cases, understanding numerical properties, and even thinking about optimization. Let's get started!

The Problem: What Exactly Are We Looking For? 🤔

We're given an integer n. Our task is to determine if n is a "power of three."

What does "power of three" mean?
It means n can be expressed as 3 raised to some integer exponent x (i.e., n == 3^x).

Let's look at the examples:

Example 1: n = 27
- Is 27 a power of three? Yes! 27 = 3 * 3 * 3 = 3^3. So, we should return true.
Example 2: n = 0
- Is 0 a power of three? No. There's no exponent x for which 3^x equals 0. 3^0 = 1, 3^1 = 3, 3^-1 = 1/3, etc. So, we should return false.
Example 3: n = -1
- Is -1 a power of three? No. Powers of positive numbers (like 3) are always positive. So, we should return false.

Key Constraints:
n will be between -2^31 and 2^31 - 1. This is the typical range for a 32-bit signed integer.

The "Aha!" Moment: How Do We Spot a Power of Three? ✨

Imagine you have a number, say 81. How would you manually check if it's a power of three?

You'd probably do something like this:

Is 81 divisible by 3? Yes, 81 / 3 = 27.
Is 27 divisible by 3? Yes, 27 / 3 = 9.
Is 9 divisible by 3? Yes, 9 / 3 = 3.
Is 3 divisible by 3? Yes, 3 / 3 = 1.
We reached 1! This means 81 is indeed a power of three (3^4).

What if we had 28?

Is 28 divisible by 3? No! 28 % 3 = 1. Since we can't divide it evenly by 3 and reach 1, 28 is not a power of three.

This repeated division gives us a strong hint! However, instead of repeatedly dividing, we can also multiply powers of three and see if we hit n. This is the intuition behind the provided solution. We'll start with 1 (which is 3^0) and keep multiplying by 3, checking if we ever reach n.

Step-by-Step Approach 🚀

Let's break down the strategy used in the solution:

Handle Non-Positive Numbers:
- As seen in Example 2 (n=0) and Example 3 (n=-1), any number less than or equal to 0 cannot be a power of three. So, our very first check should be: if (n <= 0) return false;.
Handle the Base Case (n = 1):
- 1 is 3^0. It's a power of three. So, if (n == 1) return true;. This is an important edge case to handle explicitly to avoid issues in the multiplication loop.
Iterative Multiplication:
- We need a variable, let's call it res (for "result"), to store increasing powers of three. Initialize res = 1 (since 3^0 = 1).
- Now, we'll start a loop. In each iteration, we multiply res by 3.
- After each multiplication, we check if res is equal to n. If it is, n is a power of three, and we can immediately return true.
Why long long for res and a loop for 30 iterations?
- The maximum int value is 2^31 - 1 (approx 2 * 10^9).
- The largest power of three that fits in a positive int is 3^19 = 1,162,261,467.
- 3^20 would already exceed 2^31 - 1.
- To avoid potential overflow issues if n is large (and res might temporarily exceed int max before matching n), it's safer to use long long for res. This ensures res can hold values beyond the int range if needed.
- A loop running 30 times is sufficient because 3^19 is the largest relevant power. We don't need to go much further, and 3^30 would certainly exceed long long max if we were to keep calculating without checking res > n (which isn't strictly necessary here because we check n == res and n is an int). The 30 iterations are a safe upper bound.
No Match Found:
- If the loop finishes without n ever matching res, it means n is not a power of three. We then return false.

The Code 🧑‍💻

Here's the complete C++ solution, based on the structure we discussed:

class Solution {
public:
    bool isPowerOfThree(int n) {
        // Step 1: Handle non-positive numbers
        if (n <= 0) {
            return false;
        }

        // Step 2: Handle the base case n = 1 (3^0)
        if (n == 1) {
            return true;
        }

        // Step 3 & 4: Iterative multiplication and check for match
        // Use long long for 'res' to safely store larger powers of three
        // before comparison, preventing potential overflow issues if n is large.
        long long res = 1; 
        for (int i = 0; i < 30; i++) { // 3^19 is largest power fitting in int, 30 iterations is safe
            res = res * 3; // Calculate the next power of three

            // If current power of three matches n, we found our answer!
            if (n == res) {
                return true;
            }

            // Optimization: If 'res' becomes larger than 'n', 
            // 'n' cannot be a power of three because powers of three only grow.
            // This also helps prevent 'res' from overflowing if n is not a power of 3.
            if (res > n) { 
                return false;
            }
        }

        // Step 5: If loop completes without a match, n is not a power of three
        return false;
    }
};

Time & Space Complexity Analysis ⏱️📏

Time Complexity: O(1)
- Why O(1)? The loop runs a fixed maximum number of times (30 iterations). It does not depend on the input n in a way that scales with n (e.g., n itself is not the loop bound). Performing a fixed number of operations means constant time complexity.
Space Complexity: O(1)
- We use a few variables (n, res, i) which take up a constant amount of memory regardless of the input value n.

Key Takeaways ✨

Edge Cases are Crucial: Always consider 0, negative numbers, and the smallest positive case (1 for powers of three).
Iterative Solutions: For problems involving powers, repeated multiplication or division is a very common and effective pattern.
Preventing Overflow: Be mindful of integer limits. Using long long for intermediate calculations when dealing with potentially large numbers (like res * 3) can save you from subtle bugs.
Constant Time is Awesome: When you can solve a problem in O(1) time, you've done a great job!

This problem also has a fascinating "Follow up" question: "Could you solve it without loops/recursion?" This hints at mathematical properties (like using log functions) or leveraging the fact that the largest power of 3 that fits in an int is a known constant. We'll leave that as a thought exercise for another day! 😉

Hope this breakdown helped you understand LeetCode 326 better! Happy coding!

Authored by Vansh2710. Published on 2026-04-09 23:43:07.

LeetCode Solution: 118. Pascal's Triangle

Vansh Aggarwal — Tue, 07 Apr 2026 18:29:40 +0000

Demystifying Pascal's Triangle: A Beginner's Guide to LeetCode 118

Hey there, aspiring coders and problem-solvers! 👋 Today, we're going to dive into a classic and elegant LeetCode problem that's perfect for beginners: 118. Pascal's Triangle. Don't let the mathematical name intimidate you – this problem is a fantastic way to build your foundational algorithmic skills, especially with array manipulation and understanding patterns.

So, grab your favorite beverage, get comfortable, and let's unravel the beauty of Pascal's Triangle together!

The Problem: Building a Beautiful Triangle

The problem statement asks us to generate the first numRows of Pascal's Triangle.

What is Pascal's Triangle?
It's a triangular array of numbers where:

The first and last numbers in each row are always 1.
Every other number in a row is the sum of the two numbers directly above it from the previous row.

Let's look at an example to make this crystal clear:

Example 1:
Input: numRows = 5

Output:

[
     [1],         // Row 0
    [1,1],        // Row 1
   [1,2,1],       // Row 2
  [1,3,3,1],      // Row 3
 [1,4,6,4,1]      // Row 4
]

See how 2 (in Row 2) is 1 + 1 from Row 1? And 3 (in Row 3) is 1 + 2 or 2 + 1 from Row 2? That's the core rule!

Constraints:

1 <= numRows <= 30 (This means we don't have to worry about super large inputs, which is nice for a beginner problem!)

The "Aha!" Moment: Finding the Pattern

Before jumping into code, let's think about how we'd build this triangle by hand.

Row 0: Always [1]
Row 1: Always [1, 1]
Row 2: We know it starts and ends with 1. The middle element? It's the sum of the elements above it from Row 1: 1 (left) + 1 (right) = 2. So, [1, 2, 1].
Row 3: Starts and ends with 1.
- The first inner element: 1 (from Row 2, index 0) + 2 (from Row 2, index 1) = 3.
- The second inner element: 2 (from Row 2, index 1) + 1 (from Row 2, index 2) = 3.
- So, [1, 3, 3, 1].

Do you see the pattern now? Each new row depends entirely on the row immediately above it. This dependency is our key! We can generate the triangle row by row, using the previously generated row to construct the current one. This is a classic example of Dynamic Programming, where we solve subproblems (generating previous rows) to solve the main problem (generating the whole triangle).

The Approach: Building It Up

Here's our step-by-step strategy:

Initialize an empty list of lists (or vector of vectors in C++) called ans. This will hold our final Pascal's Triangle.
Iterate numRows times. Let's say our loop variable i represents the current row number we're trying to build (from 0 up to numRows - 1).
For each row i:
- Create a temp list (or vector) to store the elements of the current row.
- The current row i will always have i + 1 elements.
- Initialize temp with i + 1 elements, setting all of them to 1. This conveniently handles the fact that the first and last elements of every row are always 1.
Calculate the inner elements:
- If i is 0 or 1, the temp row is already correct ([1] or [1, 1]). We don't need to do anything else.
- If i is greater than 1, we need to calculate the middle elements.
- Loop j from 1 up to i - 1 (these are the indices of the inner elements).
- For each temp[j], its value will be the sum of the element at ans[i-1][j-1] and ans[i-1][j].
  - ans[i-1] refers to the previous row that we've already generated and stored.
  - j-1 and j are the two elements directly above the current position j in the previous row.
Add the temp row to ans. After temp is fully constructed for the current row i, add it to our main ans list.
Return ans. After the loop finishes, ans will contain the complete Pascal's Triangle.

The Code: Bringing It to Life (C++)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans; // This will store our complete Pascal's Triangle

        // Loop to generate each row, from row 0 up to numRows-1
        for (int i = 0; i < numRows; ++i) {
            // Create a new vector for the current row.
            // It will have (i + 1) elements.
            // We initialize all elements to 1, which covers the first and last elements.
            vector<int> temp(i + 1, 1);

            // If it's not the first or second row (rows 0 and 1 are just 1s)
            // we need to calculate the inner elements based on the previous row.
            if (i >= 2) {
                // Iterate from the second element (index 1) up to the second-to-last element (index i-1).
                // The first and last elements are already set to 1.
                for (int j = 1; j < i; ++j) {
                    // Each inner element is the sum of the two elements directly above it
                    // from the *previous* row (ans[i-1]).
                    temp[j] = ans[i - 1][j - 1] + ans[i - 1][j];
                }
            }
            // Add the newly constructed row to our overall triangle
            ans.push_back(temp);
        }
        // Return the final Pascal's Triangle
        return ans;
    }
};

Complexity Analysis

Understanding how efficient our solution is crucial in competitive programming!

Time Complexity: O(numRows^2)
- We have an outer loop that runs numRows times (once for each row).
- Inside this loop, we have an inner loop that runs i times (where i is the current row number). The maximum value of i is numRows - 1.
- So, in the worst case, we are doing operations proportional to 1 + 2 + ... + numRows. This sum is approximately (numRows * (numRows + 1)) / 2, which simplifies to O(numRows^2).
Space Complexity: O(numRows^2)
- We are storing the entire Pascal's Triangle.
- The total number of elements in a triangle with numRows rows is also 1 + 2 + ... + numRows, which is O(numRows^2).
- Since the problem asks us to return the entire triangle, this space is necessary to store the output.

Key Takeaways

Pattern Recognition is King: Many algorithmic problems can be simplified by identifying repeating patterns or relationships between elements.
Build It Incrementally: For problems involving sequences or structures like triangles, often the best approach is to build the solution piece by piece, using previously computed results. This is the essence of dynamic programming!
Arrays and Nested Loops: This problem perfectly demonstrates how to use nested data structures (like vector<vector<int>> in C++) and nested loops to generate complex structures.
Edge Cases: Handling the first few rows (Row 0 and Row 1) where the "sum of two numbers above" rule doesn't fully apply is important. Our initialization of temp with all 1s gracefully handles this!

Congratulations on tackling Pascal's Triangle! This problem is a fantastic stepping stone into more complex dynamic programming challenges. Keep practicing, and you'll be solving even tougher problems in no time!

Happy coding! ✨

Authored by Vansh2710 | Published: 2026-04-07 23:59:07

LeetCode Solution: 876. Middle of the Linked List

Vansh Aggarwal — Mon, 06 Apr 2026 18:03:52 +0000

Race to the Middle! Unlocking LeetCode 876: Middle of the Linked List

Hey LeetCoders and aspiring developers! 👋 Vansh2710 here, ready to dive into another fun LeetCode challenge that's perfect for strengthening your understanding of linked lists. Today, we're tackling Problem 876: Middle of the Linked List.

This problem is a fantastic introduction to a super common and powerful technique for linked list manipulation. So, grab your favorite beverage, and let's unravel this together!

🧐 Problem Explanation: What are we actually doing?

Imagine you have a chain of connected boxes (that's a linked list!). Each box contains a number and a pointer (an arrow) to the next box in the chain. The head is the very first box.

Our mission is simple: find the box that's right in the middle of this chain.

If the chain has an odd number of boxes: There's clearly one middle box. We need to return that box and all the boxes that come after it.
- Example 1: head = [1, 2, 3, 4, 5]
  - The middle box is 3. We return [3, 4, 5].
If the chain has an even number of boxes: There are two "middle" boxes. The problem specifically asks us to return the second of these two middle boxes, and all boxes after it.
- Example 2: head = [1, 2, 3, 4, 5, 6]
  - The two middle boxes are 3 and 4. We need to return 4 (the second one) and everything after it: [4, 5, 6].

The constraints are pretty forgiving: the list will have between 1 and 100 nodes. This means we don't have to worry about super long lists for now, but our solution should ideally be efficient!

💡 Intuition: The "Aha!" Moment

How would you find the middle of a chain if you could only look at one box at a time and move forward?

A simple way might be:

Count all the boxes in the chain. Let's say there are N boxes.
Calculate the middle index. If N is 5, the middle is (5 / 2) + 1 = 3 (1-indexed). If N is 6, the middle is (6 / 2) + 1 = 4 (1-indexed, for the second middle).
Then, start from the beginning again and move (middle_index - 1) steps forward to reach the middle box.

This works, but it requires two passes through our linked list: one to count, and one to find the node. Can we do better? Can we find the middle in just one pass?

Think about two runners on a race track...

Imagine you have two runners starting at the same point.

One runner (slow) takes one step at a time.
The other runner (fast) takes two steps at a time.

If they both start from the beginning of the linked list, by the time the fast runner reaches the end of the list, where will the slow runner be?

Precisely! The slow runner will be exactly at the middle! Because the fast runner covers twice the distance in the same amount of time, when fast has reached the finish line, slow has only covered half the track. This is the Two Pointers (or Fast & Slow Pointers) technique!

🪜 Approach: Stepping Through the Solution

Let's formalize our two-pointer strategy:

Initialize two pointers:
- slow pointer, starting at head.
- fast pointer, also starting at head.
Traverse the list with both pointers:
- In each step of our loop:
  - Move slow one step forward: slow = slow->next;
  - Move fast two steps forward: fast = fast->next->next;
Determine the loop's stopping condition:
- The fast pointer is leading the race. It will reach the end first.
- We need to stop when fast or fast->next becomes nullptr (meaning fast has reached or gone past the end of the list).
- So, our loop continues while (fast != nullptr && fast->next != nullptr).
Why this works for both odd and even lists:
- Odd length list (e.g., [1, 2, 3, 4, 5]):
  - Start: slow=1, fast=1
  - Step 1: slow=2, fast=3
  - Step 2: slow=3, fast=5
  - fast->next is nullptr (after 5). The loop terminates. slow is at 3, which is our desired middle node.
- Even length list (e.g., [1, 2, 3, 4, 5, 6]):
  - Start: slow=1, fast=1
  - Step 1: slow=2, fast=3
  - Step 2: slow=3, fast=5
  - Step 3: slow=4, fast points to nullptr (after 6, so fast is nullptr in the next iteration if fast->next was checked first, or fast->next is nullptr if fast is 6 but fast->next is nullptr). The loop terminates. slow is at 4, which is the second middle node, as required!
Return slow: When the loop finishes, slow will be pointing to the middle node (or the second middle node for even-length lists).

This elegant solution finds the middle in a single pass!

💻 Code: Bringing it to Life

Here's the C++ implementation using the fast and slow pointer technique:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // Loop until fast reaches the end of the list (or one node before the end)
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // slow moves one step
            fast = fast->next->next;    // fast moves two steps
        }

        // When fast reaches the end, slow will be at the middle
        return slow;
    }
};

⏱️ Space & Time Complexity Analysis

Let N be the number of nodes in the linked list.

Time Complexity: O(N)
- We traverse the linked list exactly once. The fast pointer covers N nodes (or slightly less/more depending on N's parity), and the slow pointer covers N/2 nodes. Regardless, the number of operations scales linearly with the number of nodes.
Space Complexity: O(1)
- We only use a constant amount of extra space for our slow and fast pointers, regardless of the list's size. No auxiliary data structures are used.

This is an optimal solution in terms of both time and space complexity!

🚀 Key Takeaways

Two Pointers (Fast & Slow Pointers): This is a cornerstone technique for linked list problems! It's incredibly useful for finding the middle, detecting cycles, or finding the k-th node from the end.
Single Pass Efficiency: By using two pointers moving at different speeds, we can often solve problems that might otherwise require multiple passes, saving computation time.
Edge Cases for Linked Lists: Always consider empty lists, single-node lists, and two-node lists when designing your logic. Here, fast != nullptr && fast->next != nullptr elegantly handles these.

That's a wrap for Problem 876! I hope this deep dive into the "Middle of the Linked List" problem has demystified the fast and slow pointer technique for you. Keep practicing, and you'll master these patterns in no time!

Happy Coding! ✨

Authored by Vansh2710
Published: 2026-04-06 23:32:58

LeetCode Solution: 450. Delete Node in a BST

Vansh Aggarwal — Sun, 05 Apr 2026 16:37:03 +0000

Conquering BST Deletion: A Beginner's Guide to LeetCode 450

Hey amazing developers! Vansh2710 here, ready to tackle another classic LeetCode problem. Today, we're diving into the sometimes-tricky world of Binary Search Tree (BST) deletion. Specifically, we're taking on LeetCode 450: Delete Node in a BST.

Don't let the "deletion" part scare you! While it might seem intimidating at first, we'll break it down step-by-step, making it super clear and manageable. Think of it as a puzzle with a few distinct pieces – once you understand each piece, the whole picture becomes simple.

The Problem Explained: Deleting a Node from a BST

Imagine you have a phone directory (a BST!). Each entry (node) has a name (value). You want to remove an old contact (a key) from this directory while making sure it remains sorted alphabetically (maintaining the BST property).

That's essentially what LeetCode 450 asks us to do:
Given the root of a Binary Search Tree and a key (the value of the node you want to delete):

Search: First, locate the node that contains the key.
Delete: If the node is found, remove it. The tricky part is ensuring that after deletion, the tree remains a valid BST! If the node isn't found, simply return the original tree.

What is a BST, again?
A Binary Search Tree is a special type of binary tree where for every node:

All values in its left subtree are less than the node's value.
All values in its right subtree are greater than the node's value. This property makes searching, insertion, and deletion very efficient!

Let's look at an example:

Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

Initially:

We want to delete 3. Notice how 4 takes its place to maintain the BST property ( 4 is greater than 2 and less than 5).

After deleting 3 and replacing with 4:

(Another valid answer could have 2 taking 3's place!)

The key takeaway here is that when you remove a node, you need to find a suitable replacement that keeps the whole tree "sorted."

Intuition: The "Aha!" Moment for Deletion

The core idea behind BST deletion is maintaining its fundamental property. When you remove a node, its children (if any) can't just float in space. They need to be reattached in a way that preserves the BST order.

The "aha!" moment comes from realizing there are three main scenarios when you find the node to delete:

It's a leaf node (no children): This is the easiest! Just remove it. No children to worry about.
It has one child: The child can simply take the place of the deleted node. If you delete node X which has only a left child L, then L becomes the new child of X's parent. The BST property holds because all nodes in L's subtree are still less than X's parent (if X was a left child) or greater (if X was a right child).
It has two children: This is the trickiest part! You can't just pick one child, as the other would be lost. Here's where we get clever:
- To maintain the BST property, the replacement node must be greater than all nodes in the left subtree and less than all nodes in the right subtree.
- The perfect candidates for this are either the smallest node in the right subtree (also known as the in-order successor) or the largest node in the left subtree (the in-order predecessor).
- If we replace the deleted node's value with its in-order successor's value, the BST property is preserved. Then, we simply delete that successor from its original position in the right subtree (which will be one of the easier cases: a leaf or a node with one child, specifically a right child).

We can use a recursive approach for this. Why? Because searching for the node and then potentially deleting a replacement node (if it has two children) are both operations that can be naturally handled by recursion, similar to how we traverse BSTs.

Approach: Step-by-Step Logic

Let's translate that intuition into a concrete algorithm:

Our deleteNode(root, key) function will work recursively:

Base Case:
- If root is nullptr (the tree is empty or we've searched past a leaf), the key isn't found. Return nullptr.
Search Phase:
- If key < root->val: The node we want to delete must be in the left subtree. Recursively call root->left = deleteNode(root->left, key).
- If key > root->val: The node we want to delete must be in the right subtree. Recursively call root->right = deleteNode(root->right, key).
Deletion Phase (when key == root->val): We found the node to delete! Now, we handle the three cases:

*   **Case 1: Node has no children (Leaf Node)**
    *   Simply delete the `root` node and return `nullptr` to its parent, effectively removing it from the tree.

*   **Case 2: Node has one child**
    *   If `root->left` is `nullptr` (only a right child): Store `root->right` in a temporary variable, delete `root`, and return the `temp` node. The right child takes its parent's place.
    *   If `root->right` is `nullptr` (only a left child): Store `root->left` in a temporary variable, delete `root`, and return the `temp` node. The left child takes its parent's place.

*   **Case 3: Node has two children**
    *   This is the most involved part. We need to find the in-order successor.
    *   **Find Successor:** Traverse to the right child of the current `root`, then keep going left as far as possible. This will give you the smallest node in the right subtree. Let's call this `successor`.
    *   **Replace Value:** Copy `successor->val` into `root->val`. Now, the current node `root` has the value of its successor.
    *   **Delete Successor:** The `successor` node is now duplicated. We need to remove its original position. Recursively call `root->right = deleteNode(root->right, successor->val)`. This will remove the `successor` from the right subtree, which will be an easier deletion case (either a leaf or a node with one right child).

Return root: After any modifications (or if no deletion happened), always return the current root back to its parent. This is crucial for correctly rebuilding the tree structure in the recursive calls.

The Code

Here's the C++ implementation following our approach.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // Base Case: If the tree is empty or key not found
        if (root == nullptr){
            return nullptr;
        }

        // Search Phase: Traverse the BST to find the node
        if(key < root->val){
            // Key is smaller, go to the left subtree
            root -> left  = deleteNode(root->left, key);
        }
        else if(key > root->val){
            // Key is larger, go to the right subtree
            root->right = deleteNode(root->right, key);
        }
        else{ // key == root->val: Node to be deleted found!
            // Case 1: Node has no children (it's a leaf)
            if(root->left == nullptr && root->right == nullptr){
                delete root; // Free memory
                return nullptr; // This node is now gone
            }
            // Case 2: Node has only one child
            else if(root->left == nullptr){ // Only right child exists
                TreeNode* temp = root->right; // Store the right child
                delete root; // Delete the current node
                return temp; // Replace current node with its right child
            }
            else if(root->right == nullptr){ // Only left child exists
                TreeNode* temp = root->left; // Store the left child
                delete root; // Delete the current node
                return temp; // Replace current node with its left child
            }
            // Case 3: Node has two children
            else{
                // Find the in-order successor (smallest node in the right subtree)
                TreeNode* successor = root->right;
                while(successor->left != nullptr){
                    successor = successor->left;
                }

                // Replace the value of the current node with the successor's value
                root->val = successor->val;

                // Recursively delete the successor from the right subtree
                // The successor will either be a leaf or have only a right child,
                // making its deletion simple.
                root->right = deleteNode(root->right, successor->val);
            }
        }
        // Return the (potentially updated) root of the current subtree
        return root;
    }
};

Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(H)
- H is the height of the BST.
- In the worst case (a skewed tree, like a linked list), H can be N (number of nodes). In the best case (a balanced tree), H is log N.
- Why O(H)?
  - The search phase involves traversing down the tree, at most H levels.
  - If the node has two children, finding the successor also involves traversing down the right subtree, at most H levels.
  - The recursive call to delete the successor also follows a path down the tree, again at most H levels.
  - All these operations combined are proportional to the height of the tree.
Space Complexity: O(H)
- This is due to the recursion call stack. In the worst case, if the tree is highly skewed, the recursion depth can be N. For a balanced tree, it's log N.

This solution perfectly meets the follow-up requirement of solving it with time complexity O(height of tree)!

Key Takeaways

Recursive Thinking is Your Friend: BST problems often lend themselves beautifully to recursion. Thinking about how to solve a subproblem and combine results is key.
Three Deletion Cases: The heart of BST deletion lies in distinguishing and handling leaf nodes, nodes with one child, and nodes with two children separately.
In-order Successor/Predecessor: For nodes with two children, the in-order successor (smallest in right subtree) or predecessor (largest in left subtree) is your go-to replacement to maintain the BST property.
Memory Management: In C++, remember to delete nodes to prevent memory leaks, especially when you are freeing up a node's memory.

BST deletion is a foundational concept in data structures. Mastering it gives you a deeper understanding of how trees work and how to manipulate them efficiently. Keep practicing, and you'll be a BST pro in no time!

Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-05 22:06:35

LeetCode Solution: 938. Range Sum of BST

Vansh Aggarwal — Sat, 04 Apr 2026 17:15:21 +0000

Unleash Your Inner Tree Wizard: Summing Values in a BST Range (LeetCode #938)

Hey fellow coders! 👋 Vansh2710 here, diving deep into another LeetCode adventure. Today, we're tackling a super common and insightful problem that truly highlights the power of Binary Search Trees (BSTs): Problem 938: Range Sum of BST.

This problem is a fantastic way to solidify your understanding of tree traversals and how to leverage the unique properties of a BST for efficiency. Let's get cracking!

🌳 Problem Explanation: What's the Goal?

Imagine you have a special kind of tree called a Binary Search Tree (BST). What makes it special? For every node in the tree:

All values in its left subtree are smaller than the node's own value.
All values in its right subtree are larger than the node's own value.

Pretty neat, right? This property is what makes BSTs so powerful for searching and sorting.

Now, for this problem, you're given:

The root node of one of these amazing BSTs.
Two integers, low and high.

Your mission, should you choose to accept it (which you will!): Find the sum of all node values that fall within the inclusive range [low, high]. This means any node with a value val where low <= val <= high should be added to our total.

Let's look at an example to make it crystal clear:

Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Here's how that tree looks and why the answer is 32:

        10
       /  \
      5    15
     / \    \
    3   7    18

Nodes in range [7, 15]:

7 (Yes, 7 is >= 7 and <= 15)
10 (Yes, 10 is >= 7 and <= 15)
15 (Yes, 15 is >= 7 and <= 15)

The sum is 7 + 10 + 15 = 32. Nodes like 3, 5, and 18 are outside the range, so we ignore them.

🤔 Intuition: The "Aha!" Moment

At first glance, you might think, "Okay, I'll just traverse the entire tree (like a depth-first search or breadth-first search), check each node, and if it's in the range, add it to my sum." And you know what? That approach would work! It's perfectly valid.

But wait, we have a Binary Search Tree! Can we do better? The BST property is our secret weapon here. It tells us a lot about which parts of the tree are worth exploring and which are definitely not.

Here's the "aha!":

If our current node's value (root->val) is smaller than low, we know for sure that its entire left subtree contains values even smaller than root->val. So, none of them can possibly be in our [low, high] range. We can completely skip the left subtree and only look at the right subtree!
Similarly, if root->val is larger than high, we know its entire right subtree contains values even larger than root->val. None of those can be in our range. We can skip the right subtree and only look at the left subtree!
If root->val is within our [low, high] range, then we add it to our sum, AND we need to explore both its left and right subtrees, because they might contain other nodes within the range.

This insight allows us to "prune" (cut off) entire branches of the tree that we know won't contain any relevant nodes, making our solution much more efficient!

🚀 Approach: A Recursive Journey

We'll use a recursive Depth-First Search (DFS) approach to traverse the tree, smartly skipping subtrees based on the BST property.

Here's the step-by-step logic:

Base Case: If we encounter a null node (meaning we've gone past a leaf or an empty branch), there's nothing to add. We simply return 0. This stops our recursion.
Check Current Node's Value:
- If root->val is between low and high (inclusive):
  - This node's value is part of our sum! Add root->val to our total.
  - Since its children could also be in the range, we need to recursively call our function for both the root->left and root->right subtrees and add their returned sums.
  - So, return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);

*   **If `root->val` is less than `low`:**
    *   We know `root->val` is too small.
    *   Because it's a BST, all values in its `root->left` subtree will be even *smaller* than `root->val`, so they definitely won't be in our `[low, high]` range. We can ignore the left subtree!
    *   However, values in the `root->right` subtree *could* be larger than `low` and thus potentially in our range.
    *   So, we only need to recursively call for the `root->right` subtree: `return rangeSumBST(root->right, low, high);`

*   **If `root->val` is greater than `high`:**
    *   We know `root->val` is too large.
    *   Because it's a BST, all values in its `root->right` subtree will be even *larger* than `root->val`, so they definitely won't be in our `[low, high]` range. We can ignore the right subtree!
    *   However, values in the `root->left` subtree *could* be smaller than `high` and thus potentially in our range.
    *   So, we only need to recursively call for the `root->left` subtree: `return rangeSumBST(root->left, low, high);`

And that's it! This intelligent pruning makes our solution incredibly efficient.

🧑‍💻 Code

Here's the C++ implementation reflecting our approach:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        // Base case: If the current node is null, there's nothing to add.
        if (root == nullptr) {
            return 0;
        }

        // Case 1: Current node's value is within the range [low, high]
        if (root->val >= low && root->val <= high) {
            // Add current node's value and recursively sum from both children.
            // Both left and right subtrees might contain nodes in the range.
            return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
        }
        // Case 2: Current node's value is less than 'low'
        else if (root->val < low) {
            // All nodes in the left subtree will also be less than 'low' (BST property).
            // So, we only need to explore the right subtree.
            return rangeSumBST(root->right, low, high);
        }
        // Case 3: Current node's value is greater than 'high'
        else { // root->val > high
            // All nodes in the right subtree will also be greater than 'high' (BST property).
            // So, we only need to explore the left subtree.
            return rangeSumBST(root->left, low, high);
        }
    }
};

⏱️ Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(N) in the worst case, but often much better.
- In the worst-case scenario (e.g., if low is 1 and high is 10^5, covering the entire tree's possible range), we might end up visiting every single node in the tree. If there are N nodes, this would be O(N).
- However, thanks to the BST property and our pruning strategy, we only visit nodes that could potentially be within the [low, high] range. This means we avoid traversing entire subtrees that we know are irrelevant. So, while the upper bound is O(N), for many inputs, it's significantly faster than a generic tree traversal.
Space Complexity: O(H)
- This is due to the recursion call stack. H represents the height of the binary search tree.
- In the worst case (a skewed tree, resembling a linked list), the height H could be N (the number of nodes). So, space complexity would be O(N).
- In the best/average case (a balanced tree), the height H is log N. So, space complexity would be O(log N).

💡 Key Takeaways

BST Properties are Gold: Always look for ways to leverage the unique characteristics of a data structure. For BSTs, the left < root < right rule is incredibly powerful for optimizing searches and traversals.
Recursive Thinking for Trees: Many tree problems lend themselves beautifully to recursive solutions. Define your base case and how to combine results from subproblems.
Pruning for Performance: Smartly skipping irrelevant parts of the data structure (like entire subtrees here) can drastically improve the efficiency of your algorithms.

This problem is a fantastic stepping stone for understanding more complex BST problems and reinforcing your tree traversal skills. Keep practicing, and you'll be a tree wizard in no time! Happy coding! ✨

Author Account: Vansh2710 | Time Published: 2026-04-04 22:44:40

LeetCode Solution: 869. Reordered Power of 2

Vansh Aggarwal — Fri, 03 Apr 2026 18:54:31 +0000

Unraveling LeetCode 869: Can Your Number Shuffle into a Power of Two?

Hey everyone! Vansh2710 here, ready to tackle another intriguing LeetCode challenge. Today, we're diving into problem 869, "Reordered Power of 2." This problem sounds like a fun riddle: given a number, can you rearrange its digits to form a power of two? Let's break it down!

📝 Problem Explanation

You're given an integer n. Your task is to figure out if you can reorder its digits in any way to form a new number that is a power of two.

Important Rules:

Reordering: You can arrange the digits of n in any order.
Leading Digit: The new number you form cannot have a leading zero (unless the number itself is just '0', which isn't a power of two we're interested in here).
Power of Two: The resulting number must be a power of two (i.e., 1, 2, 4, 8, 16, 32, ... which are 2^0, 2^1, 2^2, and so on).

Let's look at some examples:

Example 1: n = 1
- The digits of n are just 1.
- Can we reorder 1? Well, it's already 1.
- Is 1 a power of two? Yes, 2^0 = 1.
- Output: true
Example 2: n = 10
- The digits of n are 1 and 0.
- Possible reorderings: 10 (leading digit not zero), 01 (leading digit is zero, so invalid).
- Is 10 a power of two? No.
- Output: false

The constraints tell us 1 <= n <= 10^9. This is a crucial piece of information!

🤔 Intuition: The "Aha!" Moment

When you see a problem asking if you can "reorder digits" to form something specific, a common technique springs to mind: digit frequency counting!

Think about it: if two numbers are just reorderings of each other, they must have the exact same count of each digit. For example, 123 and 312 both have one 1, one 2, and one 3.

So, our problem boils down to:

Take the input number n.
Count how many times each digit (0-9) appears in n.
Now, how do we check if any power of two can be formed from these digits? Instead of trying to generate permutations of n (which can be a lot!), what if we just check a list of known powers of two?

This is where the constraint n <= 10^9 becomes our best friend.

n can have at most 10 digits (e.g., 1,000,000,000).
Powers of two quickly grow!
- 2^0 = 1
- 2^1 = 2
- ...
- 2^9 = 512 (3 digits)
- 2^10 = 1024 (4 digits)
- ...
- 2^29 = 536,870,912 (9 digits)
- 2^30 = 1,073,741,824 (10 digits)
- 2^31 would exceed the int limit and also have too many digits if n maxes out at 10.

So, we only need to check a relatively small list of powers of two (from 2^0 up to 2^30 or so). For each power of two in this list, we can count its digit frequencies and compare them to the digit frequencies of our input n. If we find a match, we've solved it!

🪜 Approach: Step-by-Step Logic

Here's the detailed plan based on our intuition:

Count Digits for n:
- Create an array (or vector) of size 10, initialized to zeros. Each index i will store the count of digit i.
- Convert n to a string.
- Iterate through each character (digit) in the string, convert it back to an integer, and increment its count in our array.
Iterate Powers of Two:
- Start a loop from i = 0 up to 30 (or 31 if you want to be super safe, covering 2^0 to 2^30).
- In each iteration, calculate current_power_of_2 = 1 << i (which is a fast way to get 2^i).
Count Digits for current_power_of_2:
- For each current_power_of_2, perform the same digit counting process as we did for n. Store these counts in a temporary array.
Compare Digit Counts:
- Compare the digit count array of n (from Step 1) with the digit count array of current_power_of_2 (from Step 3).
- If both arrays are identical (meaning they have the same counts for all digits 0-9), then we've found a power of two that can be formed by reordering n's digits. In this case, immediately return true.
No Match Found:
- If the loop finishes without finding any matching power of two, it means no such rearrangement exists. Return false.

Why this works: The leading digit constraint ("leading digit is not zero") is automatically handled because powers of two (other than 2^0=1) are always positive and never start with zero. Our digit counting only cares about the set of digits, not their order initially. If the digit counts match, it means we can form that power of two, and since it's a valid power of two, its leading digit will never be zero (unless it's a single-digit '0', which isn't a power of two, or if n itself were 0, but n >= 1).

💻 Code

Here's the C++ implementation of our approach:

class Solution {
public:
    // Helper function to count digit frequencies for a given number
    // It returns a vector of size 10, where index i stores the count of digit i.
    std::vector<int> getDigitCounts(int num) {
        std::vector<int> counts(10, 0); // Initialize counts for digits 0-9 to zero
        std::string s = std::to_string(num); // Convert the number to a string

        // Iterate through each character (digit) in the string
        for (char c : s) {
            counts[c - '0']++; // Increment the count for the corresponding digit
        }
        return counts; // Return the frequency map
    }

    bool reorderedPowerOf2(int n) {
        // Step 1: Get digit frequency counts for the input number 'n'
        std::vector<int> n_digit_counts = getDigitCounts(n);

        // Step 2: Iterate through all relevant powers of 2
        // We check powers from 2^0 up to 2^30.
        // 2^0 = 1
        // ...
        // 2^29 = 536,870,912 (9 digits)
        // 2^30 = 1,073,741,824 (10 digits)
        // Since n <= 10^9, n can have at most 10 digits.
        // Any power of two with more than 10 digits, or fewer digits but different counts,
        // will automatically not match. So checking up to 2^30 is sufficient.
        for (int i = 0; i < 31; ++i) { // Loop from i=0 to i=30 (inclusive)
            int powerOf2 = 1 << i; // Calculate 2 raised to the power of i

            // Step 3: Get digit frequency counts for the current power of 2
            std::vector<int> current_power_digit_counts = getDigitCounts(powerOf2);

            // Step 4: Compare the digit frequency counts
            // If the counts are identical, it means we can reorder the digits of 'n'
            // to form this 'powerOf2'.
            if (n_digit_counts == current_power_digit_counts) {
                return true; // Found a match, so return true
            }
        }

        // If the loop completes without finding any matching power of two,
        // then it's not possible to reorder 'n' into a power of two.
        return false;
    }
};

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity:
- n can be up to 10^9, which means it has at most 10 digits (i.e., log10(n) digits). Let D be the maximum number of digits (here, D = 10).
- The getDigitCounts function:
  - to_string(num) takes O(D) time.
  - The loop iterates D times.
  - So, getDigitCounts is O(D).
- The main reorderedPowerOf2 function:
  - Calls getDigitCounts(n) once: O(D).
  - The loop runs 31 times (for i from 0 to 30). Let P be the number of powers of two we check (here, P = 31).
  - Inside the loop, getDigitCounts(powerOf2) is called: O(D) (since powers of two up to 2^30 also have at most D=10 digits).
  - Comparing std::vector<int> takes O(10) which is O(D) as it compares each of the 10 elements.
- Total Time Complexity: O(D) + P * (O(D) + O(D)) = O(D * P).
- Given D = 10 and P = 31, this is roughly 10 * 31 = 310 operations. This is extremely efficient! It's practically constant time.
Space Complexity:
- The getDigitCounts function uses a std::vector<int> of size 10 to store digit counts. This size is fixed, regardless of n.
- The reorderedPowerOf2 function also uses two std::vector<int> of size 10.
- Total Space Complexity: O(1) (constant space), as the storage required does not grow with the input n.

🔑 Key Takeaways

Digit Frequency for Permutations: When a problem involves checking if numbers can be formed by "reordering" or "permuting" digits, counting digit frequencies is a powerful and often more efficient alternative than generating actual permutations.
Leverage Constraints: The n <= 10^9 constraint was crucial. It limited our search space for powers of two to a very small, manageable number, turning what could be a complex permutation problem into a simple fixed-loop iteration.
Powers of Two: Understanding how fast powers of two grow helps in setting appropriate loop bounds.
Helper Functions: Breaking down repetitive logic (like digit counting) into a helper function makes your code cleaner, more readable, and easier to debug.

This problem is a fantastic example of how understanding constraints and choosing the right data structure/technique can simplify a seemingly complex challenge! Keep practicing, and happy coding!

Submission Details:
Author Account: Vansh2710
Time Published: 2026-04-04 00:24:08

LeetCode Solution: 204. Count Primes

Vansh Aggarwal — Thu, 02 Apr 2026 17:56:01 +0000

Unleashing the Power of Primes: Your First Sieve of Eratosthenes Adventure!

Hey there, future coding rockstars! 👋 Vansh here, ready to dive into another exciting LeetCode challenge with you. Today, we're tackling a classic problem that's super common in interviews and a fantastic way to learn about optimizing your code: 204. Count Primes.

Don't let the name scare you! We're going to break it down, understand the "aha!" moment, and build a super-efficient solution together. Ready? Let's roll!

🚀 The Problem Explained: Counting Our Prime Friends

Imagine you're at a party, and you need to count all the "special" guests. In our coding world, these special guests are prime numbers.

The problem asks us to:
Given an integer n, return the number of prime numbers that are strictly less than n.

What's a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

2, 3, 5, 7, 11 are primes.
4 (divisible by 2), 6 (divisible by 2, 3), 9 (divisible by 3) are NOT primes.

Let's look at the examples:

Example 1: n = 10
- We need primes less than 10.
- Primes: 2, 3, 5, 7
- Output: 4
Example 2: n = 0
- Primes are greater than 1. No primes less than 0.
- Output: 0
Example 3: n = 1
- No primes less than 1.
- Output: 0

The constraint 0 <= n <= 5 * 10^6 tells us that n can be quite large, hinting that a simple, brute-force approach might be too slow. This is where our optimization journey begins!

🤔 Intuition: From Naive to Nimble!

So, how would you first approach this?

First thought (The Naive Way):
"Okay, I'll just check every number from 2 up to n-1. For each number, I'll test if it's prime. How do I test if a number k is prime? I'll try dividing k by numbers from 2 up to sqrt(k). If none of them divide k evenly, then k is prime!"

count = 0
for (i from 2 to n-1):
    if (isPrime(i)):
        count++
return count

// Helper function isPrime(k):
// for (j from 2 to sqrt(k)):
//     if (k % j == 0):
//         return false
// return true

This approach works! But let's think about efficiency. If n is 5 * 10^6, checking 5 * 10^6 numbers, and for each, doing sqrt(5 * 10^6) divisions... that's going to be astronomically slow! We need something much faster.

The "Aha!" Moment (The Sieve of Eratosthenes):

Instead of checking each number individually, what if we could eliminate non-prime numbers systematically?

Imagine you have a list of all numbers from 2 to n-1.

Start with the first prime number we know: 2.
Since 2 is prime, we know all its multiples (4, 6, 8, 10, 12...) cannot be prime. Let's cross them out!
Move to the next number that hasn't been crossed out: 3.
Since 3 is prime, cross out all its multiples (6, 9, 12, 15...). Notice that 6 and 12 were already crossed out by 2 – that's perfectly fine!
Move to the next unmarked number: 5. (4 was crossed out by 2). Cross out its multiples (10, 15, 20...).
Keep repeating this process!

By the end, any number that is not crossed out must be prime! This brilliant technique is called the Sieve of Eratosthenes, and it's perfect for finding all primes up to a certain limit.

💡 Approach: The Sieve in Action!

Let's walk through the steps of implementing the Sieve of Eratosthenes:

Initialize a "Primes Tracker":
- Create a boolean array (or an integer array where 1 means true and 0 means false) called is_prime of size n.
- Initialize all entries from is_prime[2] to is_prime[n-1] as true (or 1), assuming they are prime for now.
- is_prime[0] and is_prime[1] should be false (or 0), because 0 and 1 are not prime.
Start Sieving (The Main Loop):
- We'll iterate with a variable p starting from 2.
- The loop should continue as long as p * p < n. Why p * p? Because if p is a prime, all its multiples less than p * p (like p * 2, p * 3, up to p * (p-1)) would have already been marked as not prime by smaller prime factors. For example, multiples of 5 less than 25 (like 10, 15, 20) would have been marked by 2 or 3.
Marking Multiples:
- Inside the loop, if is_prime[p] is still true (meaning p itself is a prime number):
  - We know p is prime, so all its multiples are not prime.
  - Start another inner loop from i = p * p up to n-1, incrementing by p each time (i += p).
  - Set is_prime[i] = false (or 0) for all these multiples.
Count the Primes:
- After the main loop finishes, all numbers that are still marked true in our is_prime array are prime numbers.
- Iterate through the is_prime array from 2 up to n-1.
- For every is_prime[i] that is true, increment a count variable.
Return the Count:
- The final count is our answer!

Let's see this in C!

💻 Code: The Sieve in C

#include <stdlib.h> // Required for malloc and free

int countPrimes(int n) {
    // Handle edge cases: No primes less than or equal to 2
    if (n <= 2) {
        return 0;
    }

    // 1. Create a boolean array "is_prime[0...n-1]" and initialize
    //    all entries as true (represented by 1). A value in is_prime[i] will
    //    finally be false (0) if i is Not a prime, else true (1).
    //    Using an int array as a boolean array where 1=true, 0=false.
    int* is_prime = (int*)malloc(n * sizeof(int));
    if (is_prime == NULL) {
        // Handle memory allocation failure
        // For LeetCode, this typically won't happen for given constraints,
        // but good practice in real-world C code.
        return 0;
    }

    // Initialize all numbers to be potentially prime
    for (int i = 0; i < n; i++) {
        is_prime[i] = 1; // 1 means true (potentially prime)
    }

    // 0 and 1 are not prime numbers
    is_prime[0] = 0; // 0 means false (not prime)
    is_prime[1] = 0; // 0 means false (not prime)

    // 2. Start the Sieve process from p = 2
    //    We only need to iterate up to sqrt(n) because any composite number
    //    n must have a prime factor less than or equal to sqrt(n).
    for (int p = 2; p * p < n; p++) {
        // If is_prime[p] is still true, then it is a prime number
        if (is_prime[p] == 1) {
            // 3. Mark all multiples of p as not prime (false)
            //    We start marking from p*p because any multiple smaller than p*p
            //    (e.g., 2*p, 3*p, etc.) would have already been marked by a
            //    smaller prime factor (e.g., 2, 3).
            for (int i = p * p; i < n; i += p) {
                is_prime[i] = 0; // Mark as not prime
            }
        }
    }

    // 4. Count all prime numbers
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (is_prime[i] == 1) {
            count++;
        }
    }

    // 5. Free the dynamically allocated memory
    free(is_prime);

    return count;
}

⏱️ Complexity Analysis

Understanding how efficient our algorithm is, is just as important as writing the correct code!

Time Complexity: O(N log log N)
- This might look intimidating, but it's incredibly efficient for finding all primes up to N.
- The outer loop runs up to sqrt(N).
- The inner loop (marking multiples) for each prime p iterates N/p times.
- When you sum N/p for all primes p up to N, it mathematically approximates to N log log N. This is much faster than O(N * sqrt(N)) of the naive approach!
Space Complexity: O(N)
- We use an array is_prime of size N to store the primality status of each number. This makes the space complexity directly proportional to N.

🎯 Key Takeaways

The Sieve of Eratosthenes: This is a fundamental algorithm for efficiently finding all prime numbers up to a specified limit. It's a must-know for competitive programming and interviews!
Trade-off: We use extra space (O(N) for the is_prime array) to achieve significantly faster time complexity (O(N log log N)). This is a common pattern in algorithm design!
Optimization p * p: Starting the inner loop from p * p is a crucial optimization that prevents redundant work and makes the sieve faster.
Problem Recognition: When you see problems asking for "all primes up to N" or "counting primes less than N" with large N, think Sieve!
Memory Management (in C/C++): Don't forget to free dynamically allocated memory (malloc) to prevent memory leaks!

Congratulations! You've just learned and implemented one of the coolest and most efficient prime-finding algorithms out there. Keep practicing, and you'll be a coding wizard in no time!

Happy coding! ✨

Authored by Vansh2710 | Published: 2026-04-02 23:25:05

LeetCode Solution: 204. Count Primes

Vansh Aggarwal — Thu, 02 Apr 2026 17:50:06 +0000

Unlock the Primes: Your First Dive into Counting Primes (LeetCode 204)

Hey there, future coding rockstars! 👋

Vansh2710 here, your friendly neighborhood competitive programmer and technical writer. Today, we're going to tackle a classic LeetCode problem that's super common in interviews and a fantastic way to learn about efficient algorithms: Problem 204: Count Primes.

Don't let the "mathy" title scare you! We'll break it down piece by piece, find an awesome solution, and make sure you walk away feeling like a prime number pro. Ready? Let's dive in!

Problem Explanation: What are we actually counting?

The problem asks us to do one simple thing: given an integer n, return the number of prime numbers that are strictly less than n.

"Strictly less than n" means we're looking at numbers from 0 up to n-1.

Let's look at a few examples to make it crystal clear:

Example 1: n = 10
- Numbers strictly less than 10 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- Which of these are prime? A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
- The primes are: 2, 3, 5, 7.
- So, the output is 4.
Example 2: n = 0
- Numbers strictly less than 0? None!
- Output: 0.
Example 3: n = 1
- Numbers strictly less than 1? Only 0.
- Is 0 prime? No, primes must be greater than 1.
- Output: 0.

Simple enough, right? The core challenge is how to count these primes efficiently, especially when n can be as large as 5 * 10^6.

Intuition: From Naive to "Aha!" Moment 💡

Before we jump into the best solution, let's think about how we might naively solve this.

Naive Approach:

Start a counter for primes, initialized to 0.
Loop through every number i from 2 up to n-1.
For each i, check if it's prime. How? By trying to divide i by every number j from 2 up to sqrt(i). If i is divisible by any j (meaning i % j == 0), then i is not prime. If it's not divisible by any j, then i is prime, and we increment our counter.

This approach works, but it's incredibly slow. Imagine n is 5 * 10^6. For each number up to n, you're doing another loop that goes up to its square root. The total operations would be roughly n * sqrt(n), which for n = 5 * 10^6 is a massive number (~10 billion operations!). This will definitely give us a "Time Limit Exceeded" (TLE) error on LeetCode.

The "Aha!" Moment - The Sieve of Eratosthenes

What if, instead of repeatedly checking divisibility for each number, we could mark off non-prime numbers more efficiently?

This is where the ancient Greek mathematician Eratosthenes comes in with his brilliant "sieve" method. Think of it like a strainer:

Imagine you have a list of all numbers up to n-1. Initially, assume they are all prime.
Start with the first prime number, 2.
Aha! If 2 is prime, then all its multiples (4, 6, 8, 10, ...) cannot be prime! Let's mark them as non-prime.
Move to the next unmarked number. That's 3.
Aha again! If 3 is unmarked, it must be prime. All its multiples (6, 9, 12, 15, ...) cannot be prime. Mark them off! (Note: 6 was already marked by 2, which is fine.)
Continue this process. The numbers that remain unmarked must be prime.

This is the Sieve of Eratosthenes, and it's super efficient for finding all primes up to a given limit!

Approach: Sieving Our Way to Primes

Let's formalize the Sieve of Eratosthenes step-by-step:

Initialize a boolean array: Create an array, let's call it is_prime, of size n. Initialize all its elements to true. is_prime[i] will be true if i is considered prime, and false otherwise.
Handle Base Cases:
- Numbers 0 and 1 are not prime. So, set is_prime[0] = false and is_prime[1] = false.
The Sieving Process:
- Loop through numbers p starting from 2 up to sqrt(n). Why sqrt(n)? Because if a number k has a prime factor larger than sqrt(k), it must also have a prime factor smaller than sqrt(k). So, by the time we reach sqrt(n), all composite numbers less than n will have already been marked by their smaller prime factors.
- Inside this loop, check if is_prime[p] is true.
  - If is_prime[p] is true, it means p is a prime number.
  - Now, mark all multiples of p as not prime. Start marking from p * p up to n-1, with increments of p.
    - Why start from p * p? Because any multiple k * p where k < p would have already been marked by a smaller prime factor k. For example, when p=3, we don't need to mark 3*2=6 because 6 would have already been marked when p=2. We only need to mark 3*3=9, 3*4=12, and so on.
Count the Primes:
- After the sieving process is complete, iterate through the is_prime array from index 2 up to n-1.
- Count how many is_prime[i] values are still true. This count is your answer!

Let's walk through n = 10 again with the Sieve:

is_prime array of size 10: [T, T, T, T, T, T, T, T, T, T]
Mark 0 and 1 as false: [F, F, T, T, T, T, T, T, T, T]
Sieving Loop (p up to sqrt(10) ≈ 3):
- p = 2:
  - is_prime[2] is T. So, 2 is prime.
  - Mark multiples of 2 starting from 2*2=4:
    - is_prime[4] = F
    - is_prime[6] = F
    - is_prime[8] = F
  - Array becomes: [F, F, T, T, F, T, F, T, F, T]
- p = 3:
  - is_prime[3] is T. So, 3 is prime.
  - Mark multiples of 3 starting from 3*3=9:
    - is_prime[9] = F
  - Array becomes: [F, F, T, T, F, T, F, T, F, F]
Loop ends (next p would be 4, 4 > sqrt(10)).
Count: Iterate from i = 2 to 9:
- is_prime[2] is T (count = 1)
- is_prime[3] is T (count = 2)
- is_prime[5] is T (count = 3)
- is_prime[7] is T (count = 4)
- Total count: 4. Perfect!

Code 🧑‍💻

Here's the C implementation of the Sieve of Eratosthenes:

#include <stdbool.h> // For boolean type
#include <stdlib.h>  // For malloc

int countPrimes(int n) {
    // Handle edge cases where n is too small to contain any primes
    if (n <= 2) {
        return 0;
    }

    // Create a boolean array `is_prime` of size `n`
    // Initialize all entries as true. A value of true at `is_prime[i]`
    // will mean that i is potentially prime.
    bool *is_prime = (bool *)malloc(sizeof(bool) * n);
    if (is_prime == NULL) {
        // Handle memory allocation failure
        return -1; // Or throw an error, depending on desired behavior
    }

    for (int i = 0; i < n; i++) {
        is_prime[i] = true;
    }

    // 0 and 1 are not prime numbers
    is_prime[0] = false;
    is_prime[1] = false;

    // Start the Sieve process from p = 2
    // We only need to iterate up to sqrt(n)
    // Note: The loop condition `p * p < n` works because if `p` exceeds `sqrt(n)`,
    // then `p*p` would exceed `n`.
    for (int p = 2; p * p < n; p++) {
        // If is_prime[p] is still true, then it is a prime number
        if (is_prime[p]) {
            // Mark all multiples of p as not prime.
            // Start from p*p, because smaller multiples (like 2*p, 3*p, etc.)
            // would have already been marked by their smaller prime factors (2, 3, etc.).
            for (int i = p * p; i < n; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Count all prime numbers
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) {
            count++;
        }
    }

    // Free the dynamically allocated memory
    free(is_prime);
    is_prime = NULL; // Good practice to set pointer to NULL after freeing

    return count;
}

Time & Space Complexity Analysis

Understanding how efficient our algorithm is crucial in competitive programming.

Time Complexity: O(n log log n)
- The outer loop runs up to sqrt(n).
- The inner loop (marking multiples) runs for n/p times for each prime p.
- The total number of operations is approximately n/2 + n/3 + n/5 + ... for all primes p up to n. This sum is mathematically proven to be O(n log log n).
- For n = 5 * 10^6, log log n is a very small factor (around 2-3). This makes the Sieve extremely fast, almost linear O(n). Much better than O(n * sqrt(n))!
Space Complexity: O(n)
- We use a boolean array is_prime of size n to store the primality status of each number. This requires n boolean values, leading to O(n) space complexity.

Key Takeaways

Sieve of Eratosthenes: This is the go-to algorithm for finding all prime numbers up to a given limit n. Memorize its logic!
Optimization is Key: The naive approach is easy to think of but too slow for larger inputs. Understanding how to optimize, like marking multiples instead of repeated division checks, is fundamental.
Square Root Optimization: The p * p < n (or p < sqrt(n)) condition for the outer loop is a common optimization trick in primality tests and sieving algorithms.
Memory Management (C/C++): Remember to malloc memory for dynamic arrays and free it when you're done to prevent memory leaks!

And that's it! You've successfully conquered the Count Primes problem using a powerful and elegant algorithm. Give yourself a pat on the back!

Authored by Vansh2710 | Published: 2026-04-02 23:19:43

LeetCode Solution: 204. Count Primes

Vansh Aggarwal — Thu, 02 Apr 2026 17:44:46 +0000

Master the Sieve! Counting Primes Efficiently (LeetCode 204)

Hey there, aspiring competitive programmer! 👋 Vansh here, ready to tackle another classic LeetCode problem that's super common in interviews and a fantastic way to learn about algorithm optimization. Today, we're diving into problem 204: "Count Primes."

Don't let the name scare you! Prime numbers might sound complex, but the core idea is simple, and the trick to solving this efficiently is a beautiful algorithm called the Sieve of Eratosthenes. Let's unravel it together!

🌟 The Problem: Simple Yet Tricky!

Problem Statement: Given an integer n, your task is to return the count of prime numbers that are strictly less than n.

Wait, what's a prime number?
Great question! A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Examples of primes: 2, 3, 5, 7, 11, 13, ...
Examples of non-primes (composite numbers): 4 (divisible by 2), 6 (divisible by 2, 3), 9 (divisible by 3), ...
Important: 0 and 1 are not considered prime numbers.

Let's look at the examples given:

Example 1: n = 10
- Numbers strictly less than 10 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- Out of these, the primes are: 2, 3, 5, 7.
- Output: 4
Example 2: n = 0
- No numbers are strictly less than 0.
- Output: 0
Example 3: n = 1
- No numbers are strictly less than 1 that can be prime.
- Output: 0

The constraints tell us n can be up to 5 * 10^6. This hints that a simple, brute-force check for primality for every number won't be fast enough. We need something clever!

🤔 Intuition: From Brute-Force to "Aha!"

My first thought for checking if a number k is prime is to try dividing k by every number from 2 up to sqrt(k). If none of them divide k evenly, then k is prime.

If we apply this for every number from 2 up to n-1:

count = 0
for i from 2 to n-1:
    if isPrime(i):
        count++
return count

And isPrime(i) itself involves a loop. This approach quickly becomes too slow when n gets large (like 5 * 10^6). Think about it: for n=5*10^6, we'd be calling isPrime millions of times, and each call can involve thousands of divisions. 🐌

The "Aha!" Moment: Don't Repeat Work!

What if, instead of repeatedly checking divisibility, we could somehow mark non-prime numbers as we discover them?

Consider the number 2. It's prime!
Now, any multiple of 2 (4, 6, 8, 10, 12, ...) cannot be prime, because they are all divisible by 2. So, we can just mark them as not prime.

Next, consider 3. It's prime!
Any multiple of 3 (6, 9, 12, 15, ...) cannot be prime. We can mark them. (Notice 6 was already marked by 2 – that's fine!)

This filtering process, where you start with an assumption (all numbers are prime) and then systematically cross out multiples of known primes, is exactly what the Sieve of Eratosthenes does! It's like sifting flour – you start with everything and shake out the unwanted bits.

🚀 The Approach: Sieve of Eratosthenes Step-by-Step

The Sieve of Eratosthenes is an ancient and incredibly efficient algorithm for finding all prime numbers up to any given limit. Here's how we'll implement it:

Initialize a "Primes" List:
- Create a boolean array (or vector) called isPrime of size n.
- Initialize all entries to true. This means we initially assume all numbers from 0 to n-1 are prime.
Handle Non-Primes (0 and 1):
- We know 0 and 1 are not prime. So, immediately set isPrime[0] = false and isPrime[1] = false.
Sieve Process:
- Start a loop from p = 2 (the first prime number). This loop will go up to sqrt(n-1). Why sqrt(n-1)? Because if a number X has a divisor d > sqrt(X), then it must also have a divisor X/d < sqrt(X). So, we only need to check for prime factors up to the square root. Any composite number X will have already been marked false by one of its prime factors p <= sqrt(X).
- Inside the loop (for p):
  - Check if isPrime[p] is still true. If it is, p is a prime number!
  - Now, p is prime, so all its multiples are composite (not prime). We need to mark them as false.
  - Start another inner loop from i = p * p up to n-1, incrementing i by p (i += p).
    - Set isPrime[i] = false.
    - Why start from p * p? All multiples of p smaller than p * p (i.e., 2*p, 3*p, ..., (p-1)*p) would have already been marked by smaller prime factors. For example, 2*p would have been marked by 2, 3*p by 3, and so on. So, p*p is the first multiple that might not have been marked yet.
Count the Primes:
- After the sieving process is complete, iterate through the isPrime array from p = 2 up to n-1.
- For every index p where isPrime[p] is true, increment a count variable.
Return the Count:
- The final count is your answer!

Let's walk through n = 10 using this approach:

isPrime array of size 10: [T, T, T, T, T, T, T, T, T, T]
Mark 0 and 1: [F, F, T, T, T, T, T, T, T, T]
Sieve Loop (p from 2 up to sqrt(9) = 3):
- p = 2: isPrime[2] is T. So, 2 is prime!
  - Mark multiples of 2 from 2*2=4 up to 9 as F:
  - isPrime[4]=F, isPrime[6]=F, isPrime[8]=F
  - isPrime becomes: [F, F, T, T, F, T, F, T, F, T]
- p = 3: isPrime[3] is T. So, 3 is prime!
  - Mark multiples of 3 from 3*3=9 up to 9 as F:
  - isPrime[9]=F
  - isPrime becomes: [F, F, T, T, F, T, F, T, F, F]
- Loop ends because p would be 4, which is > sqrt(9).
Count Primes:
- isPrime[2] is T -> count = 1
- isPrime[3] is T -> count = 2
- isPrime[4] is F
- isPrime[5] is T -> count = 3
- isPrime[6] is F
- isPrime[7] is T -> count = 4
- isPrime[8] is F
- isPrime[9] is F
Return: 4. Perfect!

💻 Solution Code (C)

#include <stdbool.h>
#include <stdlib.h> // For malloc and free

int countPrimes(int n) {
    // Edge cases: 0, 1, 2 have no primes strictly less than them
    if (n <= 2) {
        return 0;
    }

    // 1. Initialize a boolean array 'isPrime' of size 'n'
    // and assume all numbers are prime initially.
    // Calloc initializes memory to zero (false for boolean)
    // We want true, so let's use malloc and then fill.
    bool* isPrime = (bool*)malloc(n * sizeof(bool));
    if (isPrime == NULL) {
        // Handle memory allocation failure
        return 0; // Or some error code
    }

    for (int i = 0; i < n; i++) {
        isPrime[i] = true;
    }

    // 2. Mark 0 and 1 as not prime
    isPrime[0] = false;
    isPrime[1] = false;

    // 3. Sieve Process
    // Loop from p = 2 up to sqrt(n-1)
    // p*p <= n is equivalent to p <= sqrt(n)
    for (long long p = 2; p * p < n; p++) {
        // If isPrime[p] is still true, then p is a prime number
        if (isPrime[p]) {
            // Mark all multiples of p as not prime
            // Start from p*p, as smaller multiples would have already been marked
            for (long long i = p * p; i < n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // 4. Count the primes
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }

    // Free the dynamically allocated memory
    free(isPrime);
    isPrime = NULL;

    // 5. Return the total count
    return count;
}

⏰ Time & Space Complexity Analysis

Time Complexity: O(n log log n)
- Initializing the isPrime array takes O(n) time.
- The outer loop runs up to sqrt(n).
- The inner loop (marking multiples) is the key. For each prime p, it performs n/p operations.
- The sum of n/p for all primes p up to n is approximately n * (1/2 + 1/3 + 1/5 + ...) which is O(n log log n). This is highly efficient and much faster than O(n * sqrt(n))!
- Counting the primes takes O(n).
- Overall, the dominant factor is O(n log log n).
Space Complexity: O(n)
- We use a boolean array isPrime of size n to store the primality status of each number. This takes O(n) space. For n = 5 * 10^6, this is about 5 megabytes, which is perfectly acceptable.

🔑 Key Takeaways

Don't Brute-Force Primality for Ranges: If you need to find many primes up to a certain limit, the Sieve of Eratosthenes is almost always the way to go. Checking primality for each number individually is inefficient.
Sieve of Eratosthenes: Understand its core idea: start with all numbers as potentially prime, then systematically eliminate multiples of known primes.
Optimization p * p: Starting the marking of multiples from p * p is a crucial optimization. It avoids redundant work because smaller multiples would have already been marked by smaller prime factors.
Time Efficiency: The O(n log log n) complexity makes the Sieve extremely powerful for large inputs.
Memory Management (C/C++): Remember to malloc memory for dynamic arrays and free it after you're done to prevent memory leaks!

This problem is a fantastic entry point into number theory algorithms and demonstrates how a clever insight can dramatically improve performance. Keep practicing, and you'll be a master of these techniques in no time! Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-02 23:14:04

LeetCode Solution: 240. Search a 2D Matrix II

Vansh Aggarwal — Tue, 31 Mar 2026 18:51:35 +0000

Search a 2D Matrix II: The Clever Corner Approach You Need to Know!

Hey there, fellow coders! 👋 Vansh here, diving into another LeetCode adventure that looks tricky on the surface but has a surprisingly elegant solution. Today, we're tackling LeetCode 240: Search a 2D Matrix II.

This problem is a classic for a reason – it tests your ability to think outside the box and leverage unique properties of the input. If you've ever felt stuck with matrices, this one's a fantastic stepping stone! Let's unravel this mystery together.

The Problem: Finding Your Way in a Double-Sorted Grid

Imagine you have a large grid of numbers, like a spreadsheet. This isn't just any grid, though; it has two very special properties:

Rows are Sorted: If you look at any single row, the numbers go from smallest on the left to largest on the right.
Columns are Sorted: If you look at any single column, the numbers go from smallest at the top to largest at the bottom.

Your task? Given this special matrix and a target number, you need to efficiently determine if the target exists anywhere in the matrix.

Let's look at an example to make it super clear:

Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true (You can see 5 is right there in the second row, second column!)

Example 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false (If you scan through, 20 isn't present in this matrix.)

The key here is "efficiently". A brute-force search (checking every single number) would work, but can we do better? Given the sorted nature, probably!

Intuition: Where to Start Looking?

When dealing with sorted data, binary search often comes to mind. You could run a binary search on each row, but that would be O(m * log n) (m rows, log n for each search). Can we do even better?

The real "aha!" moment comes when you realize that both sorting properties give us powerful information. Where in the matrix can we start such that if we compare our current number to the target, we can eliminate a significant portion of the search space?

Consider the four corners:

Top-Left (smallest): If matrix[0][0] is too big, we can't eliminate anything useful. If it's too small, we don't know if we should go right or down. Not ideal.
Bottom-Right (largest): Similar problem. If matrix[m-1][n-1] is too small, we don't know where to go.
Top-Right (mix of small and large): Ah, this is interesting!
- If matrix[0][n-1] is equal to target, we found it!
- If matrix[0][n-1] is greater than target, what does that tell us? Since this is the largest element in its row, and all elements below it in its column are even larger, we know target cannot be in the current column (or any element below the current position). So, we can safely move left to a smaller column!
- If matrix[0][n-1] is less than target, what now? Since this is the smallest element at the end of its column, and all elements to its left in the current row are even smaller, we know target cannot be in the current row (or any element to the left of the current position). So, we can safely move down to a larger row!
Bottom-Left (mix of small and large): This corner also works with similar logic! (Try it out as an exercise!)

The top-right (or bottom-left) corner provides a perfect pivot point. From here, each comparison allows us to eliminate either a full row or a full column! This is incredibly efficient.

Approach: The "Staircase" Search

Let's formalize the top-right corner approach:

Start at the Top-Right: Initialize two pointers, rowIndex = 0 (first row) and colIndex = n - 1 (last column).
Iterate and Compare: While rowIndex is within the matrix bounds (rowIndex < m) AND colIndex is within the matrix bounds (colIndex >= 0):
- Let currentElement = matrix[rowIndex][colIndex].
- Case 1: currentElement == target: We found our number! Return true.
- Case 2: currentElement < target: The currentElement is too small. Since all elements to the left in the current row are even smaller, and we need a larger value, the target cannot be in the current row (left of currentElement). We need to search in rows with potentially larger values. So, we move down to the next row: rowIndex++.
- Case 3: currentElement > target: The currentElement is too large. Since all elements below in the current column are even larger, and we need a smaller value, the target cannot be in the current column (below currentElement). We need to search in columns with potentially smaller values. So, we move left to the previous column: colIndex--.
Target Not Found: If our loop finishes (either rowIndex goes out of bounds or colIndex goes out of bounds), it means we've exhausted all possible search paths without finding the target. Return false.

This strategy looks like climbing down a staircase (or moving along a diagonal path), eliminating chunks of the matrix with each step.

Code: Bringing the Strategy to Life

Here's the Python implementation of our "staircase" search:

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        # Handle edge cases: empty matrix or empty rows
        if not matrix or not matrix[0]:
            return False

        rows = len(matrix)
        cols = len(matrix[0])

        # Start from the top-right corner
        # row pointer starts at the first row (index 0)
        # col pointer starts at the last column (index cols - 1)
        rowIndex = 0
        colIndex = cols - 1

        # Continue search as long as we are within matrix boundaries
        while rowIndex < rows and colIndex >= 0:
            element = matrix[rowIndex][colIndex] # Get the current element

            if element == target:
                # Target found!
                return True
            elif element < target:
                # Current element is too small.
                # Since rows are sorted left-to-right, all elements to the left
                # in the current row are even smaller.
                # Since columns are sorted top-to-bottom, we need to go down
                # to potentially find larger values.
                rowIndex += 1
            else: # element > target
                # Current element is too large.
                # Since columns are sorted top-to-bottom, all elements below
                # in the current column are even larger.
                # Since rows are sorted left-to-right, we need to go left
                # to potentially find smaller values.
                colIndex -= 1

        # If the loop finishes, the target was not found in the matrix
        return False

Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(m + n)
- In the worst-case scenario, our pointers rowIndex or colIndex will traverse at most m rows and n columns, respectively.
- At each step, we either increment rowIndex or decrement colIndex, effectively reducing the search space.
- We don't revisit cells or iterate over an entire row/column in each step. The total number of steps is proportional to m + n.
- This is significantly better than O(m * n) (brute force) or O(m * log n) (binary search on each row).
Space Complexity: O(1)
- We only use a few extra variables (rows, cols, rowIndex, colIndex, element) to store pointers and the current value.
- This constant amount of extra space means our solution is very memory-efficient.

Key Takeaways

This problem is a fantastic lesson in algorithmic thinking:

Leverage Properties: Always look for unique properties in your input data (like the double-sorted nature here). These properties are hints for more efficient algorithms.
Eliminate Search Space: The core idea of many efficient algorithms is to eliminate as much of the potential search space as possible with each decision.
Optimal Starting Points: The choice of where to start your search can drastically impact the algorithm's efficiency. Corners, especially top-right or bottom-left in this type of matrix, are often powerful pivot points.
Think Diagonally: Sometimes the best path through a 2D structure isn't horizontal or vertical, but diagonal!

Hope you enjoyed this dive into LeetCode 240! This problem is a great example of how a clever starting point and a simple set of rules can lead to a highly optimized solution. Keep practicing, and happy coding!

Authored by Vansh2710 | Published: 2026-04-01 00:20:33