DEV Community: Vansh Aggarwal

LeetCode Solution: 263. Ugly Number

Vansh Aggarwal — Sat, 23 May 2026 19:55:31 +0000

Demystifying Ugly Numbers: A LeetCode Adventure (Problem 263)

Hey fellow coders and aspiring problem-solvers! 👋 Vansh2710 here, ready to dive into another fun and beginner-friendly LeetCode challenge. Today, we're tackling Problem 263: Ugly Number. Don't let the name scare you; these "ugly" numbers are quite elegant once you understand them!

This problem is a fantastic way to practice basic arithmetic operations and while loops, laying a solid foundation for more complex algorithms. So, grab your favorite beverage, and let's unravel the mystery of ugly numbers together!

🧐 What Exactly is an Ugly Number?

The problem defines an ugly number as a positive integer whose prime factors are only 2, 3, and 5.

Let's break that down:

Positive Integer: This means we're only looking at numbers like 1, 2, 3, 4, 5, etc. Zero and negative numbers are not considered ugly.
Prime Factors: These are the prime numbers that multiply together to make up the original number. For example, the prime factors of 12 are 2, 2, and 3 (since 2 * 2 * 3 = 12).
Only 2, 3, and 5: This is the crucial part! If a number has any other prime factor (like 7, 11, 13, etc.), it's NOT an ugly number.

Let's look at the examples:

n = 6
- Prime factors of 6 are 2 and 3.
- Both 2 and 3 are allowed prime factors (from the set {2, 3, 5}).
- Therefore, 6 is an ugly number. (Output: true)
n = 1
- 1 has no prime factors (it's a special case, considered "vacuously" true because it has no prime factors that aren't 2, 3, or 5).
- Therefore, 1 is an ugly number. (Output: true)
n = 14
- Prime factors of 14 are 2 and 7.
- While 2 is allowed, 7 is not in our allowed set {2, 3, 5}.
- Therefore, 14 is NOT an ugly number. (Output: false)

🤔 The "Aha!" Moment - Intuition

How can we programmatically check if a number only has 2, 3, and 5 as prime factors?

Imagine you have a number, say 30.

Is it divisible by 2? Yes! 30 / 2 = 15. Now our number is 15.
Is 15 divisible by 2? No.
Is 15 divisible by 3? Yes! 15 / 3 = 5. Now our number is 5.
Is 5 divisible by 2? No.
Is 5 divisible by 3? No.
Is 5 divisible by 5? Yes! 5 / 5 = 1. Now our number is 1.

We've successfully reduced 30 to 1 by only dividing by 2, 3, and 5. This tells us that 30 is an ugly number!

What if we had 14?

Is it divisible by 2? Yes! 14 / 2 = 7. Now our number is 7.
Is 7 divisible by 2? No.
Is 7 divisible by 3? No.
Is 7 divisible by 5? No.

At this point, our number (7) is still greater than 1, but it's not divisible by any of our allowed prime factors (2, 3, 5). This means 7 itself must be a prime factor that is not 2, 3, or 5. Therefore, 14 is not an ugly number.

The core intuition is: If a number n is ugly, we should be able to keep dividing it by 2, 3, or 5 until it eventually becomes 1. If at any point, n is greater than 1 but not divisible by any of these three primes, then it must have another prime factor, making it not ugly.

🚀 Step-by-Step Approach

Handle Edge Cases:
- According to the definition, ugly numbers must be positive integers. So, if n is 0 or negative, it's immediately false.
- The number 1 is a special case. It has no prime factors, so it satisfies the condition. Our loop-based approach will correctly handle this as n=1 will not enter the while(n > 1) loop and directly return true.
Iterative Division:
- We'll use a while loop that continues as long as n is greater than 1. The goal is to reduce n to 1.
- Inside the loop, we check for divisibility by 2, 3, and 5. The order doesn't strictly matter, but a consistent order (e.g., 2, then 3, then 5) is clean.
- If n is divisible by 2: Divide n by 2 (n = n / 2). We've factored out a '2'.
- Else if n is divisible by 3: Divide n by 3 (n = n / 3). We've factored out a '3'.
- Else if n is divisible by 5: Divide n by 5 (n = n / 5). We've factored out a '5'.
- Else (Crucial Check): If n is not divisible by 2, 3, or 5 at this point, but it's still greater than 1, it means n must have a prime factor other than 2, 3, or 5. In this scenario, n is not an ugly number, so we immediately return false.
Final Result:
- If the while loop finishes (meaning n has been successfully reduced to 1), it implies that all its prime factors were indeed 2, 3, or 5. In this case, we return true.

💻 The Code

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

class Solution {
public:
    bool isUgly(int n) {

        // Handle non-positive numbers: Ugly numbers are positive.
        if (n <= 0) {
            return false;
        }

        // Loop while n is greater than 1.
        // We aim to reduce n to 1 by dividing out factors of 2, 3, and 5.
        while (n > 1) {

            // Try dividing by 2
            if (n % 2 == 0) {
                n = n / 2;
            }
            // Else, try dividing by 3
            else if (n % 3 == 0) {
                n = n / 3;
            }
            // Else, try dividing by 5
            else if (n % 5 == 0) {
                n = n / 5;
            }
            // If n is not divisible by 2, 3, or 5, and it's still > 1,
            // then it must have a prime factor other than 2, 3, or 5.
            else {
                return false; // Not an ugly number
            }
        }

        // If the loop completes, it means n was successfully reduced to 1,
        // implying all its prime factors were 2, 3, or 5.
        // Also handles the case n = 1 initially (loop won't run, returns true).
        return true;
    }
};

⏱️ Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(log n)
- In each iteration of the while loop, we divide n by at least 2 (if it's divisible by 2, 3, or 5).
- This means n decreases exponentially, similar to how many times you can divide a number by 2 until it reaches 1 (e.g., log_2(n)).
- Therefore, the number of operations is proportional to the logarithm of n. For example, if n is 2^30, it takes about 30 divisions.
Space Complexity: O(1)
- We are only using a few constant variables (n). We are not allocating any additional data structures whose size depends on the input n.

💡 Key Takeaways

Iterative Reduction: Many problems can be solved by iteratively reducing the input towards a base case. Here, we reduce n to 1.
Handling Edge Cases: Always consider special inputs like 0, 1, and negative numbers.
Prime Factorization Logic: This problem teaches a fundamental approach to checking prime factors. If you can divide out all known prime factors (2, 3, 5) and the number reduces to 1, then it's composed only of those factors. If it stops reducing and is still > 1, it has other factors.
The "Else" Clause is Key: The else { return false; } inside the loop is critical for identifying numbers with forbidden prime factors.

That's it for Ugly Numbers! This problem is a great example of how simple arithmetic operations can be combined to solve interesting challenges. I hope you found this explanation clear and helpful.

Happy coding, and see you in the next one!

Author Account: Vansh2710
Time Published: 2026-05-24 01:25:09

LeetCode Solution: 1752. Check if Array Is Sorted and Rotated

Vansh Aggarwal — Sat, 23 May 2026 18:17:13 +0000

🔄 LeetCode 1752: Can You Un-Rotate This Array? (A Beginner's Guide)

Hey there, fellow coders! 👋 Vansh2710 here, ready to demystify another exciting LeetCode challenge. Today, we're tackling problem 1752: "Check if Array Is Sorted and Rotated." Sounds a bit like a puzzle, right? Don't worry, we'll break it down piece by piece and uncover a super elegant solution!

This problem is a fantastic way to sharpen your array manipulation and logical thinking skills. It might seem tricky at first, but with a simple trick, it becomes incredibly straightforward. Let's dive in!

What's the Problem All About? 🧐

Imagine you have a perfectly sorted list of numbers, like [1, 2, 3, 4, 5].
Now, imagine you rotate it. This means you take some elements from the beginning and move them to the end, keeping their relative order.

For example, if you rotate [1, 2, 3, 4, 5] by 2 positions:

[1, 2, 3, 4, 5]
Take 1, 2 and move them to the end: [3, 4, 5, 1, 2]

The problem asks: Given an array nums, can we tell if it could have been originally sorted (non-decreasingly) and then rotated some number of times (even zero rotations)?

Key things to remember:

Non-decreasing order: [1, 2, 2, 3] is sorted. [3, 2, 1] is not.
Rotation: Can be any number of positions, including 0 (no rotation).
Duplicates are allowed: This is an important detail! [3, 4, 5, 5, 1, 2] could be [1, 2, 3, 4, 5, 5] rotated.

Let's look at examples:

nums = [3, 4, 5, 1, 2]
- Is [1, 2, 3, 4, 5] sorted? Yes.
- Can [1, 2, 3, 4, 5] be rotated to get [3, 4, 5, 1, 2]? Yes, rotate by 2 positions.
- Output: true
nums = [2, 1, 3, 4]
- If sorted, it would be [1, 2, 3, 4].
- Can [1, 2, 3, 4] be rotated to [2, 1, 3, 4]? No. The 2, 1 part breaks the sorted order that a single rotation would maintain.
- Output: false
nums = [1, 2, 3]
- Is it sorted? Yes.
- Can it be rotated to get [1, 2, 3]? Yes, 0 rotations.
- Output: true

The "Aha!" Moment - Our Intuition ✨

Think about a truly sorted array like [1, 2, 3, 4, 5]. If you go from left to right, nums[i-1] is always less than or equal to nums[i]. There are no "drops" or "descents" in value.

Now, consider a rotated sorted array: [3, 4, 5, 1, 2].
If you scan this, you'll see:

3 <= 4 (OK)
4 <= 5 (OK)
5 > 1 (AHA! A descent!)
1 <= 2 (OK)

Notice something? There's only one place where the non-decreasing order is broken: 5 followed by 1. This "break" is exactly where the rotation happened! The elements [1, 2] were moved from the beginning to the end, creating this single drop in value.

What if there are two descents? For example, [2, 1, 3, 4].

2 > 1 (Descent 1)
1 <= 3 (OK)
3 <= 4 (OK) Here, we have one descent. What about the wrap-around? 4 > 2? No. Actually, if the original array was [1,2,3,4], and we rotated it, we would never get [2,1,3,4]. A single rotation implies that all elements after the rotation point are smaller than all elements before it. The only "break" can be at the rotation point.

So, the core intuition is: A sorted and rotated array will have at most ONE "descent" (where nums[i-1] > nums[i]) when you iterate through it.

Wait, what about the wrap-around?
Consider [4, 5, 1, 2, 3].
4 <= 5 (OK)
5 > 1 (Descent!)
1 <= 2 (OK)
2 <= 3 (OK)
Here, we have one descent. But also, nums[n-1] (which is 3) is less than nums[0] (which is 4). This comparison also forms part of the "break" in sorted order, conceptually wrapping around the array. Our descent counter needs to account for this.

Revised Intuition: Count the number of times nums[i-1] > nums[i]. This count should be at most 1, including the wrap-around comparison between the last and first elements.

Step-by-Step Approach 🚶‍♂️

Let's formalize our intuition into a clear algorithm:

Initialize a counter: We'll need a variable, let's call it descentCount, and set it to 0. This counter will track how many times we find nums[i-1] > nums[i].
Iterate through the array: Loop from the second element (i = 1) up to the end of the array (nums.size() - 1).
- In each iteration, compare the current element (nums[i]) with the previous one (nums[i-1]).
- If nums[i-1] > nums[i], it means we've found a "descent" or a break in the non-decreasing order. Increment descentCount.
Check the wrap-around case: After the loop finishes, we need to consider the connection between the last element and the first element. In a rotated sorted array, if there was a rotation, the last element might be greater than the first element (e.g., in [3, 4, 5, 1, 2], nums[4] (which is 2) is less than nums[0] (which is 3). This doesn't add a descent.
However, in [1,2,3] (0 rotations), nums[2] (3) is greater than nums[0] (1).
Let's re-evaluate: The descent is where the sequence decreases.
- [3, 4, 5, 1, 2] -> 5 > 1 (1 descent)
  - nums[n-1] (2) is not greater than nums[0] (3).
- [1, 2, 3] -> No descents.
  - nums[n-1] (3) is not greater than nums[0] (1).
- [2, 1, 3, 4] -> 2 > 1 (1 descent)
  - nums[n-1] (4) is not greater than nums[0] (2).
My logic for the wrap-around check in the solution code is if (nums[n-1] > nums[0]). Let's trace it with examples:
- [3,4,5,1,2] (n=5)
  - Loop: (5 > 1) -> descentCount = 1
  - Wrap-around: nums[4] (2) > nums[0] (3) is false.
  - Total descentCount = 1. Return true. Correct.

*   `[2,1,3,4]` (n=4)
    *   Loop: `(2 > 1)` -> `descentCount = 1`
    *   Wrap-around: `nums[3]` (4) `>` `nums[0]` (2) is `true`. -> `descentCount = 2`.
    *   Total `descentCount = 2`. Return `false`. Correct. (Because original `[1,2,3,4]` cannot be rotated to `[2,1,3,4]`. It has two "breaks" if you consider it circular: `2->1` and `4->2` (conceptual circular link)).

*   `[1,2,3]` (n=3)
    *   Loop: No descents. `descentCount = 0`.
    *   Wrap-around: `nums[2]` (3) `>` `nums[0]` (1) is `true`. -> `descentCount = 1`.
    *   Total `descentCount = 1`. Return `true`. Correct. (A sorted array is considered a 0-rotated sorted array).

This wrap-around check for `nums[n-1] > nums[0]` cleverly handles the case where the "rotation point" effectively exists between the last and first element *if the array was originally sorted*. If `[1,2,3]` is seen as `1,2,3,1` (circular), then `3 > 1` is a descent. This means a perfectly sorted array will register 1 descent with this method.

Final Check: After iterating through the array and checking the wrap-around, if descentCount is less than or equal to 1, it means the array could have been sorted and rotated. Return true. Otherwise, if descentCount is greater than 1, it means there are too many "breaks" in the sorted order for it to be a single rotation of a sorted array. Return false.

Show Me the Code! 💻

Here's the C++ implementation of this logic:

#include <vector> // Don't forget to include necessary headers!
#include <iostream> // For potential testing, though not strictly part of the solution

class Solution {
public:
    bool check(std::vector<int>& nums) {
        int count = 0; // Initialize descent counter
        int n = nums.size(); // Get the size of the array

        // Iterate from the second element to compare with the previous
        for (int i = 1; i < n; i++) {
            // If the previous element is greater than the current, it's a descent
            if (nums[i-1] > nums[i]) {
                count++;
            }
        }

        // Handle the wrap-around case: compare the last element with the first
        // If nums[n-1] is greater than nums[0], it means a "descent" occurs
        // conceptually between the end and the beginning of the array.
        // E.g., for [1,2,3], nums[2](3) > nums[0](1) is true.
        // For [3,4,5,1,2], nums[4](2) > nums[0](3) is false.
        if (nums[n-1] > nums[0]) {
            count++;
        }

        // A sorted and rotated array can have at most one "descent" (break).
        // This includes the wrap-around check, meaning a perfectly sorted array
        // will result in count = 1 due to the wrap-around check.
        return count <= 1;
    }
};

Complexity Analysis ⏱️🚀

Let N be the number of elements in the nums array.

Time Complexity: O(N)
- We iterate through the array once in the for loop, which takes O(N) time.
- All other operations (initialization, size() call, final comparison) take constant time, O(1).
- Therefore, the total time complexity is dominated by the loop, making it O(N). This is highly efficient as we only need to pass through the array once.
Space Complexity: O(1)
- We only use a few extra variables (count, n, i) to store our state, regardless of the input array size.
- No auxiliary data structures (like new arrays or hash maps) are used that scale with the input size.
- Thus, the space complexity is constant, O(1).

Key Takeaways ✨

Spotting the "Breaks": The most crucial insight is that a sorted and rotated array will have at most one point where the non-decreasing order is violated.
The Wrap-Around is Tricky: Don't forget the connection between the last element and the first! This is where many solutions go wrong. Our approach correctly includes this as another potential "descent."
Simple is Often Best: This problem could tempt you into complex sorting or array manipulation, but a single pass and a counter prove to be the most elegant and efficient solution.

This approach is clean, efficient, and demonstrates a good understanding of array properties! Keep practicing, and you'll master these patterns in no time. Happy coding!

Author Account: Vansh2710
Time Published: 2026-05-23 23:46:54

LeetCode Solution: Test

Vansh Aggarwal — Sat, 23 May 2026 17:15:02 +0000

Test

Hello, fellow coders!

Today, we're diving into what might seem like the simplest LeetCode problem ever, but don't let its simplicity fool you. It's a fantastic way to reinforce the absolute basics of problem-solving, function definition, and even complexity analysis. Sometimes, the best way to get started is by mastering the fundamentals!

Problem Explanation

You are tasked with creating a function that, when called, prints the integer 1 to the standard output.

Here are the constraints:

The function should not take any arguments.
The function does not need to return any value explicitly. Its primary purpose is the side-effect of printing.

Yes, you read that right. Your mission, should you choose to accept it, is to make your program say "1"!

Intuition

At first glance, this problem might make you chuckle. "Just print 1? Is that it?" And honestly, yes, that's pretty much it! The "aha!" moment here isn't about some complex algorithm or data structure. It's about recognizing that sometimes, the problem statement literally gives you the answer.

The key intuition is to:

Understand the direct instruction: The problem explicitly states "print the integer 1."
Identify the tool: Every programming language has a way to output text or numbers to the console (e.g., print() in Python, console.log() in JavaScript, System.out.println() in Java).
Structure it as a function: LeetCode problems usually require you to implement a function, so wrap your direct instruction inside one.

This problem is a gentle reminder that not every challenge requires advanced techniques; some just test your ability to read instructions and use basic language features.

Approach

Let's break down the incredibly complex steps (just kidding, it's super straightforward!):

Define a Function: We need to create a function structure. Let's name it something simple like solve or print_one. Since the problem specifies no arguments, our function signature will reflect that.
Print the Integer: Inside this function, we will use our chosen programming language's standard output command to display the integer 1.
No Return Value (Explicitly): Since the problem asks us to print and not return, our function doesn't strictly need a return statement. In many languages, a function without an explicit return will implicitly return None or undefined, which is perfectly fine for this problem.

That's it! Three simple steps to conquer the "print 1" challenge.

Code

Here's the Python solution following our approach:

def solve():
    """
    This function prints the integer 1 to the console.
    It takes no arguments and returns nothing explicitly.
    """
    print(1)

# Example of how you would call the function:
# solve() # This would print '1' to your console

Time & Space Complexity Analysis

Even for the simplest problems, analyzing complexity is a great habit to build!

Time Complexity: O(1)
- The function performs a single, constant-time operation: printing an integer. This operation doesn't depend on any input size (as there is no input to begin with!), so its execution time remains constant regardless of how many times it's called (barring external system factors). It takes the same amount of time every single time.
Space Complexity: O(1)
- The function uses a constant amount of memory. It doesn't store any data structures that grow with input size. The memory used for the integer 1 and the print operation itself is negligible and fixed, not scaling with any hypothetical input.

Key Takeaways

Read Carefully: Always, always, always read the problem description thoroughly. Sometimes the solution is incredibly direct.
Master the Basics: Understanding how to define functions, handle arguments, and perform basic I/O (input/output) like printing is foundational to all programming.
Complexity Matters (Even for Simple Problems): Getting into the habit of analyzing time and space complexity, even for trivial tasks, hones a crucial skill for more complex challenges.
Embrace the Learning Curve: Every problem, no matter how simple or complex, offers a chance to learn something new or reinforce existing knowledge.

Happy coding, and see you in the next LeetCode adventure!

Author Account: Test
Publishing Time: 2026-05-23 17:14:50

LeetCode Solution: 20. Valid Parentheses

Vansh Aggarwal — Sun, 17 May 2026 05:55:53 +0000

Cracking LeetCode 20: Valid Parentheses - A Beginner's Guide to Stacks!

Hey there, future coding rockstars! 👋 NavyaSree_14 here, ready to tackle another exciting LeetCode challenge with you. Today, we're diving into problem 20: "Valid Parentheses". Don't let the name scare you; it's a fantastic introduction to a super useful data structure: the Stack!

The Problem: Are These Parentheses Playing Fair?

Imagine you're writing code, or maybe a complex mathematical expression. You've got different types of brackets: ( ), { }, [ ]. The problem asks us to determine if a given string, made only of these characters, has "valid" parentheses.

What makes them valid? Three simple rules:

Matching Pairs: Every open bracket ((, {, [) must be closed by the same type of bracket (), }, ]). You can't close ( with }!
Correct Order: Open brackets must be closed in the correct order. Think of it like nesting dolls: the last doll you opened must be the first one you close.
No Leftovers: Every close bracket must have a corresponding open bracket. And by the end, no open brackets should be left hanging!

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

s = "()"
- ( opens, ) closes it. Correct type, correct order. Output: true
s = "()[]{}"
- ( and ) match. [ and ] match. { and } match. All good! Output: true
s = "(]"
- ( opens, but ] tries to close it. Wrong type! Output: false
s = "([)]"
- ( opens. [ opens. Then ) closes ( (correct type) but [ was opened after (, so [ should be closed before (. Incorrect order! Output: false
s = "{[]}"
- { opens. [ opens. ] closes [ (correct type, correct order for []). } closes { (correct type, correct order for {}). Output: true

The string s will only contain these six characters, and its length can be up to 10,000.

The Intuition: "Who Was Last?" 🤔

How do we keep track of which opening bracket needs to be closed next? When we see an opening bracket, we need to remember it. When we see a closing bracket, we need to check if it matches the most recently opened and yet-to-be-closed bracket.

This "most recently opened, first to close" behavior is the perfect use case for a Stack!

Imagine a stack of plates. When you add a plate, it goes on top. When you remove a plate, you take the one from the top. That's Last-In, First-Out (LIFO).

When you see an opening bracket, it's like putting a plate on the stack. You remember it.
When you see a closing bracket, it's like taking the top plate off. You expect it to match the most recently added (top) opening bracket. If it does, great! If not, or if there are no plates (no opening brackets), then something is wrong!

The Approach: A Stack-Powered Validator

Let's break down the step-by-step logic:

Initialize a Stack: We'll need an empty list (in Python, lists can act as stacks) to store our open brackets.
Create a Mapping: To quickly check if a closing bracket has a valid opening counterpart, we'll create a dictionary (or hash map) that maps each closing bracket to its corresponding opening bracket.
- ')' : '('
- '}' : '{'
- ']' : '['
Iterate Through the String: We'll go through each character in the input string s one by one.

*   **If the character is an *opening* bracket (`(`, `{`, `[`):**
    *   Push it onto our `stack`. We're remembering that we saw this open bracket.

*   **If the character is a *closing* bracket (`)`, `}`, `]`):**
    *   **Check for an empty stack:** What if we encounter a closing bracket like `)` but our stack is empty? This means there was no corresponding opening bracket. So, it's invalid!
        *   *Pro Tip (from the solution code):* Instead of explicitly checking `if not stack: return False`, we can pop from the stack and assign a special character (like `'#'`) if the stack is empty. This simplifies the next comparison.
    *   **Pop from the stack:** Get the `top` element from our stack. This `top` element represents the most recently encountered opening bracket.
    *   **Compare:** Use our `mapping` to find what the *expected* opening bracket for our current `char` (the closing bracket) should be. Compare this `expected` opening bracket with the `top` element we just popped.
        *   If `mapping[char]` (the expected open bracket) is **NOT equal** to `top` (the actual last open bracket), then it's a mismatch! The parentheses are invalid. Return `False`.

Final Check: After iterating through the entire string:
- If our stack is empty, it means every opening bracket found its matching closing bracket in the correct order. The string is valid! Return True.
- If our stack is not empty, it means there are some opening brackets left without corresponding closing brackets. The string is invalid! Return False.

The Code: Bringing it to Life

Here's the Python code implementing this stack-based approach:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        # Mapping for quick lookup: close bracket -> open bracket
        mapping = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        for char in s:
            if char in mapping:  # If it's a closing bracket
                # Pop the top element if stack is not empty, else assign a dummy value
                top = stack.pop() if stack else '#'

                # Compare the popped element with the expected opening bracket
                if mapping[char] != top:
                    return False
            else:  # If it's an opening bracket
                stack.append(char)

        # After iterating, if the stack is empty, all brackets matched
        return not stack # 'not stack' returns True if stack is empty, False otherwise

Time and Space Complexity Analysis

Time Complexity: O(N)
- We iterate through the input string s exactly once. For each character, we perform constant-time operations (dictionary lookup, stack push/pop).
- N is the length of the input string.
Space Complexity: O(N)
- In the worst-case scenario (e.g., a string like (((((((((), our stack could end up storing all N/2 opening brackets.
- The mapping dictionary uses constant space, as it always stores 3 key-value pairs.

Key Takeaways

Stacks are for LIFO problems: Whenever you need to process items in a "last-in, first-out" manner (like matching pairs, backtracking, undo operations), think of a stack!
Mapping for quick lookups: Using a dictionary (mapping in our case) makes it super efficient to check relationships between items.
Edge cases matter: Always consider what happens with empty inputs, or when the stack is empty at critical points. Our solution handles this gracefully by checking if stack else '#'.
This problem is a classic and frequently asked. Mastering it truly solidifies your understanding of stacks!

And that's a wrap for "Valid Parentheses"! I hope this breakdown was clear and helpful. Keep practicing, keep coding, and I'll catch you in the next one!

Authored by NavyaSree_14 | Published on 2026-05-17 11:25:37

LeetCode Solution: 20. Valid Parentheses

Vansh Aggarwal — Sun, 17 May 2026 05:42:28 +0000

Cracking the Code: The Parenthesis Puzzle with Stacks! (LeetCode 20 Explained)

Hey Devs and future competitive programmers! 👋 NavyaSree_14 here, ready to demystify a classic LeetCode problem that's a fantastic introduction to a super useful data structure: the Stack. We're tackling Problem 20: "Valid Parentheses."

Don't let the simplicity of parentheses fool you – this problem teaches a fundamental pattern you'll see in many other coding challenges!

What's the Puzzle? (Problem Explanation)

Imagine you're a compiler, and you need to check if a line of code has all its parentheses, curly braces, and square brackets matched up correctly. That's exactly what this problem asks us to do!

We're given a string s that contains only these six characters: '(', ')', '{', '}', '[', and ']'. Our job is to determine if the string is "valid."

What makes it valid? Three simple rules:

Same Type: An open bracket ((, {, [) must be closed by the same type of bracket (e.g., ( must be closed by ), not } or ]).
Correct Order: Open brackets must be closed in the correct order. Think about nested structures: ([{}]) is valid, but ([)] is not, because the ] is trying to close [ before { is closed.
Every Close Has an Open: Every closing bracket must have a corresponding unclosed open bracket of the same type before it. You can't just have ) without a preceding (.

Let's look at some quick examples:

s = "()" -> True (Simple and perfectly matched!)
s = "()[]{}" -> True (All pairs are distinct and valid)
s = "(]" -> False (Opening parenthesis closed by a square bracket – wrong type!)
s = "([{}])" -> True (Nested, but everything matches up beautifully)
s = "([)]" -> False (Here, the ] closes [ before } is closed. Incorrect order!)

The string length can be up to 10,000 characters. Ready to solve it?

The "Aha!" Moment (Intuition)

When you see an opening bracket, what do you expect? You expect its corresponding closing bracket to appear later. But here's the kicker: if you encounter another opening bracket before the first one is closed, you expect that new opening bracket to be closed first.

This "last one in, first one out" behavior should immediately make you think of a Stack!

Imagine you're reading the string character by character:

When you see an opening bracket ((, {, [), you're essentially "expecting" its closure. You can push it onto a stack. It's waiting for its match.
When you see a closing bracket (), }, ]), this is where the magic happens. You need to check if it matches the most recently opened bracket that hasn't been closed yet. Where is that "most recently opened" bracket? Right at the top of your stack!

If the closing bracket matches the top of the stack, awesome! They cancel each other out, so you pop the opening bracket from the stack. If they don't match, or if there's no opening bracket on the stack at all, then our string is invalid.

Step-by-Step Logic (Approach)

Let's break down the stack-based approach:

Initialize an Empty Stack: This stack will store all the opening brackets we encounter that are still waiting for their match.
Create a Mapping: We need a quick way to know which opening bracket corresponds to which closing bracket. A dictionary (or hash map) is perfect for this! We'll map closing brackets to their respective opening brackets.
- ')' : '('
- '}' : '{'
- ']' : '['
Iterate Through the String: Go through each character char in the input string s.

*   **Case 1: `char` is a Closing Bracket** (e.g., `')'`, `'}'`, `']'`).
    *   First, check if our `stack` is empty. If it is, and we've found a closing bracket, it means there's no opening bracket to match it. This immediately makes the string `invalid`. Return `False`.
    *   If the stack is *not* empty, `pop` the top element from the stack. Let's call it `top_element`.
    *   Now, compare `top_element` with the *expected* opening bracket for the current `char`. We get this `expected` opening bracket from our mapping (e.g., `mapping[char]`).
    *   If `top_element` is *not equal* to `mapping[char]`, it means the brackets don't match (e.g., we popped a `(` but expected a `[`). The string is `invalid`. Return `False`.

*   **Case 2: `char` is an Opening Bracket** (e.g., `'('`, `'{'`, `'['`).
    *   This is simple! Just `append` (or `push`) this opening bracket onto our `stack`. It's now waiting for its corresponding closing bracket.

Final Check: After iterating through the entire string:
- If the stack is empty, it means every opening bracket found its correct match and was popped. The string is valid. Return True.
- If the stack is not empty, it means there are still some opening brackets left on the stack that never found a closing bracket. The string is invalid. Return False.

This approach systematically checks for matching types and correct order using the LIFO (Last-In, First-Out) property of a stack!

The Code

Here's the Python implementation of our approach:

class Solution:
    def isValid(self, s: str) -> bool:
        # Initialize an empty stack to store opening brackets
        stack = []

        # Create a dictionary to map closing brackets to their corresponding opening brackets
        # This helps in quick lookups
        mapping = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        # Iterate through each character in the input string
        for char in s:
            # If the character is a closing bracket (i.e., it's a key in our mapping)
            if char in mapping:
                # Get the top element from the stack.
                # If the stack is empty, assign a dummy value like '#'
                # This prevents errors from popping an empty stack and allows easy comparison
                top_element = stack.pop() if stack else '#'

                # Check if the popped element matches the expected opening bracket
                # If they don't match, or if stack was empty (top_element was '#'), it's invalid
                if mapping[char] != top_element:
                    return False
            # If the character is an opening bracket
            else:
                # Push it onto the stack, waiting for its closure
                stack.append(char)

        # After iterating through the entire string, if the stack is empty,
        # all opening brackets have been correctly closed.
        # Otherwise, there are unclosed opening brackets.
        return not stack # 'not stack' returns True if stack is empty, False otherwise

Time & Space Complexity Analysis

Understanding how efficient our solution is crucial for competitive programming!

Time Complexity: O(N)
- We iterate through the input string s exactly once. N is the length of the string.
- Inside the loop, operations like char in mapping, stack.pop(), stack.append(), and dictionary lookups (mapping[char]) all take constant time, O(1), on average.
- Therefore, the total time complexity is directly proportional to the length of the string, making it O(N).
Space Complexity: O(N)
- In the worst-case scenario, the stack could potentially store all the opening brackets if they are all at the beginning of the string (e.g., s = "(((((((((").
- In such a case, the stack could grow up to a size of N/2 (since at most half the string can be opening brackets if they were to eventually be valid).
- Thus, the space required by the stack is proportional to the input string length, leading to a space complexity of O(N).

Key Takeaways

This problem is a fantastic stepping stone! Here's what we learned:

Stacks are for Matching: Whenever you need to check for matching pairs (parentheses, XML tags, function calls, etc.) that follow a "last-in, first-out" pattern, a stack is your go-to data structure.
LIFO Principle: The core idea behind stacks – Last In, First Out – is perfectly suited for handling nested structures where the most recently opened item must be the first to be closed.
Hash Maps for Quick Lookups: Using a dictionary (or hash map) to store the mapping between opening and closing brackets makes our code clean and efficient (O(1) average time for lookups).
Edge Cases: Always consider empty stacks (e.g., ) at the beginning) and non-empty stacks at the end (unmatched opening brackets).

Keep practicing, and you'll find these patterns appearing everywhere! Happy coding!

Author Account: NavyaSree_14

Time Published: 2026-05-17 11:12:11

LeetCode Solution: 1. Two Sum

Vansh Aggarwal — Sun, 17 May 2026 05:40:12 +0000

Two Sum: Your First Step into LeetCode Magic! ✨

Hey there, future coding superstar! 👋 Welcome to your very first LeetCode adventure! If you're just starting your journey into algorithms and data structures, you've landed in the perfect place. We're going to tackle a legendary problem today: Two Sum. It's often the first problem many programmers encounter, and it's a fantastic way to learn about efficiency and the power of data structures.

Ready to unlock some coding magic? Let's dive in!

🧐 Problem Explanation: What are we trying to do?

Imagine you have a list of numbers, like [2, 7, 11, 15]. And you're given a specific target number, say 9. Your mission, should you choose to accept it, is to find two different numbers in that list that add up to your target.

Once you find them, you don't return the numbers themselves, but their positions (indices) in the original list.

Let's look at our example:

nums = [2, 7, 11, 15]
target = 9

Can you spot the pair?

2 is at index 0.
7 is at index 1.
And hey, 2 + 7 = 9! Bingo!
So, our answer would be [0, 1].

A few ground rules to keep in mind:

One Solution, Guaranteed: You'll always find exactly one pair that works. No need to worry about multiple answers or no answer at all.
No Reusing: You can't use the same number twice. If nums = [3, 3] and target = 6, you use the 3 at index 0 and the 3 at index 1 (they're distinct elements, even if their values are the same).
Order Doesn't Matter: Returning [0, 1] or [1, 0] is perfectly fine.

🤔 Intuition: The "Aha!" Moment

When you first hear this problem, your brain probably jumps to the most straightforward solution: "I'll just try every single combination of two numbers until I find the pair!"

This is a totally natural and valid starting point! It's called the brute-force approach. Think of it like rummaging through a messy drawer, picking one sock, and then trying to find its matching pair by looking at every other sock.

But here's the thing about competitive programming and real-world coding: we often want the fastest and most efficient way to solve a problem. Is there a shortcut to finding that second sock? What if you had an ultra-organized sock drawer where you could instantly find any sock you needed?

The "aha!" moment for Two Sum comes when you realize that instead of constantly re-scanning the list for the second number, you could remember the numbers you've already seen and their positions. This way, when you're looking for a complement (the number that adds up to the target), you can "ask" your memory if you've already seen it.

🚀 Approach: Step-by-Step Logic

Let's break down how we can solve this problem, starting with the simpler (but less efficient) way, then moving to a much smarter solution!

1. The Brute-Force (Nested Loops) Approach

This is your first instinct, and it's essential to understand it before optimizing!

Start with the first number in the list (let's call it num1).
Then, take num1 and compare it with every other number in the rest of the list (let's call these num2).
If num1 + num2 equals your target, fantastic! You've found your pair. Return their indices.
If not, keep trying different num2s with the current num1.
If you've checked all possible num2s for the current num1, move to the next num1 in the original list and repeat the whole process.

Dry Run Example: nums = [2, 7, 11, 15], target = 9

Outer loop (i = 0, num1 = 2):
- Inner loop (j = 1, num2 = 7): Is 2 + 7 == 9? YES! Return [0, 1].

This works perfectly, but as the list nums gets bigger, this approach becomes very slow because of all the re-checking.

2. The Smarter Way: Using a Hash Map (Dictionary)

This is where the magic happens! A Hash Map (also known as a Dictionary in Python, HashMap in Java, or Hash Table) is a data structure that allows you to store key: value pairs and look up a key almost instantly! Think of it like a super-fast index for your numbers.

Here's the optimized strategy:

Create an empty Hash Map. We'll use it to store numbers we've already seen, along with their indices. The format will be {number: index}.
Go through the nums list one number at a time. For each number, let's call it current_num and its index i.
Calculate the complement: This is the number we need to find to hit our target.
- complement = target - current_num
- Example: If target = 9 and current_num = 2, we need complement = 9 - 2 = 7.
Check your Hash Map: Look if this complement is already a key in your Hash Map.
- If it IS in the map: Wow! You've found your pair! The complement is one number, and your current_num is the other.
  - Return the index stored with the complement (i.e., hashmap[complement]) and your current index i.
- If it's NOT in the map: No worries! It just means we haven't encountered its partner yet. Add your current_num and its index i to the Hash Map. This way, if a future number needs current_num as its complement, it will be found instantly.
Continue this process until you find the pair (which, remember, you're guaranteed to do!).

Dry Run Example: nums = [2, 7, 11, 15], target = 9

Current `i`	Current `num`	`complement = target - num`	Is `complement` in `hashmap`?	Action	`hashmap` (after action)
					`{}`
`0`	`2`	`9 - 2 = 7`	No	Add `2:0` to `hashmap`	`{2:0}`
`1`	`7`	`9 - 7 = 2`	Yes! (`2` is in `hashmap`)	Return `[hashmap[2], 1]` which is `[0, 1]`

And we found the answer much quicker!

💻 Code (Python)

Here's the Python code implementing the Hash Map approach:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hash map (dictionary in Python)
        # This map will store: {number_value: its_index}
        hashmap = {}

        # Iterate through the list of numbers.
        # 'enumerate' gives us both the index (i) and the value (num) at each step.
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed.
            # If current 'num' is X and 'target' is T, we need T - X.
            complement = target - num

            # Check if this 'complement' is already a key in our hashmap.
            # This is a very fast O(1) average time operation!
            if complement in hashmap:
                # If found, we've got our pair!
                # Return the index of the complement (retrieved from the hashmap)
                # and the index of the current number (i).
                return [hashmap[complement], i]

            # If the complement isn't found, it means the current 'num'
            # hasn't found its partner yet. So, we add 'num' and its index 'i'
            # to the hashmap. This makes it available for future numbers
            # that might need 'num' as their complement.
            hashmap[num] = i

        # The problem guarantees exactly one solution, so this part of the code
        # should technically never be reached. However, in other scenarios,
        # you might raise an error or return an empty list if no solution is found.

⏱️ Time & Space Complexity Analysis

Understanding how efficient your code is is a crucial skill!

Brute-Force Approach (Nested Loops)

Time Complexity: O(n^2)
- We have two loops, one nested inside the other. If the list has n elements, the outer loop runs n times, and the inner loop runs up to n-1 times for each outer loop iteration. This results in approximately n * n = n^2 operations. As n grows, n^2 grows very quickly, making it inefficient for large lists.
Space Complexity: O(1)
- We're not using any additional data structures that scale with the input size, just a few variables.

Hash Map Approach

Time Complexity: O(n)
- We iterate through the list only once. For each number, we perform a constant number of operations: calculate the complement, check if it's in the hash map, and potentially add the current number to the hash map.
- Looking up an item in a hash map and inserting an item into it both take, on average, O(1) (constant) time.
- Therefore, n operations, each taking O(1) time, results in an overall O(n) time complexity. This is significantly faster than O(n^2) for larger inputs!
Space Complexity: O(n)
- In the worst case, we might have to add almost all n numbers and their indices to our hash map before finding the desired pair. This means the space used by the hash map grows proportionally with the number of elements in the input list.

🌟 Key Takeaways

Start Simple: Don't be afraid to think of the brute-force solution first. It helps you understand the problem thoroughly.
Hash Maps are Powerful: For problems that involve quick lookups, checking for existence, or mapping values to other values, Hash Maps (dictionaries) are incredibly efficient and often the key to optimizing your solution.
Think in Complements: Many "find a pair/sum" problems can be broken down into calculating what complement you need and then efficiently searching for it.
Time-Space Trade-off: We improved our time complexity from O(n^2) to O(n) by using more space (O(n) for the hash map). This is a very common and powerful trade-off in algorithm design!

Congratulations! You've just conquered your first LeetCode problem with an optimized solution. This foundational problem teaches you concepts that you'll apply to many more challenges down the road. Keep practicing, and happy coding!

Author: NavyaSree_14
Published: 2026-05-17 11:09:40

LeetCode Solution: 1. Two Sum

Vansh Aggarwal — Sat, 16 May 2026 15:24:46 +0000

Conquering Your First LeetCode Challenge: Two Sum Demystified!

Hey there, aspiring coder! 👋 Ever heard of LeetCode? It's a fantastic platform to sharpen your problem-solving skills, and we're about to tackle one of its most famous (and foundational!) problems: Two Sum. Don't let the number "1" fool you; while it's often the first problem people encounter, it's packed with key concepts that will serve you well in your coding journey.

Let's dive in and unravel this classic together!

The Problem: Finding Our Pair

Imagine you have a list of numbers, like [2, 7, 11, 15], and a specific target number, say 9. Your mission, should you choose to accept it, is to find two different numbers in that list that add up to the target. Once you find them, you need to tell us their positions (their "indices") in the original list.

Here's the official breakdown:

Given:

An array of integers nums (e.g., [2, 7, 11, 15])
An integer target (e.g., 9)

Goal:

Return the indices of the two numbers in nums that sum up to target.

Key Assumptions:

There will always be exactly one pair that solves the problem.
You cannot use the same number twice (meaning, the two numbers must come from different positions in the array).
The order of the returned indices doesn't matter.

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

Example 1:

nums = [2, 7, 11, 15]
target = 9

Thinking Process:

We look at 2. What number do we need to add to 2 to get 9? We need 7 (9 - 2 = 7).
Is 7 in our nums array? Yes, it is!
The index of 2 is 0.
The index of 7 is 1.
Since nums[0] + nums[1] == 9, we found our pair!

Output: [0, 1]

See? Not so scary, right?

The "Aha!" Moment: Beyond Brute Force

When you first encounter a problem like this, a common initial thought (and a totally valid one!) is to try every single combination. You might think:

"Let's take the first number (2).
- Add it to the second (7): 2 + 7 = 9. Bingo!
- (If not found, try 2 + 11, 2 + 15, etc.)"
"Then take the second number (7).
- Add it to the third (11): 7 + 11 = 18. No.
- (And so on...)"

This approach, known as brute force, involves using nested loops to check every possible pair. It works, but for very large lists, it can be slow. Imagine a list with 10,000 numbers! You'd be doing tens of millions of checks! 😵

So, the "aha!" moment comes when you realize: instead of searching for the other_number, what if we could instantly know if it exists and where it is?

This is where a super-powered data structure comes into play: the Hash Map (or Dictionary in Python, HashMap in Java/JavaScript, etc.).

If we know we need complement = target - current_number, and we want to find complement fast, a hash map is our best friend. It lets us store values (like numbers from our list) and retrieve their associated information (like their index) almost instantly!

Our Smart Approach: The Hash Map Helper

Here's how we can use a hash map to solve Two Sum efficiently:

Step 1: Build a Map of Numbers to Their Indices

First, we'll iterate through our nums array once. As we go, we'll build a hash map where:

Keys are the numbers from nums.
Values are their corresponding indices.

Why do this? Because it gives us a quick way to ask, "Hey, does the number X exist in nums, and if so, what's its index?"

Let's use nums = [2, 7, 11, 15] and target = 9 again:

Iteration	`nums[i]`	`i`	`hashmap` after adding `nums[i]: i`
1	2	0	`{2: 0}`
2	7	1	`{2: 0, 7: 1}`
3	11	2	`{2: 0, 7: 1, 11: 2}`
4	15	3	`{2: 0, 7: 1, 11: 2, 15: 3}`

Step 2: Find the Complement

Now that our hash map is fully built, we iterate through nums again. For each number nums[i]:

Calculate the complement: This is the number we need to find to reach our target. complement = target - nums[i].
Check the hash map: Does our complement exist as a key in the hashmap?
Crucial Check: If it does exist, we also need to make sure that the index stored for the complement (hashmap[complement]) is not the same as our current index i. Remember, we can't use the same element twice!
Found It!: If both conditions are true, we've found our pair! We return [i, hashmap[complement]].

Let's trace this step with our example: nums = [2, 7, 11, 15], target = 9, hashmap = {2: 0, 7: 1, 11: 2, 15: 3}.

`i`	`nums[i]`	`complement = target - nums[i]`	`complement` in `hashmap`?	`hashmap[complement]`	`hashmap[complement] != i`?	Action
0	2	`9 - 2 = 7`	Yes	1	`1 != 0` (True)	Return `[0, 1]`

And just like that, we found our solution efficiently!

The Code: Python Magic ✨

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Step 1: Build the hash map
        # Stores {number: index}
        hashmap = {} 
        for i in range(len(nums)):
            hashmap[nums[i]] = i

        # Step 2: Iterate again to find the complement
        for i in range(len(nums)):
            complement = target - nums[i]

            # Check if the complement exists in our hashmap
            # AND make sure its index isn't the same as our current 'i'
            if complement in hashmap and hashmap[complement] != i:
                return [i, hashmap[complement]]

        # This line should technically not be reached given the problem constraints
        # ("exactly one solution exists"), but it's good practice for robust code.
        return []

The Nitty-Gritty: Time & Space Complexity

Understanding how efficient your code is (or isn't!) is a fundamental skill. We measure this using Time Complexity (how execution time grows with input size) and Space Complexity (how memory usage grows).

Time Complexity: O(n)
- Explanation: We iterate through the nums array twice.
  - The first loop builds the hash map, doing n operations (each insertion into a hash map takes, on average, O(1) time). So, O(n) for the first loop.
  - The second loop performs n lookups (each complement in hashmap and hashmap[complement] takes, on average, O(1) time). So, O(n) for the second loop.
- Adding these up, O(n) + O(n) simplifies to O(n). This is considered very efficient!
- (Remember the follow-up question? "Can you come up with an algorithm that is less than O(n^2) time complexity?" We did it! Brute force would have been O(n^2).)
Space Complexity: O(n)
- Explanation: We create a hash map to store elements from the nums array. In the worst case (all numbers are unique), the hash map will store n key-value pairs. Therefore, the space required grows linearly with the input size n.

Key Takeaways for Your Coding Journey

Hash Maps are Powerful: They excel at fast lookups. Whenever you need to quickly check if an item exists or retrieve its associated data, think hash map!
The "Complement" Idea: Many problems can be reframed by thinking, "What X do I need to reach Y?" (i.e., X = Y - current_item). This is a common pattern in competitive programming.
Optimize Beyond Brute Force: While brute force is a great starting point to understand a problem, always challenge yourself to find more efficient solutions, especially when dealing with larger inputs. O(n) is often a significant upgrade from O(n^2).
Understand Constraints: The problem statement's constraints and assumptions (like "exactly one solution" and "cannot use the same element twice") are vital. They guide your solution and help you avoid unnecessary checks or edge cases.

And there you have it! You've successfully navigated LeetCode's Problem #1, "Two Sum," armed with the power of hash maps. This problem is a gateway to many more exciting algorithmic challenges. Keep practicing, keep learning, and happy coding!

Author: p1Hzd8mRM8
Published: 2026-05-16 20:53:55

LeetCode Solution: 1. Two Sum

Vansh Aggarwal — Sat, 16 May 2026 11:08:22 +0000

Your First LeetCode Journey: Conquering the Classic Two Sum Problem!

Hey everyone! 👋 NavyaSree_14 here, excited to kick off our coding adventure with LeetCode's most famous warm-up challenge: Two Sum. If you've just started your DSA journey, this problem is a fantastic stepping stone. It's simple to understand, yet introduces a powerful optimization technique that's vital for competitive programming and interviews.

Let's dive in!

Problem Explanation

Imagine you're at a treasure hunt. You have a list of numbers, let's call it nums, and a specific "target" number you're looking for. Your mission? Find two different numbers in nums that add up exactly to target. Once you find them, you need to tell us their positions (their "indices") in the original list.

Important Notes:

There will always be exactly one pair of numbers that sums to the target. No need to worry about multiple answers or no answer!
You can't use the same number twice. If nums[0] is part of the pair, you can't use nums[0] again as the second number.
The order of the indices you return doesn't matter. [0, 1] is the same as [1, 0].

Let's look at some examples:

Example 1:

nums = [2, 7, 11, 15]
target = 9
Output: [0, 1]
Why? Because nums[0] (which is 2) + nums[1] (which is 7) = 9. We return their indices: 0 and 1.

Example 2:

nums = [3, 2, 4]
target = 6
Output: [1, 2]
Why? nums[1] (which is 2) + nums[2] (which is 4) = 6.

See? Simple enough!

Intuition: The "Aha!" Moment 💡

How would you solve this manually? You'd probably pick a number, say 2, and then look through the rest of the list for 7 (because 9 - 2 = 7). If you find 7, great! If not, you move to the next number, say 7, and look for 2 (9 - 7 = 2), and so on.

This "pick one, then search the rest" approach works, but it can be slow if the list is very long. For every number you pick, you might have to scan almost the entire remaining list. This is what we call a brute-force approach, and its time complexity is O(n²), which isn't ideal for large inputs.

The "aha!" moment comes when you realize: Can I avoid repeatedly scanning the list?

Instead of searching for the complement (the target - current_num) in the rest of the array, what if I could instantly know if I've seen that complement before, and if so, what its index was?

This is where hashmaps (or dictionaries in Python) shine! A hashmap lets you store key-value pairs and quickly check if a key exists, and retrieve its value, usually in O(1) (constant) time on average.

So, the new intuition is: As I iterate through the numbers, for each number, I calculate what its "partner" (complement) would need to be. Then, I quickly check if I've already encountered that partner in my journey so far.

Approach: Step-by-Step Logic

We'll use a single pass through the array, leveraging a hashmap (dictionary in Python) to keep track of numbers we've already processed and their indices.

Initialize an empty hashmap: Let's call it num_map. This map will store numbers as keys and their indices as values. hashmap = {number: index}.
Iterate through the nums array: We need both the index (i) and the value (num) of each element.
For each num:
- Calculate the complement: This is the value we need to find to sum up to target. So, complement = target - num.
- Check if the complement is already in our num_map:
  - If YES: Fantastic! We've found our pair! The complement was encountered earlier, and its index is num_map[complement]. The current number's index is i. We return [num_map[complement], i].
  - If NO: The complement isn't in our num_map yet. This means the current num doesn't form a pair with any number we've seen so far. So, we add the current num and its index i to num_map. This way, num can act as a complement for a future number we encounter. num_map[num] = i.
Why does this work? Because we are guaranteed exactly one solution. Once we find the pair, we return immediately.

Let's trace Example 1: nums = [2, 7, 11, 15], target = 9

Iteration	`i`	`num`	`complement` (`target - num`)	`num_map` (before check)	`complement` in `num_map`?	Action	`num_map` (after action)	Output
1	0	2	7	`{}`	No	Add `2:0`	`{2:0}`
2	1	7	2	`{2:0}`	Yes	Return `[num_map[2], 1]`		`[0,1]`

Boom! We found it in just two steps.

Code

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hashmap (dictionary in Python)
        # to store numbers we've seen and their indices.
        # Format: {number: index}
        hashmap = {}

        # Iterate through the input list 'nums' using enumerate
        # to get both the index 'i' and the value 'num'
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed to reach the target
            # complement = target - current_num
            complement = target - num

            # Check if this 'complement' already exists in our hashmap.
            # If it does, it means we've seen its partner before!
            if complement in hashmap:
                # We found the two numbers!
                # The index of the 'complement' is stored in hashmap[complement]
                # The index of the current 'num' is 'i'
                return [hashmap[complement], i]

            # If the complement is NOT in the hashmap,
            # it means the current 'num' doesn't form a pair with any
            # number encountered *so far*.
            # So, we add the current 'num' and its index to the hashmap.
            # This makes it available as a 'complement' for future numbers.
            hashmap[num] = i

        # The problem guarantees that exactly one solution exists,
        # so this line will theoretically never be reached.
        # However, for completeness in a real-world scenario, you might
        # raise an error or return an empty list if no solution was found.
        # return []

Time & Space Complexity Analysis

Understanding how efficient your solution is, is crucial!

Time Complexity: O(n)

We iterate through the nums list exactly once.
Inside the loop, operations like calculating the complement, checking if an element is in the hashmap, and adding an element to the hashmap (hashmap[num] = i) all take, on average, O(1) (constant) time.
Since we perform these O(1) operations n times (where n is the length of nums), the total time complexity is n * O(1), which simplifies to O(n).
This is a significant improvement over the brute-force O(n^2) approach!

Space Complexity: O(n)

In the worst-case scenario, we might have to store all n elements from the nums array into our hashmap. This happens if the target pair is at the very end of the array, or if the complement is always found after the current num is added.
Therefore, the space required by the hashmap can grow up to n elements, making the space complexity O(n).

This is a classic time-space trade-off: we use extra space (the hashmap) to achieve a much faster time complexity.

Key Takeaways

Hashmaps are your friends! They are incredibly powerful data structures for quick lookups and can often transform O(n^2) problems into O(n) problems.
Think about complements: Many "find a pair" or "find a sum" problems can be reframed as finding a complement.
One pass is often better than two: If you can achieve the result in a single iteration by storing necessary information, it's usually more efficient.
LeetCode #1 is foundational: Master this concept, and you're well on your way to tackling more complex problems!

Keep practicing, and don't be afraid to experiment with different approaches. Happy coding!

Author Account: NavyaSree_14 | Published: 2026-05-16 16:37:57

LeetCode Solution: 20. Valid Parentheses

Vansh Aggarwal — Sat, 16 May 2026 10:55:25 +0000

The Great Parentheses Puzzle: Cracking LeetCode 20 with Stacks!

Hey there, future coding superstar! 👋 NavyaSree_14 here, and today we're diving into a classic LeetCode problem that might seem simple on the surface but teaches us a fundamental data structure concept: Valid Parentheses (Problem 20).

Don't let the "LeetCode" tag intimidate you! We're going to break this down step-by-step, making it as clear as possible. Think of it as a fun puzzle that will level up your problem-solving skills. Ready to unravel some brackets? Let's go!

What's the Puzzle? (Problem Explanation)

Imagine you're writing a math equation or some code. You use parentheses like (), curly braces {} and square brackets [] all the time. But what makes them "correctly" used?

That's exactly what this problem asks us to determine! We're given a string s that contains only these six characters: (, ), {, }, [, ]. Our mission is to figure out if the arrangement of these brackets is valid.

So, what makes a string of brackets valid? Three simple rules:

Matching Pairs: Every open bracket ((, {, [) must be closed by the same type of bracket (so ( needs ), not ] or }).
Correct Order: Open brackets must be closed in the correct sequence. Think of it like peeling an onion: the last bracket opened must be the first one closed. ([{}]) is valid, but ([)] is not.
No Leftovers: Every close bracket must have a corresponding open bracket. You can't just have )) without an opening ((.

Let's look at a few quick examples:

"()" -> True (Simple and perfectly matched)
"()[]{}" -> True (Multiple pairs, all valid)
"(]" -> False (An open parenthesis closed by a square bracket – wrong type!)
"([)]" -> False (Open parenthesis, then open square, but then square is closed before parenthesis. Incorrect order!)
"{[]}" -> True (Looks complex, but [] is inside {}, all matched correctly!)
"[" -> False (An open bracket without a closing one!)

The "Aha!" Moment (Intuition)

When you read a sequence of brackets like "{[()]}", how do you intuitively know it's valid?

You probably keep track of what's "open" and what you're "expecting" to close.

You see {, you think "Okay, I need a } eventually."
Then [, you think "Now I also need a ] before that }."
Then (, you think "And a ) before the ]."
When you see ), you check: "Is the last thing I opened a (? Yes! Great, match found. Forget about (. Now I'm back to needing a ]."
Then ], you check: "Is the last thing I opened a [? Yes! Perfect. Forget about [. Now I'm back to needing a }."
Finally }, you check: "Is the last thing I opened a {? Yes! Awesome. Forget about {. Nothing left."

This pattern of "remembering the last opened item and checking if the current closed item matches it" is a classic use case for a Stack!

A stack is like a pile of plates: you add new plates to the top (push), and when you want to take one, you always take the one from the top (pop). It's LIFO (Last-In, First-Out). This is exactly what we need for brackets: the last bracket we opened is the first one we expect to close.

Our Game Plan (Approach)

We'll use a stack to keep track of all the open brackets we encounter.

Here's the step-by-step breakdown:

Initialize a Stack: Create an empty list (which will act as our stack in Python).
Create a Mapping: We need a quick way to know which opening bracket corresponds to which closing bracket. A dictionary (hash map) is perfect for this! We'll map closing brackets to their opening counterparts: ')' : '(', '}' : '{', ']' : '['.
Iterate Through the String: Go through each character in the input string s one by one.

*   **If it's an Opening Bracket (`(`, `{`, `[`):**
    *   Simply push this bracket onto our stack. We're "remembering" that we've opened it and will expect its corresponding closing bracket later.

*   **If it's a Closing Bracket (`)`, `}`, `]`):**
    *   **Check for an Empty Stack:** First, check if our stack is empty. If it is, it means we've encountered a closing bracket *without any corresponding open bracket*. This is invalid! Return `False`.
    *   **Pop and Compare:** If the stack is *not* empty, pop the top element from the stack. This `top_element` is the *most recently opened* bracket.
    *   Now, compare this `top_element` with the *expected* opening bracket for our *current closing bracket*. We'll use our `mapping` dictionary for this. If `mapping[current_closing_bracket]` (e.g., `'('` for `')'`) is *not* equal to `top_element`, then we have a mismatch (e.g., `(]` or `{[)]`). This is invalid! Return `False`.

Final Check: After checking all characters in the string:
- If our stack is empty, it means every opening bracket we pushed onto the stack eventually found its matching closing bracket. The string is valid! Return True.
- If our stack is not empty, it means there are still some opening brackets left on the stack that never found their closing partners. The string is invalid! Return False.

The Code (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        # Our stack to keep track of opening brackets
        stack = []

        # A dictionary to map closing brackets to their corresponding opening brackets
        # This helps us quickly check if a closing bracket matches the top of the stack.
        mapping = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        # Iterate through each character in the input string
        for char in s:
            # If the character is a CLOSING bracket (i.e., it's a key in our mapping)
            if char in mapping:
                # Pop the top element from the stack if it's not empty.
                # If the stack is empty, it means we encountered a closing bracket
                # without any open bracket preceding it. We use '#' as a dummy value
                # to ensure the comparison fails correctly in that case.
                top_element = stack.pop() if stack else '#'

                # Check if the popped opening bracket matches the expected opening bracket
                # for the current closing bracket.
                # If they don't match (or if stack was empty, top_element is '#'),
                # then the sequence is invalid.
                if mapping[char] != top_element:
                    return False
            # If the character is an OPENING bracket
            else:
                # Push all opening brackets onto the stack to remember them.
                stack.append(char)

        # After iterating through the entire string:
        # If the stack is empty, it means all opening brackets found their matching
        # closing brackets in the correct order. The string is valid.
        # If the stack is not empty, it means there are unclosed opening brackets.
        # So, 'not stack' will return True if empty, False if not empty.
        return not stack

How Fast & How Much Memory? (Complexity Analysis)

Understanding how efficient our solution is is super important!

Time Complexity: O(N)
- N is the length of the input string s.
- We iterate through the string exactly once. For each character, we perform constant-time operations (dictionary lookup, stack push/pop).
- Therefore, the time taken grows linearly with the length of the string.
Space Complexity: O(N)
- In the worst-case scenario (e.g., (((((((((), our stack could end up storing all N opening brackets if they never find their match.
- So, the space required for the stack can grow linearly with the length of the string.

Key Takeaways

Stacks are your friends for order-dependent matching! Whenever you need to match opening/closing items, process things in reverse order of appearance, or manage recursive structures, think of a stack.
Dictionaries for quick lookups: Using mapping for closing -> opening bracket pairs makes our code clean and efficient for comparisons.
Edge cases matter: Remember to handle scenarios like an empty stack when a closing bracket appears, or a non-empty stack at the very end.

This problem is a fantastic introduction to stacks and a common interview question. Mastering it sets a strong foundation for more complex problems!

Happy coding! Keep those brackets balanced! 😉

Authored by NavyaSree_14. Published on 2026-05-16 16:25:05.

LeetCode Solution: 1. Two Sum

Vansh Aggarwal — Sat, 16 May 2026 10:51:25 +0000

Your First LeetCode Victory: Cracking "Two Sum" with Python!

Hey there, aspiring coders and LeetCode adventurers! 👋 Welcome to your first step into the exciting world of algorithmic problem-solving. Today, we're tackling a true classic, often the very first problem many developers encounter: "Two Sum".

Don't let the "LeetCode" name intimidate you! We'll break it down step-by-step, uncover the magic behind the solution, and get you confident in your coding journey. Think of this as your friendly guide to an "aha!" moment. ✨

🧐 The Problem: What Are We Looking For?

Imagine you're given a list of numbers, like a shuffled deck of cards, and a specific "target" number. Your mission, should you choose to accept it, is to find two different numbers in that list that, when added together, perfectly equal your target.

But there's a twist! Instead of just saying "Found them!", you need to tell us where they are in the list – their positions, or indices.

Here's the official breakdown:

Given:

An array (list) of integers called nums.
An integer called target.

Return:

The indices of the two numbers that add up to target.

Important Guarantees (to make our lives easier!):

There will always be exactly one pair of numbers that sum to the target. No need to worry about multiple solutions or no solutions.
You cannot use the same number twice (even if it appears multiple times in the list, you pick two distinct positions).
You can return the indices in any order.

Let's look at some examples to make it super clear:

Example 1:

nums = [2, 7, 11, 15]
target = 9
Output: [0, 1]
Why? Because nums[0] (which is 2) + nums[1] (which is 7) = 9. We return their positions: 0 and 1.

Example 2:

nums = [3, 2, 4]
target = 6
Output: [1, 2]
Why? Because nums[1] (which is 2) + nums[2] (which is 4) = 6.

See? Not so scary, right? Now, let's figure out how to solve it!

🤔 Intuition: How Would You Find It?

Before jumping to code, let's think like a human.

The "Brute Force" Way (Our first thought):
If you had nums = [2, 7, 11, 15] and target = 9, you might do this:

Take 2 (at index 0).
- Pair it with 7 (at index 1): 2 + 7 = 9. Aha! Found it!
- (If not, you'd continue: 2 + 11 = 13 (no), 2 + 15 = 17 (no)).
Then you'd move to 7 (at index 1).
- Pair it with 11 (at index 2): 7 + 11 = 18 (no).
- Pair it with 15 (at index 3): 7 + 15 = 22 (no).
...and so on.

This approach works! You're checking every possible pair. But imagine a list with thousands of numbers. Checking every number with every other number would take a very long time. This is what we call an O(n^2) solution (quadratic time complexity), which means the time it takes grows very quickly as the list gets larger. Can we do better?

The "Aha!" Moment (The Smart Way):
Let's rethink. We're looking for num1 + num2 = target.
This can be rewritten as num2 = target - num1.

So, as we look at num1, we immediately know exactly what num2 we need.
Instead of blindly searching for num2 by checking every subsequent number, what if we could instantly ask: "Hey, have I already seen the num2 I need among the numbers I've processed so far?"

If we have a super-fast way to remember numbers we've seen and their positions, we could find the num2 instantly! This "super-fast way to remember and look up" is exactly what a hash map (or a dictionary in Python) is for!

🚶 The Approach: Step-by-Step with a Hash Map

Here's how we'll use a hash map to solve "Two Sum" efficiently:

Initialize an empty hash map (dictionary): We'll call it seen_numbers. This map will store key-value pairs where the key is a number we've encountered, and the value is its index in the nums array.
- Example: {number: index}
Iterate through the nums array: Go through each number one by one. For each number, we'll keep track of its actual value and its index.
For each num at index:
a. Calculate the complement: This is the number we need to find to make the sum equal to target.
complement = target - num
b. Check if complement is in seen_numbers:
* IF YES: Fantastic! We've found our pair. The complement is in our hash map, and its index is seen_numbers[complement]. The current num is what we're looking at right now, and its index is i. We return [seen_numbers[complement], i]. We're done!
* IF NO: No worries! The complement isn't among the numbers we've seen yet. So, we add the current number (num) and its index (i) to our seen_numbers map. This way, if a future number needs num as its complement, it can find it quickly. seen_numbers[num] = i

Since the problem guarantees there's exactly one solution, our loop will always find a pair and return it.

Let's trace nums = [2, 7, 11, 15], target = 9:

`i`	`num`	`complement = 9 - num`	`complement` in `seen_numbers`?	Action	`seen_numbers`
0	2	`9 - 2 = 7`	No (map is empty)	Add `2: 0` to `seen_numbers`	`{2: 0}`
1	7	`9 - 7 = 2`	Yes (2 is in map, at index 0)	Return `[seen_numbers[2], 1]` which is `[0, 1]`	(Function exits)

Boom! We found it on the second step. Much faster than checking 2 with 7, 11, 15 and then 7 with 11, 15, etc.

💻 The Code

Here's the Python implementation of our approach:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hash map (Python dictionary)
        # It will store numbers we've seen and their indices: {number: index}
        hashmap = {} 

        # Iterate through the array 'nums' along with their indices
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed to reach the target
            complement = target - num

            # Check if this 'complement' is already in our hash map
            if complement in hashmap:
                # If yes, we found the pair!
                # The index of the complement is hashmap[complement]
                # The index of the current number is 'i'
                return [hashmap[complement], i]

            # If the complement was NOT found, it means the current 'num'
            # is not the second part of a pair with any number we've seen yet.
            # So, we add the current 'num' and its 'index' to the hash map,
            # so future numbers can check against it.
            hashmap[num] = i

        # This line is technically unreachable due to the problem constraint
        # "Only one valid answer exists." meaning we'll always return inside the loop.
        # However, for completeness in a real-world scenario, you might raise an error
        # or return an empty list if no solution were guaranteed.
        return []

⏱️ Time & Space Complexity Analysis

Understanding how efficient our code is crucial for competitive programming and good software design.

Time Complexity: O(N)
- We iterate through the nums array once.
- Inside the loop, operations like calculating the complement, checking if an element in a hash map, and adding an element to a hash map (hashmap[num] = i) all take, on average, constant time (O(1)).
- Since we do a constant amount of work for each of the N elements, the total time complexity is O(N). This is fantastic! It means if the list doubles in size, the time to solve it roughly doubles, which is very efficient.
Space Complexity: O(N)
- In the worst-case scenario, our hash map hashmap might end up storing almost all the numbers from the nums array and their indices. This would happen if the two numbers that sum to the target are the very last two numbers in the array.
- Therefore, the space used by the hash map grows proportionally to the number of elements in nums. So, the space complexity is O(N).

This O(N) time and O(N) space solution is a significant improvement over the brute-force O(N^2) time complexity!

🎯 Key Takeaways

Hash Maps are Your Friends: When you need to quickly check if an element exists or retrieve its associated value (like an index), hash maps (dictionaries in Python) are incredibly powerful. They offer average O(1) lookups and insertions.
The "Complement" Pattern: For problems asking you to find pairs that sum to a target, thinking about the complement (target - current_number) can often lead to an efficient solution using a hash map.
Optimize Beyond Brute Force: Always consider simpler, less efficient solutions first (like brute force) to understand the problem, then challenge yourself to find more optimized approaches. O(N^2) often becomes O(N) with the right data structure.
Read Constraints Carefully: "Exactly one solution" and "cannot use the same element twice" simplify the problem by removing edge cases you might otherwise need to handle.

Congratulations! You've just conquered LeetCode's "Two Sum" problem using an efficient, industry-standard approach. This problem is a foundational building block, and mastering it sets you up for success in many more algorithmic challenges. Keep practicing, keep learning, and happy coding! 🚀

Author Account: NavyaSree_14
Time Published: 2026-05-16 16:21:00

LeetCode Solution: 153. Find Minimum in Rotated Sorted Array

Vansh Aggarwal — Fri, 15 May 2026 11:06:52 +0000

Master the Mystery: Finding the Minimum in a Rotated Sorted Array!

Hey LeetCoders and aspiring developers! 👋 Vansh2710 here, ready to demystify another classic algorithm problem that often pops up in interviews and challenges our problem-solving skills. Today, we're tackling LeetCode 153: "Find Minimum in Rotated Sorted Array."

This problem is a fantastic introduction to how binary search, a technique you might think is only for perfectly sorted arrays, can be cleverly adapted to solve more complex scenarios. Ready to dive in? Let's go!

The Problem: A Twisted Tale of Sorted Numbers

Imagine you have a perfectly sorted array of unique numbers, like [0, 1, 2, 4, 5, 6, 7]. Simple enough, right? The minimum is clearly 0.

Now, here's the twist: this array gets "rotated." This means some number of elements from the end are moved to the beginning.

Example: [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] if it was rotated 4 times. Or, [7, 0, 1, 2, 4, 5, 6] if rotated once.

Your mission, should you choose to accept it, is to find the minimum element in this rotated sorted array. The kicker? Your algorithm must run in O(log n) time. This immediately screams "binary search" to a competitive programmer, but how do we apply it to a "broken" sorted array? That's the fun part!

The "Aha!" Moment: Binary Search's Hidden Power

At first glance, an array like [4,5,6,7,0,1,2] doesn't look sorted. But wait! It's partially sorted. It's actually two sorted arrays mashed together. The minimum element is the "pivot" where the ascending order breaks.

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

The left part: [4,5,6,7] (sorted)
The right part: [0,1,2] (sorted)
The minimum 0 is the first element of the right part.

Our "aha!" moment is realizing that we can still use the core idea of binary search: discarding half of the search space in each step. The trick is figuring out which half to discard.

The key insight: If we compare the middle element (nums[mid]) with the rightmost element (nums[e]), we can tell which "side" the minimum element is on.

If nums[mid] > nums[e]: This means mid is in the "larger" sorted part (e.g., 7 in [4,5,6,7,0,1,2]). The minimum must be in the elements to the right of mid.
If nums[mid] <= nums[e]: This means mid is in the "smaller" sorted part (e.g., 0 in [4,5,6,7,0,1,2]). The minimum is either mid itself or somewhere to its left.

This simple comparison is our compass in the rotated array jungle!

The Approach: Navigating with Binary Search

Let's break down the binary search logic step-by-step:

Initialize Pointers:
- s (start) to 0
- e (end) to nums.size() - 1
Loop Condition: Continue as long as s < e. When s equals e, we've narrowed down our search to a single element, which must be the minimum.
Calculate Midpoint: mid = s + (e - s) / 2. This prevents potential integer overflow compared to (s + e) / 2.
Decision Time! Compare nums[mid] with nums[e]:

*   **Case 1: `nums[mid] > nums[e]`**
    *   This tells us that the pivot (minimum element) *must* be located somewhere to the **right** of `mid`. Why? Because `nums[mid]` is part of the "larger" sorted segment, and `nums[e]` is part of the "smaller" segment. For `nums[mid]` to be greater than `nums[e]`, the break point (the minimum) has to be between `mid` and `e` (inclusive of `e`).
    *   So, we update `s = mid + 1`.

*   **Case 2: `nums[mid] <= nums[e]`**
    *   This implies two possibilities:
        1.  `nums[mid]` is the minimum itself.
        2.  The minimum is somewhere in the left half of the array (including `mid`).
    *   In both scenarios, `mid` or an element to its left could be the minimum. We can safely discard the right half *after* `mid`.
    *   So, we update `e = mid`.

Termination: When the while loop finishes (s == e), the pointer s (or e) will be pointing to the minimum element. Return nums[s].

Let's quickly trace [3,4,5,1,2] (Example 1):

Initial: s=0, e=4, nums = [3,4,5,1,2]
Iteration 1:
- mid = 0 + (4-0)/2 = 2. nums[mid] = nums[2] = 5.
- nums[mid] (5) > nums[e] (2) is True.
- Minimum is to the right. s = mid + 1 = 3.
- State: s=3, e=4.
Iteration 2:
- mid = 3 + (4-3)/2 = 3. nums[mid] = nums[3] = 1.
- nums[mid] (1) <= nums[e] (2) is True.
- Minimum is at or to the left. e = mid = 3.
- State: s=3, e=3.
Loop ends because s is no longer less than e.
Return nums[s] = nums[3] = 1. Correct!

The Code 🧑‍💻

Here's the C++ implementation following our logic:

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int s = 0;
        int e = nums.size() - 1;

        // Loop until s and e meet (or cross, but in this specific binary search variant, they meet)
        while (s < e) {
            int mid = s + (e - s) / 2; // Calculate midpoint to prevent overflow

            // If nums[mid] is greater than nums[e], it means mid is in the 'left' sorted part
            // and the minimum must be in the elements to the right of mid.
            if (nums[mid] >= nums[e]) {
                s = mid + 1;
            }
            // Otherwise, nums[mid] is less than or equal to nums[e].
            // This means mid is in the 'right' sorted part (or is the minimum).
            // The minimum could be mid itself, or something to its left.
            else {
                e = mid;
            }
        }

        // When the loop terminates, s == e, and this index points to the minimum element.
        return nums[s];
    }
};

Time & Space Complexity Analysis

Time Complexity: O(log n)
- Each step of our binary search effectively halves the search space. This is the hallmark of logarithmic time complexity. Regardless of how large n gets, the number of operations grows very slowly.
Space Complexity: O(1)
- We are only using a few extra variables (s, e, mid) to keep track of our pointers. The amount of memory used doesn't scale with the input size n.

Key Takeaways

Binary Search Adaptability: Don't limit binary search to perfectly sorted arrays. Look for properties that allow you to discard half of the search space.
Pivot Point: In rotated sorted arrays, the minimum element acts as a "pivot" or a "break" in the otherwise sorted order.
Comparison Strategy: Comparing nums[mid] with nums[e] is a powerful technique to determine which half contains the minimum in this specific problem.
Edge Cases: The algorithm gracefully handles cases where the array isn't rotated at all (e.g., [1,2,3,4,5] where nums[mid] <= nums[e] will always be true, eventually e will be 0 and nums[0] is returned).

And there you have it! Finding the minimum in a rotated sorted array using an elegant O(log n) binary search solution. This problem is a fantastic way to deepen your understanding of binary search and its versatility. Keep practicing, and you'll master these algorithmic patterns in no time!

Happy coding!

Author Account: Vansh2710
Time Published: 2026-05-15 16:35:29

LeetCode Solution: 2784. Check if Array is Good

Vansh Aggarwal — Thu, 14 May 2026 17:16:05 +0000

Cracking LeetCode 2784: Is This Array "Good"? Let's Find Out!

Hey everyone! Vansh2710 here, your friendly neighborhood competitive programmer and technical writing enthusiast! Today, we're diving into a fun little LeetCode problem that's perfect for beginners to sharpen their logical thinking: 2784. Check if Array is Good.

Don't let the "permutation" jargon scare you. We'll break it down step by step and discover an elegant solution together. Ready to level up your LeetCode game? Let's go!

🚀 Problem Explanation: What Makes an Array "Good"?

Imagine you have a special kind of array called base[n]. This base[n] array always looks like this:

[1, 2, ..., n - 1, n, n]

In plain English, it's an array of length n + 1 that contains:

All numbers from 1 up to n - 1 appear exactly once.
The number n appears exactly twice.

For example:

If n = 1, then base[1] = [1, 1]. (Length 1+1=2)
If n = 3, then base[3] = [1, 2, 3, 3]. (Length 3+1=4)
If n = 5, then base[5] = [1, 2, 3, 4, 5, 5]. (Length 5+1=6)

The problem asks us to determine if a given array nums is a permutation of one of these base[n] arrays. "Permutation" just means it contains the same numbers, just possibly in a different order.

Let's look at the examples:

nums = [2, 1, 3]
- The largest number is 3. So, if this were a base[n] array, n must be 3.
- base[3] should be [1, 2, 3, 3], which has 4 elements.
- But nums has only 3 elements. So, it cannot be base[3]. Output: false.
nums = [1, 3, 3, 2]
- The largest number is 3. So, n must be 3.
- base[3] is [1, 2, 3, 3].
- nums also has 4 elements, just like base[3].
- Can we rearrange [1, 3, 3, 2] to get [1, 2, 3, 3]? Yes! They contain the exact same numbers with the same counts. Output: true.
nums = [3, 4, 4, 1, 2, 1]
- Largest number is 4. So, n must be 4.
- base[4] should be [1, 2, 3, 4, 4], which has 5 elements.
- But nums has 6 elements. It's too long! Output: false.

See? It's all about checking the elements, their counts, and the array's length!

💡 Intuition: The "Aha!" Moment

When you're trying to figure out if an array is a "permutation" of another specific array structure, the first thing that often comes to mind is sorting. If two arrays are permutations of each other, they will be identical once sorted.

So, if nums is a "good" array, after sorting it, it should exactly match [1, 2, ..., n - 1, n, n].

But what is n? The problem examples give us a HUGE hint: n is always the maximum value present in the nums array. If the nums array is supposed to be base[n], then n is the highest number appearing twice, and n-1 is the next highest. So, n must be the largest element.

Once we figure out n (by finding the maximum value in nums), we can determine two key properties that nums must satisfy:

Length Check: nums must have n + 1 elements.
Content Check: After sorting, nums must look exactly like [1, 2, ..., n - 1, n, n].

If nums passes both these checks, it's a "good" array!

🧠 Approach: Step-by-Step Logic

Let's put our intuition into a concrete plan:

Determine the Candidate n:
- Find the maximum element in the input array nums. Let's call this max_val. This max_val is our candidate n from base[n].
Initial Length Check:
- The base[n] array always has a length of n + 1.
- Check if the nums.size() (the actual number of elements in nums) is equal to max_val + 1.
- If nums.size() is not equal to max_val + 1, then nums cannot be a permutation of base[max_val]. Immediately return false.
Sort the Array:
- Sort the nums array in non-decreasing order. This makes it easy to check the pattern [1, 2, ..., n - 1, n, n].
Verify Elements in Order:
- After sorting, we expect the elements to be 1, 2, ..., max_val - 1, max_val, max_val.
- Loop from i = 0 up to max_val - 2 (which means checking elements nums[0] through nums[max_val - 2]).
- In this loop, for each i, check if nums[i] is equal to i + 1. If it's not, it means we don't have the sequence 1, 2, 3, .... Return false.
- Special Case: What if max_val is 1? If max_val = 1, then base[1] = [1, 1]. The loop i from 0 to max_val - 2 (i.e., 0 to -1) won't run, which is correct. We only need to check the two 1s.
Verify the Duplicate n (or max_val):
- After the loop, we need to check the last two elements. These should both be max_val.
- Since nums.size() is max_val + 1, the elements are at indices 0 to max_val.
- So, we need to check if nums[max_val - 1] is equal to max_val AND nums[max_val] is equal to max_val.
- If both these conditions are true, then nums has the required duplicate max_val. If not, return false.
All Checks Passed:
- If we've made it this far, it means nums has the correct length, and its sorted elements match the base[max_val] pattern. Return true.

This approach covers all the conditions systematically and efficiently!

💻 Code: Bringing the Logic to Life

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

#include <vector>
#include <algorithm> // Required for std::sort and std::max_element

class Solution {
public:
    bool isGood(std::vector<int>& nums) {
        int current_size = nums.size();

        // Step 1: Determine the candidate 'n' (max_val)
        // If the array is empty, it can't be good (constraints say nums.length >= 1)
        // If only one element, max_element will still work.
        int max_val = 0;
        for (int x : nums) {
            if (x > max_val) {
                max_val = x;
            }
        }
        // An alternative using std::max_element (requires <algorithm>):
        // int max_val = *std::max_element(nums.begin(), nums.end());


        // Step 2: Initial Length Check
        // base[max_val] has length max_val + 1
        if (current_size != max_val + 1) {
            return false;
        }

        // Step 3: Sort the Array
        std::sort(nums.begin(), nums.end());

        // Step 4: Verify Elements 1 to (max_val - 1)
        // Loop up to max_val - 1 (exclusive, so indices 0 to max_val - 2)
        // For example, if max_val = 3, we check nums[0] == 1, nums[1] == 2.
        for (int i = 0; i < max_val - 1; ++i) {
            if (nums[i] != i + 1) {
                return false;
            }
        }

        // Step 5: Verify the Duplicate 'n' (max_val)
        // The last two elements should both be max_val.
        // These are at indices max_val - 1 and max_val (since current_size = max_val + 1)
        if (nums[max_val - 1] != max_val || nums[max_val] != max_val) {
            return false;
        }

        // Step 6: All Checks Passed
        return true;
    }
};

⏱️ Time & Space Complexity Analysis

Let's break down the efficiency of our solution:

Time Complexity:
- Finding max_val: We iterate through nums once. This takes O(N) time, where N is nums.size().
- Sorting nums: Using std::sort on a std::vector takes O(N log N) time on average.
- Checking elements after sorting: We loop through nums at most N times (specifically max_val times, which is roughly N). This takes O(N) time.
- Overall: The dominant factor is the sorting step. Therefore, the total time complexity is O(N log N).
Space Complexity:
- max_val and current_size variables: These use O(1) constant space.
- std::sort: For std::vector, std::sort typically uses an introspection sort algorithm, which has O(log N) auxiliary space complexity for its recursive calls (or O(N) in worst-case for heapsort partition, but often considered in-place or O(log N) for the stack). For competitive programming contexts, it's often effectively treated as O(1) additional space if it sorts in-place. Let's consider it as O(1) (ignoring recursion stack space if small enough, or O(log N) more precisely for a typical implementation).

🎯 Key Takeaways

Deconstruct the Problem: Break down complex definitions (like base[n]) into simpler rules (length, distinct elements, duplicate element).
Leverage Hints: The example explanations often provide crucial clues, like how to determine n (it's the max element!).
Sorting is Your Friend: For problems involving permutations or specific ordered structures, sorting is often the most straightforward way to normalize the input for easy validation.
Edge Cases Matter: Always consider small n values (like n=1) to ensure your logic holds. Our loop condition i < max_val - 1 correctly handles max_val = 1 by not running the loop, which is perfect as base[1] only needs [1, 1] checks.
Systematic Checks: Go through each requirement (length, distinct elements, duplicate elements) one by one. If any check fails, you can immediately return false.

This problem is a fantastic warm-up to understanding how to translate descriptive array properties into a clear, implementable algorithm. Keep practicing!

Vansh2710
Published: 2026-05-14 22:44:58