DEV Community: Vansh Aggarwal

LeetCode Solution: 48. Rotate Image

Vansh Aggarwal — Mon, 04 May 2026 06:35:20 +0000

Spin That Image! Rotating a 2D Matrix Like a Pro (LeetCode #48)

Hey fellow coders and aspiring problem-solvers! 👋 Vansh here, diving into another classic LeetCode challenge that's more about visual thinking than complex algorithms. Today, we're tackling problem #48: Rotate Image.

This one is fantastic because it pushes us to think in-place, meaning we can't just create a new matrix and copy rotated values. We have to be clever and modify the original! Ready to give your matrix a spin? Let's go!

Understanding the Challenge: Rotate That Image!

You're given a square 2D matrix (think of it like a grid or an image made of pixels). Your task is to rotate this "image" by 90 degrees clockwise.

The catch? You must do it in-place. No creating a brand new matrix to store the result. You have to transform the given matrix directly.

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

Example 1: A simple 3x3 matrix

Input:

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

Imagine physically turning this piece of paper 90 degrees clockwise.

Output:

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

Notice how 1 (top-left) moves to (0, 2) (top-right of new matrix), 3 (top-right) moves to (2, 2) (bottom-right of new matrix), and so on.

The "Aha!" Moment: Two Simple Steps to Rotation

Rotating an image 90 degrees clockwise in-place might seem tricky at first. If you try to move elements one by one, you'll quickly realize you need to store temporary values to avoid overwriting numbers you still need. That can get messy fast!

But what if we could break down this complex rotation into simpler, more intuitive transformations?

The "aha!" moment comes when you realize that a 90-degree clockwise rotation can be achieved by two fundamental operations:

Transpose the matrix: This means swapping elements across its main diagonal. matrix[i][j] becomes matrix[j][i].
Reverse each row: After transposing, each row needs to be reversed to get the final clockwise rotation.

Let's visualize this with our 3x3 example:

Original Matrix:

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

Step 1: Transpose (Swap (0,1) with (1,0), (0,2) with (2,0), (1,2) with (2,1))

[[1, 4, 7],   <-- 1 (0,0) stays, 2 (0,1) swapped with 4 (1,0), 3 (0,2) swapped with 7 (2,0)
 [2, 5, 8],   <-- 5 (1,1) stays, 6 (1,2) swapped with 8 (2,1)
 [3, 6, 9]]   <-- 9 (2,2) stays

Step 2: Reverse Each Row
Row 0: [1, 4, 7] becomes [7, 4, 1]
Row 1: [2, 5, 8] becomes [8, 5, 2]
Row 2: [3, 6, 9] becomes [9, 6, 3]

Final Rotated Matrix:

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

Voila! This matches our desired output. This two-step process does the job perfectly, and it's all done in-place!

The Step-by-Step Approach

Let's break down how to implement these two steps efficiently in code.

Step 1: Transposing the Matrix

To transpose a matrix in-place, we iterate through the upper triangle of the matrix and swap matrix[i][j] with matrix[j][i]. We only need to consider j starting from i + 1 to avoid:

Swapping elements twice (e.g., swapping (0,1) with (1,0) and then (1,0) with (0,1) again would revert the change).
Swapping elements on the main diagonal with themselves (e.g., (0,0) with (0,0)).

Algorithm for Transposition:

Get the size of the matrix, n.
Loop with i from 0 to n-1 (for rows).
Inside this, loop with j from i+1 to n-1 (for columns, starting from i+1).
Swap matrix[i][j] with matrix[j][i].

Step 2: Reversing Each Row

After transposition, each individual row needs to be reversed. This is a straightforward operation.

Algorithm for Reversing Rows:

Loop with i from 0 to n-1 (for each row).
For each matrix[i], use a reverse function (most languages have one built-in for containers like vectors or arrays) to reverse its elements. If not, you can implement a simple two-pointer swap from start and end of the row.

And that's it! These two operations combined give you the 90-degree clockwise rotation, all without using extra space.

The Code (C++)

Here's the C++ implementation of this elegant solution:

#include <vector>
#include <algorithm> // Required for std::swap and std::reverse

class Solution {
public:
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size(); // Get the dimension of the square matrix

        // Step 1: Transpose the matrix
        // Iterate through the upper triangle (j starts from i+1)
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // Swap matrix[i][j] with matrix[j][i]
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Step 2: Reverse each row
        // Iterate through each row and reverse its elements
        for (int i = 0; i < n; ++i) {
            std::reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

Complexity Analysis

Time Complexity:
- Transposition: We have a nested loop. The outer loop runs n times, and the inner loop runs approximately n/2 times on average (j goes from i+1 to n-1). In total, we perform (n-1) + (n-2) + ... + 1 = n*(n-1)/2 swaps. This is proportional to n^2. So, it's O(n^2).
- Reversing Rows: We iterate through n rows. For each row, we iterate through its n elements to reverse them. This also takes O(n * n) = O(n^2) time.
- Overall: The dominant factor is n^2. Therefore, the total time complexity is O(n^2), where n is the dimension of the square matrix.
Space Complexity:
- We are performing all operations directly on the input matrix without allocating any additional matrices or significant data structures. The std::swap and std::reverse operations work in-place.
- Therefore, the space complexity is O(1) (constant space).

Key Takeaways

In-Place Challenges: Problems requiring "in-place" modification often hint at clever manipulations like swapping or using existing memory efficiently.
Decomposition: Complex transformations (like 90-degree rotation) can often be broken down into simpler, sequential operations (like transpose + reverse).
Visual Thinking: Drawing out the matrix and how elements move is incredibly helpful for problems involving 2D arrays.
Standard Library Functions: Don't forget powerful standard library functions like std::swap and std::reverse in C++ (or equivalent in other languages) – they can simplify your code and often are highly optimized.

I hope this breakdown made the "Rotate Image" problem feel less daunting and more like a fun puzzle! Happy coding, and keep spinning those matrices!

Author Account: Vansh2710
Time Published: 2026-05-04 12:03:48

LeetCode Solution: 69. Sqrt(x)

Vansh Aggarwal — Sat, 02 May 2026 13:01:36 +0000

✨ Unlocking `Sqrt(x)`: Your First Dive into Binary Search! 🚀

Hey amazing developers! 👋 Vansh2710 here, ready to embark on another exciting LeetCode adventure with you. Today, we're tackling problem #69: Sqrt(x). Sounds simple, right? Just find the square root! But here's the twist: we can't use any fancy built-in functions. We're going old-school and building our own square root finder from scratch. Get ready to discover the magic of Binary Search!

🧐 Problem Explanation: What are we actually doing?

The problem asks us to find the square root of a given non-negative integer x. The catch? We need to round down the result to the nearest whole number. So, if sqrt(x) is 2.828..., we return 2. And a critical constraint: NO built-in functions like pow(x, 0.5) or x ** 0.5 allowed! This means we have to come up with our own algorithm.

Let's look at the examples:

Example 1: x = 4
- The square root of 4 is exactly 2.
- Output: 2
Example 2: x = 8
- The actual square root of 8 is approximately 2.82842...
- When we round this down to the nearest integer, we get 2.
- Output: 2

The constraints tell us x can be pretty large (0 <= x <= 2^31 - 1), so our solution needs to be efficient!

🤔 Intuition: How would you guess the square root?

Imagine you're a human calculator, and I ask you to find the square root of, say, 49. How would you do it without a calculator?

You'd probably start guessing:

"Is it 1? 1 * 1 = 1 (Too small!)"
"Is it 10? 10 * 10 = 100 (Too big!)"
"Okay, somewhere between 1 and 10. Let's try 5. 5 * 5 = 25 (Still too small!)"
"Let's try 8. 8 * 8 = 64 (Too big!)"
"Okay, between 5 and 8. How about 7? 7 * 7 = 49 (Bingo! Just right!)"

Notice a pattern here? You're constantly narrowing down your search space based on whether your guess squared is too small or too big. This exact thought process is the cornerstone of an incredibly powerful algorithm: Binary Search!

🚀 Approach: Binary Search to the Rescue!

Binary Search is perfect for problems where you need to find a specific value within a sorted range or determine a "point" where a condition changes (like y*y goes from less than x to greater than x).

Here's how we'll apply it:

Define our Search Space: What's the smallest possible square root for x? 0 (for x=0). What's the largest? It can't be more than x itself (e.g., sqrt(1) is 1). So, our search range will be from 0 (or 1 if we handle x=0 separately) to x. Let's call these s (start) and e (end).
Iterate and Conquer: We'll keep guessing the midpoint of our s and e range.

*   Initialize `s = 0` (or `1`), `e = x`.
*   Also, initialize an `ans` variable to store our best possible rounded-down answer, starting at `0` (or `1`).

The Loop: While s is less than or equal to e (meaning our search space is still valid):

*   **Calculate `mid`:** `mid = s + (e - s) / 2;` (This way of calculating `mid` prevents potential integer overflow compared to `(s+e)/2` if `s` and `e` are very large).

*   **Calculate `square`:** `long long square = mid * mid;`
    *   **CRITICAL STEP:** We use `long long` here! Why? Because `x` can be up to `2^31 - 1`. If `mid` is, say, `60000`, `mid * mid` is `3,600,000,000`, which is larger than the maximum value for a standard `int` (`~2*10^9`). Using `long long` prevents overflow and ensures our calculations are accurate.

*   **Compare `square` with `x`:**
    *   **Case 1: `square == x`**
        *   We found the exact square root! Return `mid` immediately.
    *   **Case 2: `square < x`**
        *   `mid` is too small, or it *could* be our rounded-down answer, but we might find a larger, more accurate one.
        *   So, we store `mid` in `ans` (because `mid` is the largest integer whose square is `_less than or equal to_ x` *so far*).
        *   Then, we search in the **right half** to find a potentially larger `mid`: `s = mid + 1;`
    *   **Case 3: `square > x`**
        *   `mid` is too big. Its square exceeds `x`.
        *   We need to search in the **left half**: `e = mid - 1;`

Return ans: After the loop finishes (when s becomes greater than e), our ans variable will hold the largest integer y such that y * y <= x. This is precisely the square root of x rounded down!

💻 Code (C++)

class Solution {
public:
    int mySqrt(int x) {
        // Handle edge case for x = 0
        if (x == 0) {
            return 0;
        }

        // Initialize our binary search range
        // The square root of x will be between 1 and x
        long long s = 1;         // 's' for start
        long long e = x;         // 'e' for end
        long long ans = 1;       // To store the potential answer (rounded down)

        // Perform binary search
        while (s <= e) {
            // Calculate mid-point. Using this formula to prevent potential overflow
            // if s and e were both very large and their sum exceeded MAX_INT
            long long mid = s + (e - s) / 2;

            // Calculate the square of mid. Use long long to prevent overflow
            // since mid * mid could exceed the maximum value of an int.
            long long square = mid * mid;

            if (square == x) {
                // Found the exact square root, return it
                return mid;
            } else if (square < x) {
                // mid is too small, or it could be our rounded-down answer.
                // We keep mid as a potential answer and try to find a larger one
                // by searching in the right half.
                ans = mid;
                s = mid + 1;
            } else { // square > x
                // mid is too large, search in the left half
                e = mid - 1;
            }
        }

        // After the loop, 'ans' holds the largest integer whose square is less than or equal to x.
        // This is our square root rounded down.
        return ans;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log x)
- Binary search works by repeatedly halving the search space. If our initial search space has N elements (in our case, x possibilities), it takes log N steps to find the target. Here, N is roughly x, so it's O(log x). This is super efficient for large x!
Space Complexity: O(1)
- We are only using a few variables (s, e, mid, square, ans) regardless of the input x. We don't use any extra data structures that grow with the input size.

🎯 Key Takeaways

Binary Search is Versatile: It's not just for finding exact values! It's incredibly powerful for finding "thresholds" or "transition points" in a sorted or monotonically changing range (like y*y increasing as y increases).
Beware of Integer Overflow: Always be mindful of the maximum possible values your variables can hold, especially when multiplying large numbers. long long is your friend!
Rounded Down Logic: When a problem asks for a rounded-down (floor) value, you often need to keep track of the "best valid answer so far" when your mid is still too small, but potentially correct.

This problem is a fantastic introduction to the elegance and efficiency of binary search. Keep practicing, and you'll master it in no time! Happy coding!

Author Account: Vansh2710
Time Published: 2026-05-02 18:31:13

LeetCode Solution: 69. Sqrt(x)

Vansh Aggarwal — Sat, 02 May 2026 12:56:20 +0000

Unlocking the Power of Binary Search: Solving Sqrt(x) ⚡

Hey awesome coders! 👋 Vansh here, ready to demystify another LeetCode classic. Today, we're tackling problem 69: Sqrt(x). Sounds simple, right? Just find the square root! But here's the twist: we can't use any fancy built-in functions like pow(x, 0.5) or x ** 0.5. This challenge pushes us to think deeper and build our own solution from scratch.

Don't worry, even if you're just starting your coding journey, we'll break down this problem step by step, making it super accessible and fun! By the end, you'll have a powerful new tool in your algorithmic belt: Binary Search.

🧐 Problem Explanation: What are we actually doing?

Imagine you're given a number, let's say x. Your mission is to find its square root. But there's a catch: you need to round the result down to the nearest whole number.

For example:

If x = 4, the square root is exactly 2. So, we return 2.
If x = 8, the square root is approximately 2.82842.... Since we need to round down, we return 2.

The problem also tells us x will always be a non-negative integer. And remember, no built-in square root functions allowed!

🤔 Intuition: The "Aha!" Moment

How would you find the square root of a number x if you could only use multiplication and comparison?

Let's take x = 25.

Is 1 * 1 equal to 25? No, too small.
Is 2 * 2 equal to 25? No.
...
Is 5 * 5 equal to 25? Yes! So 5 is the answer.

What about x = 8?

1 * 1 = 1 (too small)
2 * 2 = 4 (too small)
3 * 3 = 9 (too large!)

Since 3 * 3 is too large, and 2 * 2 is the largest square less than or equal to 8, our answer (rounded down) must be 2.

Notice a pattern? As we try larger numbers, their squares also get larger. This monotonic property (always increasing) is a huge hint! It screams Binary Search!

Binary search is super efficient for finding a target value within a sorted range. Here, we're looking for a number ans such that ans * ans <= x and (ans + 1) * (ans + 1) > x.

🚶‍♀️ Approach: Step-by-Step with Binary Search

Let's outline our binary search strategy:

Define Search Space: What's the possible range for our square root?
- The smallest possible square root is 0 (for x=0).
- The largest possible square root for x will be x itself (since 1*1=1, x*x will be much larger than x unless x=1 or x=0). So, our search space [start, end] can be [0, x]. For x=0, the answer is 0. For x=1, the answer is 1. We can safely start our search from 1 if x > 0.
Initialize Variables:
- s (start): 1 (or 0 for x=0 edge case)
- e (end): x
- ans: A variable to store our potential answer, initialized to 0. This will eventually hold the largest mid whose square is less than or equal to x.
The Loop: We'll use a while loop that continues as long as s <= e.
Calculate mid: In each iteration, find the middle of our current search space:
mid = s + (e - s) / 2;
This way of calculating mid (s + (e - s) / 2) is safer than (s + e) / 2 because it prevents potential integer overflow if s and e are very large.
Calculate square: Compute the square of mid:
long long int square = mid * mid;
Crucial Point: mid * mid can become very large and exceed the maximum value of an int if x is large (e.g., x = 2^31 - 1). To prevent overflow, we must use long long int for square.
Compare and Adjust:
- If square == x: We found the exact square root! Return mid.
- If square < x: This mid is a potential candidate for our answer (since we need to round down, and its square is not too big). Store mid in ans. Now, we need to check if we can find an even larger number whose square is still less than or equal to x. So, we shift our search to the right half: s = mid + 1;
- If square > x: This mid is too large, its square exceeds x. We need to look for smaller numbers. So, we shift our search to the left half: e = mid - 1;
Return ans: Once the loop finishes (s > e), ans will hold the largest integer whose square was less than or equal to x. This is exactly our desired rounded-down square root!

💻 Code

Let's put it all together in C++:

class Solution {
public:
    int mySqrt(int x) {
        // Handle edge case for x = 0 separately
        if (x == 0) {
            return 0;
        }

        // Initialize our search range
        // The square root of x will be between 1 and x (inclusive for x=1)
        long long s = 1;
        long long e = x;

        // 'ans' will store the potential answer (the largest integer whose square is <= x)
        long long ans = 0;

        // Perform binary search
        while (s <= e) {
            // Calculate mid to prevent potential integer overflow for large s and e
            long long mid = s + (e - s) / 2;

            // Calculate the square of mid.
            // Use long long to prevent overflow if mid * mid exceeds int max value.
            long long square = mid * mid;

            if (square == x) {
                // Found the exact square root, return it immediately
                return mid;
            } else if (square < x) {
                // If mid*mid is less than x, mid could be our answer.
                // Store it and try to find a larger potential answer in the right half.
                ans = mid;
                s = mid + 1;
            } else { // square > x
                // If mid*mid is greater than x, mid is too large.
                // Search in the left half.
                e = mid - 1;
            }
        }

        // After the loop, 'ans' holds the largest integer whose square is less than or equal to x.
        // This is the square root rounded down.
        return ans;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log x)
Binary search works by repeatedly dividing the search space in half. For a search space of size x, it takes log x operations to find the target. This is incredibly efficient!
Space Complexity: O(1)
We are only using a few constant variables (s, e, mid, ans, square) regardless of the input x. Therefore, the space complexity is constant.

✨ Key Takeaways

Binary Search Power: Whenever you see a problem asking to find a value within a sorted (or monotonically increasing/decreasing) range, think Binary Search!
Preventing Overflow: Be mindful of potential integer overflows, especially when multiplying large numbers. Using long long int is a common fix.
Rounding Down: For "round down" problems, binary search often involves storing a potential_answer and then trying to find a better one in the appropriate half.

This problem is a fantastic entry point into binary search and a great way to build your foundational algorithmic skills. Keep practicing, and you'll be a LeetCode master in no time! Happy coding! 🚀

^{Authored by Vansh2710 | Published on 2026-05-02 18:25:11}

LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

Vansh Aggarwal — Fri, 01 May 2026 18:04:20 +0000

Finding Your Way: First and Last Occurrences in a Sorted Array (LeetCode 34 Explained!)

Hey there, future coding rockstars! 👋 Vansh here, and today we're diving into a super common, yet incredibly insightful problem from LeetCode: "Find First and Last Position of Element in Sorted Array."

This problem is a fantastic way to level up your understanding of one of the most fundamental algorithms out there: Binary Search. While simple binary search finds if an element exists, this problem challenges us to find its boundaries in a sorted list. Let's break it down!

🔍 Problem Explanation: What are We Even Doing?

Imagine you have a phonebook (remember those?) where all names are sorted alphabetically. Now, imagine you're looking for every "Smith" in that phonebook. You don't just want any Smith; you want to know where the first "Smith" starts and where the last "Smith" ends. That's exactly what this problem asks!

Formally, we're given:

An array of integers nums. Crucially, this array is sorted in non-decreasing order (meaning numbers either stay the same or go up).
A target integer value.

Our mission:

Find the starting index (first occurrence) of target.
Find the ending index (last occurrence) of target.
Return these as an array [start_index, end_index].
If the target isn't found anywhere in nums, we should return [-1, -1].

The kicker? We must do this with an O(log n) runtime complexity. This is a strong hint for using Binary Search!

Let's look at a few examples:

Example 1: nums = [5,7,7,8,8,10], target = 8

The first 8 is at index 3.
The last 8 is at index 4.
Output: [3, 4]

Example 2: nums = [5,7,7,8,8,10], target = 6

6 is not in the array.
Output: [-1, -1]

Example 3: nums = [], target = 0

The array is empty. 0 can't be found.
Output: [-1, -1]

🤔 Intuition: The "Aha!" Moment

When you see a sorted array and an O(log n) complexity requirement, your brain should immediately scream: BINARY SEARCH!

A standard binary search helps you find if an element exists and its index. But here, if target appears multiple times, a standard binary search might give you any of its occurrences, not necessarily the first or last.

The "aha!" moment is realizing that we can adapt binary search to specifically look for the leftmost (first) occurrence and then, with a slight modification, for the rightmost (last) occurrence.

Think about it:

To find the first occurrence: If we find the target at mid, we store this mid as a potential answer, but then we try to find an even earlier target by continuing our search in the left half of the current array (end = mid - 1).
To find the last occurrence: If we find the target at mid, we store this mid as a potential answer, but then we try to find an even later target by continuing our search in the right half of the current array (start = mid + 1).

This way, we "squeeze" our search space until we pinpoint the extreme positions!

🪜 Approach: Step-by-Step Logic

We'll essentially perform two separate binary searches: one for the first occurrence and one for the last occurrence.

Let's define a helper function, say find_occurrence(nums, target, find_first), that can do both based on a flag.

1. `find_occurrence(nums, target, find_first)` Function Logic:

Initialize ans = -1. This will store our found index.
Initialize start = 0 and end = len(nums) - 1. These define our search space.
While start <= end:
- Calculate mid = start + (end - start) // 2. (Using (end - start) // 2 instead of (start + end) // 2 helps prevent potential integer overflow for very large start and end values, though less critical in Python).
- Case 1: nums[mid] == target
  - We found a target! Store mid in ans.
  - Now, the crucial part:
    - If find_first is True (we're looking for the first occurrence): We know mid could be our first, but there might be an even earlier one. So, we shrink our search space to the left: end = mid - 1.
    - If find_first is False (we're looking for the last occurrence): We know mid could be our last, but there might be an even later one. So, we shrink our search space to the right: start = mid + 1.
- Case 2: nums[mid] < target
  - The target must be in the right half (if it exists). Shift our search to the right: start = mid + 1.
- Case 3: nums[mid] > target
  - The target must be in the left half (if it exists). Shift our search to the left: end = mid - 1.
Return ans.

2. Main Function Logic:

Call find_occurrence(nums, target, True) to get the first_occurrence.
Call find_occurrence(nums, target, False) to get the last_occurrence.
Return [first_occurrence, last_occurrence].

This elegant modification to binary search allows us to pinpoint both boundaries efficiently!

💻 Code

Here's the Python implementation based on our approach:

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:

        def find_occurrence(nums, target, find_first):
            """
            Helper function to find either the first or last occurrence of the target.

            Args:
                nums (list): The sorted array.
                target (int): The value to search for.
                find_first (bool): If True, search for the first occurrence.
                                   If False, search for the last occurrence.

            Returns:
                int: The index of the found occurrence, or -1 if not found.
            """
            ans = -1
            start = 0
            end = len(nums) - 1

            while start <= end:
                mid = start + (end - start) // 2

                if nums[mid] == target:
                    ans = mid  # Store potential answer
                    if find_first:
                        end = mid - 1 # Try to find an even earlier occurrence on the left
                    else:
                        start = mid + 1 # Try to find an even later occurrence on the right
                elif nums[mid] < target:
                    start = mid + 1 # Target is in the right half
                else: # nums[mid] > target
                    end = mid - 1 # Target is in the left half
            return ans

        # Find the first occurrence
        first_pos = find_occurrence(nums, target, True)

        # Find the last occurrence
        last_pos = find_occurrence(nums, target, False)

        return [first_pos, last_pos]

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log n)
- We perform two independent binary searches. Each binary search takes O(log n) time because we repeatedly halve the search space. Therefore, O(log n) + O(log n) simplifies to O(log n). This satisfies the problem's constraint!
Space Complexity: O(1)
- We only use a few constant extra variables (start, end, mid, ans). We don't allocate any data structures that grow with the input size n.

💡 Key Takeaways

Binary Search is your best friend for sorted arrays! Always consider it when you see "sorted" and "O(log n)".
Binary Search isn't just for exact matches. It's a versatile algorithm that can be adapted to find boundaries, closest elements, and more, with slight modifications to its core logic (especially how you adjust start and end when nums[mid] == target).
Modularize your code. Breaking down the problem into a helper function for find_occurrence makes the main searchRange function clean, readable, and less repetitive.

This problem is a fantastic stepping stone from basic binary search to more complex variations. Master this, and you'll be well on your way to tackling trickier search problems!

Happy coding! ✨

Author: Vansh2710 | Published: 2026-05-01 23:33:33

LeetCode Solution: 74. Search a 2D Matrix

Vansh Aggarwal — Thu, 30 Apr 2026 17:11:20 +0000

LeetCode 74: Search a 2D Matrix - Conquer the Grid with Binary Search!

Hey fellow coders and problem-solvers! 👋 Vansh2710 here, diving into another LeetCode adventure. Today, we're tackling a classic problem that brilliantly combines the elegance of a sorted structure with the power of binary search: "Search a 2D Matrix".

This problem is a fantastic stepping stone for understanding how seemingly complex 2D data structures can often be simplified and optimized using fundamental algorithms. Ready to unlock its secrets? Let's go!

Problem Explanation: What's the Challenge?

Imagine you're given a special kind of grid, an m x n matrix, filled with integers. This isn't just any grid, though; it has two super helpful properties:

Each row is sorted: If you pick any row and read it from left to right, the numbers are always increasing (non-decreasing, to be precise).
Rows are also "sorted" relative to each other: The very first number in any given row is always greater than the very last number of the row directly above it. Think of it like a staircase where each step starts higher than the previous one ended.

Your mission? Given this unique matrix and a target integer, you need to figure out if target exists anywhere in this matrix. The catch? You must do it super efficiently, in O(log(m * n)) time.

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

Example 1:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true (Because 3 is in the first row!)

Example 2:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false (13 is nowhere to be found in this matrix.)

Notice how the numbers 1,3,5,7 are sorted. Then 10 (first of second row) is greater than 7 (last of first row). 10,11,16,20 are sorted. 23 (first of third row) is greater than 20 (last of second row). This pattern is key!

Intuition: The "Aha!" Moment 💡

When you hear "sorted data" and "logarithmic time complexity" in the same sentence, what's the first algorithm that pops into your mind? If you thought Binary Search, you're absolutely on the right track!

Binary search works wonders on 1D sorted arrays. But we have a 2D matrix here. How can we apply binary search to it?

This is where the magic happens! Look at those two properties again:

Each row is sorted.
The first element of a row is greater than the last element of the previous row.

These two properties combined mean that if you were to "flatten" or "unroll" this entire 2D matrix into a single 1D array, that resulting 1D array would also be perfectly sorted!

Imagine taking all elements from the first row, then all elements from the second row, and so on, and concatenating them. You'd get something like [1,3,5,7,10,11,16,20,23,30,34,60]. See? It's completely sorted!

So, the "aha!" moment is: We can treat this 2D matrix as a single, giant, sorted 1D array and perform a standard binary search on it!

Approach: From 2D to 1D (and Back!)

Our strategy will be to simulate a binary search on this "flattened" 1D array. But how do we access elements if we're only actually given a 2D matrix? We need a way to map the index of an element in our conceptual 1D array back to its corresponding (row, column) in the original 2D matrix.

Let's say our matrix has m rows and n columns. The total number of elements is m * n.
If we have a 1D index k (where k ranges from 0 to (m*n - 1)), how do we find its (row, col) in the 2D matrix?

Row Calculation: In a matrix with n columns, each row contains n elements. So, an element at 1D index k would be in row k / n (integer division).
Column Calculation: Within that row, its column index would be k % n (remainder after division by n).

For example, in a 3x4 matrix (n=4 columns):

1D index 0 -> (0/4, 0%4) -> (0, 0)
1D index 3 -> (3/4, 3%4) -> (0, 3)
1D index 4 -> (4/4, 4%4) -> (1, 0) (This is the start of the second row!)
1D index 7 -> (7/4, 7%4) -> (1, 3)
1D index 8 -> (8/4, 8%4) -> (2, 0) (Start of the third row!)

This mapping is the core of our solution!

Here's the step-by-step approach:

Initialize Pointers:
- start: Set to 0 (representing the first element of our conceptual 1D array).
- end: Set to (m * n) - 1 (representing the last element).
Binary Search Loop: Continue as long as start <= end.
Calculate Midpoint:
- mid = start + (end - start) / 2 (This prevents potential integer overflow compared to (start + end) / 2).
Map Midpoint to 2D Coordinates:
- currentRow = mid / numberOfColumns
- currentColumn = mid % numberOfColumns
Retrieve Element: Get element = matrix[currentRow][currentColumn].
Compare and Adjust Pointers:
- If element == target: We found it! Return true.
- If element < target: The target is larger, so we need to search in the right half of our conceptual array. Update start = mid + 1.
- If element > target: The target is smaller, so we need to search in the left half. Update end = mid - 1.
Target Not Found: If the loop finishes without finding the target, it means the target isn't in the matrix. Return false.

Code 🖥️

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

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Get the dimensions of the matrix
        int numRows = matrix.size();
        if (numRows == 0) return false; // Handle empty matrix edge case

        int numCols = matrix[0].size();
        if (numCols == 0) return false; // Handle empty rows edge case

        // Initialize binary search pointers for the conceptual 1D array
        int start = 0;
        int end = (numRows * numCols) - 1; // Total elements - 1

        // Perform binary search
        while (start <= end) {
            // Calculate the middle index for the 1D conceptual array
            int mid = start + (end - start) / 2;

            // Map the 1D 'mid' index back to 2D (row, col) coordinates
            int elementRow = mid / numCols;
            int elementCol = mid % numCols;

            // Get the element at the calculated 2D coordinates
            int element = matrix[elementRow][elementCol];

            // Compare the element with the target
            if (element == target) {
                return true; // Target found!
            } else if (element < target) {
                // Element is too small, search in the right half
                start = mid + 1;
            } else {
                // Element is too large, search in the left half
                end = mid - 1;
            }
        }

        // If the loop finishes, the target was not found
        return false;
    }
};

Time & Space Complexity Analysis

Time Complexity: O(log(m * n))
- We are performing a binary search on a conceptual 1D array of m * n elements.
- In each step of binary search, we cut the search space in half.
- Therefore, the number of operations is proportional to the logarithm of the total number of elements.
Space Complexity: O(1)
- We are only using a few extra variables (start, end, mid, numRows, numCols, etc.) which take up constant extra space regardless of the input matrix size.

This solution perfectly meets the O(log(m * n)) requirement!

Key Takeaways

Binary Search Power: Don't limit binary search to just 1D arrays! It can be applied to any data structure that can be conceptually "flattened" into a sorted sequence.
2D to 1D Mapping: Understanding how to convert a 1D index to 2D coordinates (index / numCols for row, index % numCols for column) is a powerful technique for grid problems.
Leverage Properties: Always pay close attention to the problem constraints and properties. The two "sorted" properties were the keys that unlocked this efficient solution.
Edge Cases: Remember to handle edge cases like empty matrices or empty rows, though the problem constraints (1 <= m, n) might sometimes make this less critical depending on the platform's test cases.

That's it for LeetCode 74! I hope this breakdown helped you understand how to approach and solve this problem efficiently. Binary search is truly a fundamental algorithm, and seeing its application in a 2D context is a great way to solidify your understanding.

Happy coding!

Author Account: Vansh2710
Published: 2026-04-30 22:40:57

LeetCode Solution: 74. Search a 2D Matrix

Vansh Aggarwal — Thu, 30 Apr 2026 17:04:43 +0000

Conquer the Sorted Labyrinth: Searching a 2D Matrix with Binary Search Magic! ✨

Hey LeetCoders and aspiring developers! Vansh2710 here, ready to demystify another classic problem that's far simpler than it looks, especially if you know a neat trick. Today, we're diving into LeetCode problem 74: "Search a 2D Matrix."

This problem is a fantastic way to solidify your understanding of binary search and see how it can be applied in seemingly non-standard situations. If you've ever felt intimidated by anything beyond a simple sorted array, this post is for you!

The Quest: Search a 2D Matrix

Imagine you have a spreadsheet filled with numbers, but it has two very special properties:

Each row is perfectly sorted: From left to right, the numbers in every row are in increasing order.
Rows are also "sorted" relative to each other: The very first number in any row is always larger than the very last number of the row directly above it.

Here's an example:

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

Notice how 7 (last in row 0) is less than 10 (first in row 1), and 20 (last in row 1) is less than 23 (first in row 2). This is a crucial detail!

Your mission? Given this matrix and an integer target, you need to figure out if target exists anywhere in the matrix. You also have a secret constraint: your solution must be super-efficient, running in O(log(m * n)) time. That's a big hint!

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true (3 is right there in the first row!)

Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false (13 is nowhere to be found in this matrix.)

The "Aha!" Moment: Flattening the Matrix (Mentally!)

At first glance, you might think of iterating through each row and then doing a binary search on that row. That's a decent start, but it might not hit our O(log(m * n)) target directly. A binary search on m rows, each of length n, would be O(m * log n) in the worst case (if we had to search every row).

However, those two special properties of the matrix are screaming a secret: this 2D matrix behaves exactly like a single, giant, perfectly sorted 1D array!

Think about it:
If you take the first row [1, 3, 5, 7], then the second row [10, 11, 16, 20], and so on, and just concatenate them all together, you'd get:
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

This new "flattened" array is completely sorted! And what do we use for finding elements efficiently in a sorted array? Binary Search!

The "aha!" is realizing we don't actually need to flatten the array. We can just pretend it's a 1D array and use clever math to translate our 1D binary search indices back into 2D (row, column) coordinates.

The Approach: Binary Search on a Virtual 1D Array

Here's how we apply the binary search magic:

Count Elements: First, determine the total number of elements in the matrix. If the matrix has m rows and n columns, the total number of elements is m * n. Let's call this totalElements.
Define Search Space:
- Our "virtual" 1D array has indices from 0 to totalElements - 1.
- Initialize start = 0 and end = totalElements - 1.
Binary Search Loop: Continue as long as start <= end.
- Calculate mid: Find the middle index using mid = start + (end - start) / 2. This formula helps prevent integer overflow compared to (start + end) / 2.
- Convert 1D mid to 2D (row, column): This is the clever part!
  - The row index for our mid element will be mid / n (integer division).
  - The column index for our mid element will be mid % n (modulo operator).
  - Why does this work? Imagine a 1D array mapped to a 2D grid. The first n elements are in row 0, the next n elements are in row 1, and so on. mid / n tells you how many full rows mid has "passed", giving you its row. mid % n tells you its position within that specific row.
- Get the element: Retrieve the actual value from the matrix using matrix[mid / n][mid % n].
- Compare and Adjust:
  - If element == target: Congratulations! You found it. Return true.
  - If element < target: The target must be in the "right half" of our virtual array (i.e., larger values). So, update start = mid + 1.
  - If element > target: The target must be in the "left half" of our virtual array (i.e., smaller values). So, update end = mid - 1.
Not Found: If the loop finishes (meaning start became greater than end), it means the target was not present in the matrix. Return false.

That's it! By treating the 2D matrix as a flat, sorted 1D array, we can leverage the power of binary search directly.

The Code

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

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Get dimensions of the matrix
        int numRows = matrix.size();
        if (numRows == 0) return false; // Handle empty matrix edge case

        int numCols = matrix[0].size();
        if (numCols == 0) return false; // Handle empty rows edge case

        // Initialize binary search pointers for our virtual 1D array
        int start = 0;
        // Total number of elements, our 1D array's last index
        int end = (numRows * numCols) - 1; 

        // Standard binary search loop
        while (start <= end) {
            // Calculate mid-point, preventing potential overflow
            int mid = start + (end - start) / 2;

            // Convert the 1D 'mid' index back to 2D (row, column) coordinates
            // row = mid / numCols
            // col = mid % numCols
            int element = matrix[mid / numCols][mid % numCols];

            // Compare the element at mid with the target
            if (element == target) {
                return true; // Target found!
            } else if (element < target) {
                // Target is larger, so search in the right half
                start = mid + 1;
            } else { // element > target
                // Target is smaller, so search in the left half
                end = mid - 1;
            }
        }

        // If the loop completes, the target was not found
        return false;
    }
};

Complexity Analysis

This is where our clever approach truly shines!

Aspect	Complexity	Explanation
Time Complexity	`O(log(m * n))`	We perform a binary search over `m * n` elements. Each step reduces the search space by half.
Space Complexity	`O(1)`	We only use a few constant extra variables (`start`, `end`, `mid`, `numRows`, `numCols`, `element`), regardless of the input matrix size.

This beautifully meets the O(log(m * n)) time complexity requirement!

Key Takeaways

Look for Hidden Order: Many problems, especially involving matrices, might have implicit properties that transform them into simpler, well-known data structures (like a sorted array).
Binary Search Power: Binary search isn't just for 1D arrays! With a little mathematical mapping, it can be applied to 2D structures or even more complex search spaces.
1D to 2D Index Mapping: Remember the trick: row = index / num_cols and col = index % num_cols is your go-to for converting a 1D index to 2D coordinates.
Efficiency Matters: Understanding the time and space complexity helps you choose the most optimal algorithm, especially in competitive programming.

I hope this breakdown helped you understand how to approach this problem and empowered you to look for creative binary search applications! Keep coding, keep learning, and see you in the next post!

Author: Vansh2710 | Published: 2026-04-30 22:33:53

LeetCode Solution: 283. Move Zeroes

Vansh Aggarwal — Sun, 26 Apr 2026 18:08:06 +0000

Zeroes Got You Down? Let's Kick 'Em to the Curb! (LeetCode 283: Move Zeroes)

Hey there, future coding rockstars! 👋 Vansh2710 here, and today we're tackling a super common, yet incredibly insightful, LeetCode problem: 283. Move Zeroes. This problem is a fantastic introduction to a powerful technique and teaches us to think cleverly about modifying arrays.

Don't let the simplicity fool you; mastering this kind of problem builds a solid foundation for much tougher challenges. Ready to make those zeroes move? Let's dive in!

The Problem: Zeroes on the Loose!

Imagine you have a list of numbers, like [0, 1, 0, 3, 12]. Your mission, should you choose to accept it, is to rearrange this list so that all the zeroes are at the very end. But there are a couple of crucial rules:

Maintain Relative Order: The non-zero numbers must stay in their original order. So, 1 must still come before 3, and 3 before 12. You can't just sort the array!
- [0, 1, 0, 3, 12] should become [1, 3, 12, 0, 0], not [0, 0, 1, 3, 12] or [1, 12, 3, 0, 0].
In-Place Modification: This is the big one! You can't create a new array and copy elements over. You have to modify the original array directly. This is like tidying up your room without using an extra box to put things into temporarily – you're just moving things around within the existing space.

Example 1:
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2:
Input: nums = [0]
Output: [0]

Seems simple enough, right? But the "in-place" and "relative order" constraints make us think a little more deeply!

The "Aha!" Moment: Focus on What Matters!

When faced with a problem that asks us to move certain elements to the end while maintaining the order of others, a common pitfall is to try and move the "bad" elements (the zeroes) to their destination directly. You might think, "If I see a zero, swap it with the next element until it's at the end!" But this quickly gets messy and breaks the relative order of non-zeroes.

Instead, let's flip our perspective: what if we focus on the elements we want to keep in order – the non-zero numbers?

The "aha!" moment here is realizing that we can effectively "collect" all the non-zero elements at the beginning of the array, in their correct relative order. Once we've done that, all the remaining spots at the end of the array must be zeroes. This way, we ensure both the relative order and the in-place requirement.

Our Strategy: The Two-Pointer Dance!

This problem is a classic candidate for the two-pointer technique. We'll use two pointers:

nonZeroPointer: This pointer will keep track of where the next non-zero element should be placed. It essentially marks the boundary between the "non-zero section" and the "unknown/zero section" of our array. It starts at the beginning (index 0).
i (or currentPointer): This pointer will iterate through the entire array from left to right, checking each element.

Here's the step-by-step breakdown:

Initialize nonZeroPointer to 0. This is where our first non-zero number will go.
Iterate through the array with i (from 0 to nums.size() - 1).
For each nums[i]:
- If nums[i] is NOT a zero: This is a number we want to keep at the beginning!
  - We put nums[i] at nums[nonZeroPointer].
  - Crucially, if i and nonZeroPointer are different, it means we just moved a non-zero number from a later position (i) to an earlier position (nonZeroPointer). The element that was originally at nums[i] (which was a zero that we overwrote, or a non-zero that we moved) is now at nums[nonZeroPointer]. To ensure the "fill with zeroes" part implicitly, we perform a swap. If i and nonZeroPointer are the same, it means nums[i] is already in its correct non-zero position, and we don't need to swap it with itself.
  - Increment nonZeroPointer by 1, because the spot it was pointing to is now filled with a non-zero value, and the next non-zero should go to the next available spot.
After the loop finishes, all non-zero elements will be at the beginning of the array, in their correct relative order. All elements from nonZeroPointer to the end of the array will implicitly be zeroes (due to the swaps moving zeroes out of the way or overwriting them with zeroes when i == nonZeroPointer).

Let's trace [0, 1, 0, 3, 12]:

`i`	`nums[i]`	`nonZeroPointer`	`nums` (before swap)	Condition `(nums[i] != 0)`	Action	`nums` (after swap)
0	0	0	`[0, 1, 0, 3, 12]`	False	None	`[0, 1, 0, 3, 12]`
1	1	0	`[0, 1, 0, 3, 12]`	True	`swap(nums[1], nums[0])`; `nonZeroPointer` becomes 1	`[1, 0, 0, 3, 12]`
2	0	1	`[1, 0, 0, 3, 12]`	False	None	`[1, 0, 0, 3, 12]`
3	3	1	`[1, 0, 0, 3, 12]`	True	`swap(nums[3], nums[1])`; `nonZeroPointer` becomes 2	`[1, 3, 0, 0, 12]`
4	12	2	`[1, 3, 0, 0, 12]`	True	`swap(nums[4], nums[2])`; `nonZeroPointer` becomes 3	`[1, 3, 12, 0, 0]`

Loop ends. The array is [1, 3, 12, 0, 0]. Perfect!

The Code

#include <vector> // Required for std::vector
#include <algorithm> // Required for std::swap

class Solution {
public:
    void moveZeroes(std::vector<int>& nums) {
        int nonZeroPointer = 0; // Pointer for the next position for a non-zero element

        // Iterate through the array with 'i'
        for (int i = 0; i < nums.size(); ++i) {
            // If the current element is non-zero,
            // it means we found an element that belongs in the non-zero section
            if (nums[i] != 0) {
                // If 'i' and 'nonZeroPointer' are different, it means
                // nums[i] is a non-zero element and nonZeroPointer is pointing
                // to a zero (or an element that will be a zero after the swap).
                // We swap to move the non-zero element to its correct position.
                // If i == nonZeroPointer, the element is already in place,
                // so we don't need to swap it with itself.
                if (i != nonZeroPointer) {
                    std::swap(nums[i], nums[nonZeroPointer]);
                }
                // Move the nonZeroPointer forward, indicating the next spot
                // for another non-zero element.
                nonZeroPointer++;
            }
        }
    }
};

Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(N)
- We iterate through the array exactly once with our i pointer.
- Inside the loop, operations like if checks, !=, and swap take constant time, O(1).
- Therefore, the total time complexity is directly proportional to the number of elements in the array, N.
Space Complexity: O(1)
- We are modifying the array directly "in-place" without creating any auxiliary data structures that scale with the input size.
- The nonZeroPointer and i variables only take up a constant amount of extra space.

This solution is highly optimized, satisfying the "minimize total number of operations" follow-up as it performs at most N swaps and N comparisons.

Key Takeaways

Two-Pointer Power: The two-pointer technique is your best friend for array manipulation problems, especially those involving sorting, partitioning, or relative ordering.
In-Place Challenges: When a problem demands "in-place" modification, think about how you can reuse the existing memory. Often, this involves overwriting elements or clever swapping.
Flip the Perspective: Sometimes, focusing on what you don't want can be harder than focusing on what you do want. Instead of chasing zeroes, we collected non-zeroes.
Practice Makes Perfect: This problem might seem straightforward now, but the "aha!" moment comes with practice. Keep solving, keep thinking, and soon these patterns will be second nature!

Happy coding, and may your arrays always be perfectly ordered!

Author Account: Vansh2710
Time Published: 2026-04-26 23:36:47

LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

Vansh Aggarwal — Sat, 25 Apr 2026 17:56:15 +0000

Uncover the Hidden Range: Finding First & Last Occurrences in Sorted Arrays (LeetCode #34)

Hey everyone! Vansh2710 here, diving deep into another classic LeetCode problem that might seem tricky at first, but unravels beautifully with a touch of algorithmic magic. Today, we're tackling problem #34: Find First and Last Position of Element in Sorted Array.

This problem is a fantastic way to stretch your understanding of one of the most fundamental algorithms: Binary Search! Ready to find those elusive boundaries? Let's get started!

Problem Explanation

Imagine you have a super organized bookshelf where all the books are sorted alphabetically. Now, someone asks you to find all copies of "The Great Gatsby" and tell them exactly where the first one starts and the last one ends on the shelf. That's essentially what we're doing here!

Given an array of integers nums that is already sorted in non-decreasing order (meaning numbers are either increasing or staying the same), and a specific target integer:

We need to find the starting index (first occurrence) and the ending index (last occurrence) of the target value in nums.
If the target isn't found anywhere in the array, we should return [-1, -1].
Crucially, your solution must run in O(log n) time complexity. This is a massive hint!

Let's look at the examples:

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
(The first '8' is at index 3, the last '8' is at index 4)

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
(6 is not in the array)

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
(Empty array, target cannot be found)

Constraints to keep in mind:

The array nums can be empty or have up to 10^5 elements.
Numbers and target can be quite large or small (negative values included).
nums is guaranteed to be sorted non-decreasingly.

Intuition: The "Aha!" Moment

The moment you see "sorted array" and "O(log n) runtime complexity" in the same sentence, your brain should immediately yell "BINARY SEARCH!" 🚀

A standard binary search is excellent for telling you if an element exists in a sorted array, and if so, it typically returns one of its indices. But here, we need two specific indices: the very first and the very last.

So, how do we adapt our trusty binary search? Instead of stopping once we find the target, we need to keep searching!

If we find the target and we're looking for the first occurrence, we mark that index as a potential answer, but then we try to find an even earlier target by searching in the left half of the current segment.
Conversely, if we find the target and we're looking for the last occurrence, we mark that index and then try to find an even later target by searching in the right half.

This tweak transforms our standard binary search into a powerful tool for finding boundaries!

Approach: Two-Pronged Binary Search

Our strategy will involve two separate, slightly modified binary searches:

find_first_occurrence(nums, target): This function will find the index of the first target in the array.
find_last_occurrence(nums, target): This function will find the index of the last target in the array.

Let's detail each one:

1. Finding the First Occurrence

Initialize ans = -1 (this will store our result, default to not found).
Set start = 0 and end = len(nums) - 1.
While start <= end:
- Calculate mid = start + (end - start) // 2 to prevent potential integer overflow.
- If nums[mid] == target:
  - We found the target! This mid could be our first occurrence. Store it: ans = mid.
  - But wait, there might be an even earlier target to its left. So, we try to shrink our search space to the left: end = mid - 1.
- If nums[mid] < target:
  - The target must be in the right half (or not present). So, search right: start = mid + 1.
- If nums[mid] > target:
  - The target must be in the left half (or not present). So, search left: end = mid - 1.
Return ans.

2. Finding the Last Occurrence

Initialize ans = -1.
Set start = 0 and end = len(nums) - 1.
While start <= end:
- Calculate mid = start + (end - start) // 2.
- If nums[mid] == target:
  - We found the target! This mid could be our last occurrence. Store it: ans = mid.
  - But wait, there might be an even later target to its right. So, we try to shrink our search space to the right: start = mid + 1.
- If nums[mid] < target:
  - The target must be in the right half (or not present). So, search right: start = mid + 1.
- If nums[mid] > target:
  - The target must be in the left half (or not present). So, search left: end = mid - 1.
Return ans.

Finally, our main searchRange function will simply call these two helper functions and return their results as [first_occurrence, last_occurrence].

Code

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        # Helper function to find the first occurrence of the target
        def find_first_occurrence(arr: list[int], val: int) -> int:
            ans = -1
            left, right = 0, len(arr) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == val:
                    ans = mid      # Potentially the first occurrence
                    right = mid - 1 # Try to find an even earlier occurrence in the left half
                elif arr[mid] < val:
                    left = mid + 1
                else: # arr[mid] > val
                    right = mid - 1
            return ans

        # Helper function to find the last occurrence of the target
        def find_last_occurrence(arr: list[int], val: int) -> int:
            ans = -1
            left, right = 0, len(arr) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == val:
                    ans = mid     # Potentially the last occurrence
                    left = mid + 1 # Try to find an even later occurrence in the right half
                elif arr[mid] < val:
                    left = mid + 1
                else: # arr[mid] > val
                    right = mid - 1
            return ans

        first = find_first_occurrence(nums, target)
        last = find_last_occurrence(nums, target)

        return [first, last]

Time & Space Complexity Analysis

Let's break down the efficiency of our solution:

Time Complexity: O(log n)

We perform two independent binary searches: find_first_occurrence and find_last_occurrence.
Each binary search operates on a sorted array of n elements and halves its search space in each step. This gives each individual search a time complexity of O(log n).
Since we do two of these operations sequentially, the total time complexity is O(log n) + O(log n), which simplifies to O(log n).
This perfectly satisfies the problem's constraint!

Space Complexity: O(1)

Our solution uses a few constant variables (left, right, mid, ans).
We are not using any auxiliary data structures that grow with the input size n (like extra arrays or lists).
Therefore, the space complexity is O(1).

Key Takeaways

Binary Search Power-Up: Binary search isn't just for checking existence! By carefully adjusting the start and end pointers when nums[mid] == target, you can find specific boundaries like first/last occurrences, smallest element greater than target, etc.
Two Searches for Two Boundaries: For problems requiring both a start and an end index in a sorted array, often two slightly modified binary searches are the most straightforward and efficient approach.
Edge Cases: Always consider empty arrays or cases where the target isn't found. Our solution handles these gracefully by initializing ans = -1 and letting the binary search naturally return it if no target is ever found.
mid Calculation: Using mid = left + (right - left) // 2 is a good practice to prevent potential integer overflow, especially in languages like C++ where left + right could exceed MAX_INT for very large left and right. In Python, this is less critical due to arbitrary precision integers, but it's a good habit!

Hopefully, this breakdown helps you understand how to approach range-finding problems in sorted arrays! Keep practicing, and you'll master these variations in no time. Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-25 23:25:30

LeetCode Solution: 7. Reverse Integer

Vansh Aggarwal — Thu, 23 Apr 2026 19:52:22 +0000

Cracking LeetCode 7: Reversing Integers Without Breaking the Bank (or the Integer Limit!) 🚀

Hey everyone! Vansh here, ready to dive into another classic LeetCode problem that might seem simple on the surface but hides a crucial twist: integer overflow. Today, we're tackling LeetCode Problem 7: Reverse Integer.

This problem is a fantastic stepping stone for beginners because it teaches you not just about basic arithmetic manipulations but also about handling the often-overlooked boundaries of data types. Let's get cracking!

Understanding the Challenge: Reverse Integer 🔄

Imagine you have a number, say 123. The goal is to reverse its digits to get 321. Sounds easy, right? What if it's -123? Then it should be -321. And 120 should become 21 (leading zeros are dropped).

Here's the catch: We're dealing with a signed 32-bit integer. This means our number x can range from -2,147,483,648 (which is -2³¹) to 2,147,483,647 (which is 2³¹ - 1).

If, after reversing the digits, the number goes outside this specific range, we're supposed to return 0. And to make things spicier, we cannot use 64-bit integers to store our result temporarily. This constraint forces us to be clever with our overflow checks!

Let's look at the examples:

Input: x = 123 Output: 321 (Perfectly within range)
Input: x = -123 Output: -321 (Also good!)
Input: x = 120 Output: 21 (Trailing zero vanishes, as expected)
Consider this tricky one: If x = 2147483647 (the maximum 32-bit integer), reversing it would give 7463847412. This number is much larger than 2147483647, so we should return 0. This is where the overflow check comes in!

The "Aha!" Moment: Intuition ✨

How do we reverse a number, digit by digit? Think about how you'd get the last digit of a number and then remove it.

Get the last digit: The modulo operator (%) is our best friend here! 123 % 10 gives 3.
Remove the last digit: Integer division (/) does the trick! 123 / 10 gives 12.
Build the reversed number: If our reversed_num starts at 0, and we get a digit, we can do reversed_num = reversed_num * 10 + digit.
- Start: reversed_num = 0
- x = 123, digit = 3. reversed_num = 0 * 10 + 3 = 3. x = 12.
- x = 12, digit = 2. reversed_num = 3 * 10 + 2 = 32. x = 1.
- x = 1, digit = 1. reversed_num = 32 * 10 + 1 = 321. x = 0.
- Loop ends! We have 321.

This basic process works perfectly. But remember the overflow constraint? That's the real "aha!" moment. We can't just let reversed_num * 10 + digit happen blindly. We need to check for potential overflow before it occurs, because once an integer overflows, its value becomes unpredictable (or wraps around, which is incorrect for this problem).

The trick for overflow is to check if reversed_num is already too large (or too small) such that multiplying it by 10 or adding the next digit would push it past INT_MAX or INT_MIN. Specifically, we check if reversed_num > INT_MAX / 10 or reversed_num < INT_MIN / 10. If reversed_num equals these thresholds, we need a final check on the digit.

Step-by-Step Approach 🚶‍♂️

Let's outline our robust approach:

Initialize result: We'll need a variable, let's call it result, to store our reversed number. Initialize it to 0.
Loop while x is not 0: We continue this process until all digits from x have been extracted.
Extract the last digit:
- int digit = x % 10;
Crucial Overflow Check (before updating result!): This is the heart of handling the constraints.
- Positive Overflow Check:
  - If result is already greater than INT_MAX / 10, then multiplying result by 10 will definitely overflow. Return 0.
  - If result is exactly equal to INT_MAX / 10, then we need to check the digit. INT_MAX ends in 7 (2,147,483,647). If our digit is greater than 7 (i.e., 8 or 9), then result * 10 + digit will overflow. Return 0.
- Negative Overflow Check:
  - If result is already less than INT_MIN / 10, then multiplying result by 10 will definitely underflow. Return 0.
  - If result is exactly equal to INT_MIN / 10, then we need to check the digit. INT_MIN ends in 8 (-2,147,483,648). If our digit is less than -8 (i.e., -9), then result * 10 + digit will underflow. Return 0.
Build the reversed number:
- result = result * 10 + digit;
Remove the last digit from x:
- x = x / 10;
Return result: Once the loop finishes, result holds our fully reversed integer (or 0 if an overflow was detected).

This approach handles positive numbers, negative numbers, and most importantly, gracefully manages the overflow conditions without needing 64-bit integers!

The Code 💻

Here's the C++ implementation using the INT_MAX and INT_MIN constants found in <limits.h> (or <climits> for C++):

#include <limits.h> // Required for INT_MAX and INT_MIN

class Solution {
public:
    int reverse(int x) {
        int result = 0; // This will store our reversed integer

        while (x != 0) {
            // Step 1: Extract the last digit
            int digit = x % 10;

            // Step 2: Crucial Overflow Check BEFORE updating result
            // Check for potential positive overflow:
            // If result is already greater than INT_MAX / 10, then multiplying by 10 will surely overflow.
            // If result is exactly INT_MAX / 10, then adding a digit > 7 will cause overflow (since INT_MAX is 2,147,483,647).
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
                return 0;
            }

            // Check for potential negative overflow (underflow):
            // If result is already less than INT_MIN / 10, then multiplying by 10 will surely underflow.
            // If result is exactly INT_MIN / 10, then adding a digit < -8 will cause underflow (since INT_MIN is -2,147,483,648).
            if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
                return 0;
            }

            // Step 3: Build the reversed number
            result = result * 10 + digit;

            // Step 4: Remove the last digit from the original number
            x = x / 10;
        }

        return result; // Return the final reversed integer
    }
};

Time & Space Complexity Analysis ⏱️📏

Time Complexity: O(log |x|)
We iterate through the digits of the input number x. The number of digits in an integer x is proportional to log10(|x|). For example, a 1-digit number takes 1 iteration, a 2-digit number takes 2 iterations, and so on. Since we process each digit exactly once, the time complexity is logarithmic with respect to the absolute value of x.
Space Complexity: O(1)
We use a fixed number of variables (result, digit). The amount of memory used does not grow with the size of the input x. Hence, the space complexity is constant.

Key Takeaways 💡

Digit Manipulation: The modulo (% 10) and integer division (/ 10) operators are your go-to tools for extracting and removing digits from an integer.
Building Numbers: To construct a number from individual digits, multiply the current result by 10 and add the new digit.
Overflow is Critical: Always be mindful of integer limits, especially in competitive programming problems where data type constraints are common.
Pre-emptive Checks: For overflow problems where a larger data type isn't allowed, check for overflow before performing operations that might cause it. The INT_MAX / 10 and INT_MIN / 10 trick is a standard way to do this.

This problem is a fantastic blend of basic arithmetic and careful edge-case handling. Master it, and you'll be well on your way to tackling more complex LeetCode challenges!

Happy coding! 👩‍💻👨‍💻

Author Account: Vansh2710
Published: 2026-04-24 01:21:55

LeetCode Solution: 7. Reverse Integer

Vansh Aggarwal — Thu, 23 Apr 2026 19:14:28 +0000

Brain Teaser: Can You Reverse an Integer Without Breaking the Bank? (LeetCode #7)

Hey there, fellow coding adventurers! 👋 Vansh2710 here, ready to dive into another classic LeetCode challenge. Today, we're tackling problem #7: Reverse Integer. It sounds super simple, right? Just flip the digits! But as with many LeetCode problems, there's a sneaky little twist that makes it a fantastic learning experience about handling real-world integer limits.

Let's unravel this puzzle together!

📚 Problem Explanation: The Core Challenge

Imagine you have a number, say 123. Your task is to reverse its digits to get 321. Sounds simple, right? What about negative numbers? If x = -123, the output should be -321. And if x = 120, the reversed number is 21 (we naturally drop leading zeros, so 021 becomes 21).

Here's the catch: We're dealing with a "signed 32-bit integer". This means our numbers have a strict upper and lower limit: they can go from (-2^31) to (2^31 - 1). That's roughly from -2 billion to +2 billion. If reversing the number causes it to go beyond these limits (an "overflow"), your function must return 0.

And another critical rule: You cannot use 64-bit integers (like long long in C++) to store your result temporarily. This forces us to be clever with our overflow checks!

Examples:

Input: x = 123 Output: 321
Input: x = -123 Output: -321
Input: x = 120 Output: 21

🧠 Intuition: How Do We "Flip" Numbers Digit by Digit?

Let's break down the mechanics of reversing a number. How would you do it manually, one digit at a time?

Getting the Last Digit: To grab the last digit of any integer, we can use the modulo operator (% 10).
- For 123, 123 % 10 gives 3.
- For 12, 12 % 10 gives 2.
- For 1, 1 % 10 gives 1.
Removing the Last Digit: After we've extracted a digit, we need to chop it off the original number. We can do this with integer division (/ 10).
- For 123, 123 / 10 gives 12.
- For 12, 12 / 10 gives 1.
- For 1, 1 / 10 gives 0.
Building the Reversed Number: We need a variable to store our reversed number, let's call it reversed_num, initialized to 0. Each time we extract a digit, we'll "shift" our current reversed_num one place to the left (by multiplying by 10) and then add the new digit.

Let's trace x = 123:
- Start: x = 123, reversed_num = 0
- Iteration 1:
  - digit = 123 % 10 = 3
  - reversed_num = 0 * 10 + 3 = 3
  - x = 123 / 10 = 12
- Iteration 2:
  - digit = 12 % 10 = 2
  - reversed_num = 3 * 10 + 2 = 32
  - x = 12 / 10 = 1
- Iteration 3:
  - digit = 1 % 10 = 1
  - reversed_num = 32 * 10 + 1 = 321
  - x = 1 / 10 = 0
- Loop ends because x is now 0. Return 321. Perfect!

The "aha!" moment is realizing this iterative process. The BIGGEST "aha!" (and the trickiest part) is figuring out how to check for overflow before it actually happens, because once an integer overflows, its value becomes unpredictable!

🛠️ Approach: The Step-by-Step Logic

Combining our intuition, here's the detailed plan to solve the Reverse Integer problem, keeping the overflow constraint in mind:

Initialize num = 0: This variable will store our result as we build it digit by digit. We're using num as per the provided solution snippet's variable name.
Loop While x is Not Zero: We'll keep extracting digits from x and adding them to num until x becomes 0.
The Critical Overflow Check: This is the most vital part! Before we update num (by multiplying by 10 and adding a new digit), we need to check if this operation will cause num to exceed the INT_MAX (maximum 32-bit integer) or fall below INT_MIN (minimum 32-bit integer).

The specific check provided in the solution snippet is:
if (num > INT_MAX / 10 || num < INT_MIN / 10)

Let's break down why this works:
- INT_MAX is the largest positive 32-bit integer (typically 2,147,483,647).
- INT_MIN is the smallest negative 32-bit integer (typically -2,147,483,648).
- If num is already greater than INT_MAX / 10, then multiplying num by 10 (even before adding the digit) will definitely exceed INT_MAX. For example, if INT_MAX / 10 is roughly 2.1e8, and num is 3e8, then 3e8 * 10 = 3e9 is clearly too big.
- The same logic applies to INT_MIN / 10 for checking negative overflow.
- If this condition is true, we immediately return 0 because an overflow is imminent.
Extract the Last Digit: int digit = x % 10; (e.g., if x=123, digit=3). This digit will be appended to num.
Build the Reversed Number: num = num * 10 + digit;
- This shifts the existing digits in num one position to the left and adds the newly extracted digit to the rightmost position.
Remove the Last Digit from x: x = x / 10;
- This prepares x for the next iteration, effectively "eating away" its digits from right to left.
Return num: Once the while loop finishes (meaning x has become 0 and all digits have been processed), num will hold the correctly reversed integer. If any overflow was detected, we would have returned 0 earlier.

💻 Code: Bringing It All Together (C++)

Here's the C++ implementation following our approach. Note that INT_MAX and INT_MIN are defined in the <limits.h> (or <climits>) header.

#include <limits.h> // Required for INT_MAX and INT_MIN

class Solution {
public:
    int reverse(int x) {
        int num = 0; // This variable will store our reversed number

        // Loop as long as there are digits left in x
        while (x != 0) {
            // --- OVERFLOW CHECK ---
            // This is the critical step. We check for potential overflow *before*
            // we perform the multiplication and addition that could cause it.
            // If 'num' is already so large (or small) that multiplying by 10
            // would exceed INT_MAX (or INT_MIN) even before adding the last digit,
            // we know an overflow is inevitable.
            if (num > INT_MAX / 10 || num < INT_MIN / 10) {
                return 0; // Overflow detected, return 0 as per problem statement
            }
            // --- END OVERFLOW CHECK ---

            // Extract the last digit of x
            int digit = x % 10;

            // Build the reversed number:
            // 1. Multiply 'num' by 10 to shift its existing digits one position to the left.
            // 2. Add the newly extracted 'digit' to the rightmost position.
            num = num * 10 + digit;

            // Remove the last digit from x to process the next digit in the next iteration
            x = x / 10;
        }

        // After the loop, 'num' holds the completely reversed integer
        return num;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log |x|)
- The while loop runs once for each digit in the input number x.
- The number of digits in an integer x is proportional to log10(|x|). For example, log10(100) is 2, meaning 3 digits.
- Therefore, the time complexity is logarithmic with respect to the absolute value of x.
Space Complexity: O(1)
- We are only using a few constant-space variables (num, digit, x).
- The memory usage does not grow with the size of the input number.

🌟 Key Takeaways

Digit Manipulation is Key: The modulo % 10 and integer division / 10 operators are your best friends for breaking down and building numbers digit by digit.
Edge Cases are Crucial: Always consider negative inputs and numbers ending in zero (like 120).
The Overflow Challenge: When working with fixed-size integer types, understanding and implementing pre-emptive overflow checks is paramount. Doing the check before the potentially overflowing operation is the way to go, especially when you can't use larger data types.
Practice Makes Perfect: These types of problems build a strong foundation for thinking about integer properties and constraints.

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

Author Account: Vansh2710
Time Published: 2026-04-24 00:43:37

LeetCode Solution: 7. Reverse Integer

Vansh Aggarwal — Thu, 23 Apr 2026 19:05:49 +0000

🚀 Master LeetCode 7: Reversing Integers Without Breaking the Bank (or Your Code!)

Hey LeetCoders and aspiring developers! 👋 Vansh2710 here, your friendly neighborhood competitive programmer and technical writer. Today, we're diving into a classic LeetCode problem that might seem simple on the surface but hides a crucial detail that trips up many beginners (and even some seasoned folks!): Reverse Integer (Problem 7).

It's a fantastic problem to learn about integer manipulation and, more importantly, how to handle those pesky overflow scenarios. Let's conquer it together!

📖 Problem Explained: The Digit Dilemma

You're given a signed 32-bit integer x. Your task is to return x with its digits reversed. Sounds easy, right?

Here's the catch: If reversing x causes its value to go outside the signed 32-bit integer range (which is [-2^31, 2^31 - 1]), you must return 0. Oh, and you can't use 64-bit integers. This last constraint is key!

Let's look at some examples to get a feel for it:

Example 1:
- Input: x = 123
- Output: 321 (Simple positive reversal)
Example 2:
- Input: x = -123
- Output: -321 (Negative numbers reverse similarly, keeping the sign)
Example 3:
- Input: x = 120
- Output: 21 (Trailing zeros become leading zeros and get dropped)

The core idea seems straightforward, but the "overflow" part is where the real challenge lies!

✨ Intuition: Building Backwards, Digit by Digit

Imagine you have the number 123. How would you "reverse" it manually?

You'd grab the 3.
Then the 2.
Then the 1.

And then you'd put them together as 321.

How can we do this programmatically?

Getting the last digit: The modulo operator (%) is our best friend! 123 % 10 gives us 3.
Removing the last digit: Integer division (/) comes to the rescue! 123 / 10 gives us 12.
Building the reversed number: Let's say we have a reversed_num variable, initially 0.
- When we get 3: reversed_num = 0 * 10 + 3 = 3.
- When we get 2: reversed_num = 3 * 10 + 2 = 32.
- When we get 1: reversed_num = 32 * 10 + 1 = 321.

This "extract-and-build" loop forms the heart of our solution. But wait! What if x is 2147483647 (which is INT_MAX)? Reversing it would give 7463847412, which is much larger than INT_MAX. This is where our overflow check becomes absolutely vital! We need to detect this before it happens.

🧠 Our Step-by-Step Approach

Let's break down the logic into clear, manageable steps:

Initialize reversed_num: We'll need a variable, let's call it reversed_num, initialized to 0. This will store our result as we build it.
Loop While x Has Digits: We'll use a while loop that continues as long as x is not 0. Each iteration will process one digit.
Extract the Last Digit: Inside the loop, get the last digit of x using int digit = x % 10;.
🚨 CRITICAL OVERFLOW CHECK 🚨: This is the most important part! Before we actually update reversed_num with the new digit, we need to check if doing so would cause an overflow (i.e., exceed INT_MAX or go below INT_MIN).
- How to check?
  - If reversed_num is already greater than INT_MAX / 10, then multiplying reversed_num by 10 will definitely overflow.
  - If reversed_num is exactly INT_MAX / 10, then adding a digit greater than 7 (since INT_MAX is 2,147,483,647 and 7 is its last digit) will cause an overflow.
  - Similar logic applies for INT_MIN: if reversed_num < INT_MIN / 10 or (reversed_num == INT_MIN / 10 and digit < -8), it will underflow.
- If any overflow/underflow is detected, immediately return 0 as per the problem statement.
Build reversed_num: If no overflow is detected, safely update reversed_num: reversed_num = reversed_num * 10 + digit;.
Shrink x: Remove the last digit from x by integer division: x /= 10;.
Return Result: Once the loop finishes (meaning x is 0 and all digits have been processed), return the final reversed_num.

✍️ The Code (C++)

Here's the C++ implementation incorporating the logic we just discussed:

#include <limits.h> // Required for INT_MAX and INT_MIN

class Solution {
public:
    int reverse(int x) {
        int reversed_num = 0; // This will store our reversed integer

        // Loop until x becomes 0 (all digits processed)
        while (x != 0) {
            // Extract the last digit of x
            int digit = x % 10;

            // --- CRITICAL OVERFLOW CHECK ---
            // This check must happen BEFORE we update `reversed_num`.
            // We're essentially asking: "If I multiply `reversed_num` by 10
            // and add `digit`, will it go out of bounds?"

            // Positive overflow check:
            // 1. If `reversed_num` is already greater than `INT_MAX / 10`,
            //    multiplying by 10 will *definitely* overflow.
            // 2. If `reversed_num` is exactly `INT_MAX / 10`,
            //    adding `digit` will cause overflow IF `digit` is greater than 7.
            //    (Because INT_MAX = 2,147,483,647, so the last digit is 7).
            if (reversed_num > INT_MAX / 10 || (reversed_num == INT_MAX / 10 && digit > 7)) {
                return 0; // Overflow detected, return 0
            }

            // Negative overflow check:
            // 1. If `reversed_num` is already less than `INT_MIN / 10`,
            //    multiplying by 10 will *definitely* underflow.
            // 2. If `reversed_num` is exactly `INT_MIN / 10`,
            //    adding `digit` will cause underflow IF `digit` is less than -8.
            //    (Because INT_MIN = -2,147,483,648, so the last digit is -8).
            if (reversed_num < INT_MIN / 10 || (reversed_num == INT_MIN / 10 && digit < -8)) {
                return 0; // Underflow detected, return 0
            }

            // If no overflow, safely build the reversed number
            reversed_num = reversed_num * 10 + digit;

            // Remove the last digit from x
            x /= 10;
        }

        // All digits processed, return the final reversed number
        return reversed_num;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log |x|)

Why O(log |x|)?
Because in each iteration of our while loop, we're effectively removing one digit from x (by dividing x by 10). The number of digits in an integer x is proportional to log10 |x|. For a 32-bit integer, the maximum number of digits is around 10 (since 2^31 - 1 is roughly 2 * 10^9). So, even for the largest possible x, the loop runs a very small, constant number of times. It's incredibly efficient!

Space Complexity: O(1)

We are only using a few extra variables (reversed_num, digit, etc.) whose memory usage does not change with the input size x. Therefore, the space complexity is constant.

🎯 Key Takeaways

Digit Manipulation Power Duo: Remember num % 10 to get the last digit and num / 10 to remove it. They are fundamental for many integer-based problems.
The Dreaded Overflow: Always be mindful of integer limits, especially in problems specifying fixed-size types (like 32-bit integers).
Proactive Overflow Checks: The golden rule is to check for potential overflow before performing the operation that might cause it. Don't wait for your program to crash!
Building Numbers: The pattern result = result * 10 + digit is a common and powerful technique for constructing numbers from their digits.
Edge Cases Matter: Think about negative numbers and numbers ending in zero (like 120 becoming 21). Our solution handles these gracefully!

This problem is a fantastic way to solidify your understanding of basic arithmetic operations and introduce you to the critical concept of overflow handling in programming. Keep practicing, and you'll be a LeetCode master in no time!

Author: Vansh2710

Published: 2026-04-24 00:33:03

LeetCode Solution: 7. Reverse Integer

Vansh Aggarwal — Thu, 23 Apr 2026 18:54:40 +0000

Reversing Integers: Tackling LeetCode Problem 7 with Confidence!

Hey there, future coding rockstars! 👋 Vansh here, ready to demystify another classic LeetCode problem that might seem simple on the surface but hides a clever trick: Problem 7: Reverse Integer.

Don't let the "easy" tag fool you; this problem is a fantastic way to sharpen your understanding of integer manipulation and, more importantly, handle those pesky edge cases like a pro! Let's dive in!

The Challenge: What's the Goal?

Imagine you have a number, say 123. Your mission, should you choose to accept it, is to reverse its digits to get 321. Sounds straightforward, right? But there's a catch (or two!):

Signed 32-bit integer: We're dealing with numbers that can be positive or negative, and they live within a specific computer memory limit: [-2^31, 2^31 - 1].
- Minimum: -2,147,483,648
- Maximum: 2,147,483,647
Overflow Protection: If reversing the number makes it too big (or too small) to fit within this 32-bit range, we must return 0. This is the sneaky part!
No 64-bit integers: We can't just convert to a larger data type to avoid overflow during intermediate steps. We have to be smart with our 32-bit integers throughout.

Let's look at a few examples:

Example 1: x = 123 -> Output: 321 (Simple positive)
Example 2: x = -123 -> Output: -321 (Simple negative, sign should be preserved)
Example 3: x = 120 -> Output: 21 (Trailing zeros disappear in the reversal)

See? It's not just flipping digits; it's about handling signs and staying within bounds!

The "Aha!" Moment: How Do We Even Reverse Digits?

Before we jump to the overflow puzzle, let's figure out how to reverse digits of an integer. Think about how you'd do it manually:

To get the last digit of a number, we can use the modulo operator (%) with 10.

123 % 10 gives 3
12 % 10 gives 2
1 % 10 gives 1

To remove the last digit from a number, we can use integer division (/) by 10.

123 / 10 gives 12
12 / 10 gives 1
1 / 10 gives 0

Now, how do we build the reversed number? We start with 0 and, for each digit we extract, we:

Multiply our current reversed_number by 10.
Add the new digit.

Let's trace x = 123:

Step	`x` (original)	`digit` (`x % 10`)	`reversedNum` (`reversedNum * 10 + digit`)
Start	`123`	-	`0`
1	`123`	`3`	`0 * 10 + 3 = 3`
2	`12`	`2`	`3 * 10 + 2 = 32`
3	`1`	`1`	`32 * 10 + 1 = 321`
End	`0`	-	`321`

This iterative process, using modulo and division within a while loop (which continues as long as x is not 0), is the core intuition!

The Smart Approach: Handling Overflow!

The simple digit-reversal logic works perfectly until we hit the 32-bit integer limits. The trick is to check for potential overflow before we perform the operation that might cause it.

Imagine reversedNum is currently 214748364. If the next digit is 7, 214748364 * 10 + 7 would be 2147483647, which is exactly INT_MAX (the maximum 32-bit integer). Perfect!

But what if the next digit was 8? 214748364 * 10 + 8 would be 2147483648, which is INT_MAX + 1! This is an overflow!

So, we need a check:

For Positive Overflow:
- If reversedNum is already greater than INT_MAX / 10, multiplying it by 10 will definitely overflow.
- If reversedNum is equal to INT_MAX / 10, we need to check the digit. If digit is greater than 7, it will cause an overflow. (Since INT_MAX ends in 7: 2,147,483,647).
For Negative Overflow:
- If reversedNum is already less than INT_MIN / 10, multiplying it by 10 will definitely overflow (become too negative).
- If reversedNum is equal to INT_MIN / 10, we need to check the digit. If digit is less than -8, it will cause an overflow. (Since INT_MIN ends in 8: -2,147,483,648).

These checks must happen before the line reversedNum = reversedNum * 10 + digit;. If an overflow is detected, we immediately return 0.

The Code (C++)

Let's put it all together into a clean, working solution. We'll use INT_MAX and INT_MIN constants available in <limits.h> for the maximum and minimum values of a 32-bit integer.

#include <limits.h> // Required for INT_MAX and INT_MIN

class Solution {
public:
    int reverse(int x) {
        int reversedNum = 0; // This will store our reversed number

        // Loop continues as long as there are digits left in x
        while (x != 0) {
            // Step 1: Extract the last digit of x
            // For positive x, x % 10 gives the last digit (e.g., 123 % 10 = 3)
            // For negative x, x % 10 gives the last digit (e.g., -123 % 10 = -3)
            int digit = x % 10;

            // Step 2: Critical Overflow Check BEFORE updating reversedNum
            // Check for potential positive overflow
            // If reversedNum is already too large (e.g., > INT_MAX / 10)
            // OR if reversedNum is exactly INT_MAX / 10 AND the next digit would push it over (digit > 7 for INT_MAX = ...7)
            if (reversedNum > INT_MAX / 10 || (reversedNum == INT_MAX / 10 && digit > 7)) {
                return 0; // Overflow detected, return 0 as per problem statement
            }

            // Check for potential negative overflow
            // If reversedNum is already too small (e.g., < INT_MIN / 10)
            // OR if reversedNum is exactly INT_MIN / 10 AND the next digit would push it over (digit < -8 for INT_MIN = ...8)
            if (reversedNum < INT_MIN / 10 || (reversedNum == INT_MIN / 10 && digit < -8)) {
                return 0; // Overflow detected, return 0
            }

            // Step 3: Build the reversed number
            // Multiply current reversedNum by 10 to shift digits left, then add the new digit
            reversedNum = reversedNum * 10 + digit;

            // Step 4: Remove the last digit from x
            // Integer division by 10 truncates the last digit
            x /= 10;
        }

        // Once x becomes 0, all digits have been processed, return the final reversed number
        return reversedNum;
    }
};

Time and Space Complexity Analysis

Time Complexity: O(log |x|)
- The number of iterations in our while loop is proportional to the number of digits in the input integer x.
- Since x is a 32-bit integer, it has at most 10 digits (e.g., 2,147,483,647).
- Each iteration involves a constant number of operations (modulo, division, multiplication, addition, comparisons).
- Therefore, the time complexity is logarithmic with respect to the absolute value of x.
Space Complexity: O(1)
- We are only using a few fixed-size integer variables (x, reversedNum, digit).
- The amount of memory used does not grow with the input size.

Key Takeaways

Digit Manipulation: The core pattern of num % 10 for getting the last digit and num / 10 for removing it is fundamental for many integer-based problems.
Overflow Awareness: This problem is a prime example of why you need to be mindful of integer limits. Don't assume numbers will always fit!
Pre-computation Checks: The crucial lesson here is to check for overflow before performing the operation that might cause it. This often involves checking against INT_MAX / 10 or INT_MIN / 10.
Edge Cases: Remember to consider 0, single-digit numbers, and the maximum/minimum possible integer values as test cases.

This problem is a fantastic stepping stone in your LeetCode journey. It teaches you practical skills for dealing with data types and their limitations. Keep practicing, and you'll be solving even tougher challenges in no time! Happy coding!

Authored by Vansh2710 | Published: 2026-04-24 00:24:13

DEV Community: Vansh Aggarwal

LeetCode Solution: 48. Rotate Image

Spin That Image! Rotating a 2D Matrix Like a Pro (LeetCode #48)

Understanding the Challenge: Rotate That Image!

The "Aha!" Moment: Two Simple Steps to Rotation

The Step-by-Step Approach

Step 1: Transposing the Matrix

Step 2: Reversing Each Row

The Code (C++)

Complexity Analysis

Key Takeaways

LeetCode Solution: 69. Sqrt(x)

✨ Unlocking Sqrt(x): Your First Dive into Binary Search! 🚀

🧐 Problem Explanation: What are we actually doing?

🤔 Intuition: How would you guess the square root?

🚀 Approach: Binary Search to the Rescue!

💻 Code (C++)

⏱️ Time & Space Complexity Analysis

🎯 Key Takeaways

LeetCode Solution: 69. Sqrt(x)

Unlocking the Power of Binary Search: Solving Sqrt(x) ⚡

🧐 Problem Explanation: What are we actually doing?

🤔 Intuition: The "Aha!" Moment

🚶‍♀️ Approach: Step-by-Step with Binary Search

💻 Code

⏱️ Time & Space Complexity Analysis

✨ Key Takeaways

LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

Finding Your Way: First and Last Occurrences in a Sorted Array (LeetCode 34 Explained!)

🔍 Problem Explanation: What are We Even Doing?

🤔 Intuition: The "Aha!" Moment

🪜 Approach: Step-by-Step Logic

1. find_occurrence(nums, target, find_first) Function Logic:

2. Main Function Logic:

💻 Code

⏱️ Time & Space Complexity Analysis

💡 Key Takeaways

LeetCode Solution: 74. Search a 2D Matrix

LeetCode 74: Search a 2D Matrix - Conquer the Grid with Binary Search!

Problem Explanation: What's the Challenge?

Intuition: The "Aha!" Moment 💡

Approach: From 2D to 1D (and Back!)

Code 🖥️

Time & Space Complexity Analysis

Key Takeaways

LeetCode Solution: 74. Search a 2D Matrix

Conquer the Sorted Labyrinth: Searching a 2D Matrix with Binary Search Magic! ✨

The Quest: Search a 2D Matrix

The "Aha!" Moment: Flattening the Matrix (Mentally!)

The Approach: Binary Search on a Virtual 1D Array

The Code

Complexity Analysis

Key Takeaways

LeetCode Solution: 283. Move Zeroes

Zeroes Got You Down? Let's Kick 'Em to the Curb! (LeetCode 283: Move Zeroes)

The Problem: Zeroes on the Loose!

The "Aha!" Moment: Focus on What Matters!

Our Strategy: The Two-Pointer Dance!

The Code

Complexity Analysis

Key Takeaways

LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

Uncover the Hidden Range: Finding First & Last Occurrences in Sorted Arrays (LeetCode #34)

Problem Explanation

Intuition: The "Aha!" Moment

Approach: Two-Pronged Binary Search

1. Finding the First Occurrence

2. Finding the Last Occurrence

Code

Time & Space Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

Key Takeaways

LeetCode Solution: 7. Reverse Integer

Cracking LeetCode 7: Reversing Integers Without Breaking the Bank (or the Integer Limit!) 🚀

Understanding the Challenge: Reverse Integer 🔄

The "Aha!" Moment: Intuition ✨

Step-by-Step Approach 🚶‍♂️

The Code 💻

Time & Space Complexity Analysis ⏱️📏

✨ Unlocking `Sqrt(x)`: Your First Dive into Binary Search! 🚀

1. `find_occurrence(nums, target, find_first)` Function Logic: