DEV Community: AussieCoder

LeetCode Solution: 8. String to Integer (atoi)

AussieCoder — Mon, 18 May 2026 01:03:00 +0000

Cracking `atoi`: How to Convert Strings to Integers with LeetCode 8

Hey everyone! 👋 Aaradhya here, diving into another exciting LeetCode challenge. Today, we're tackling problem 8: "String to Integer (atoi)". This one sounds simple – just convert a string to a number, right? Well, as we'll see, atoi is famous for its sneaky edge cases and makes for a fantastic exercise in robust parsing!

🧐 Problem Explanation: The `atoi` Gauntlet

Imagine you're building a calculator app, and users input numbers as text (like "123" or "-42"). Your job is to take that string and turn it into an actual integer your program can use for calculations. That's exactly what myAtoi(string s) asks us to do!

But it's not just a straightforward conversion. LeetCode throws in a few crucial rules that make this problem interesting:

Whitespace Whisperer: First things first, ignore any leading spaces. Think of it like trimming a string before you start reading the juicy bits.
- Example: " -42" should become "-42" after ignoring spaces.
Sign Detective: After the spaces, look for a '-' or '+'. This determines if your number is negative or positive. If neither is present, assume it's a positive number.
- Example: " -042" the '-' tells us it's negative. "42" is positive by default.
Digit Dynamo: Now, start reading digits (0-9) one by one. Keep going until you hit a character that isn't a digit, or you reach the end of the string.
- Important: If you don't find any digits after handling whitespace and sign, the result is 0.
- Example: "1337c0d3" becomes 1337 because c isn't a digit. "words and 987" becomes 0 because w isn't a digit.
Range Ranger (Clamping): The final integer must fit within the 32-bit signed integer range, which is [-2^31, 2^31 - 1].
- INT_MAX is 2147483647.
- INT_MIN is -2147483648.
- If your number is too small (e.g., -99999999999), it gets "rounded" (clamped) to INT_MIN.
- If your number is too big (e.g., 99999999999), it gets clamped to INT_MAX.

Let's quickly look at an example to tie it all together:

Input: s = " -042"

Step 1 (Whitespace): " -042" -> We ignore the three leading spaces. Our reading starts at '-'.
Step 2 (Signedness): "-042" -> We see '-', so our number will be negative.
Step 3 (Conversion): "-042" -> We read 0, then 4, then 2. The 0 is a leading zero, so it doesn't change the value 42. We stop after 2 as the string ends.
Step 4 (Rounding): The number is -42. This is well within INT_MIN and INT_MAX.
Output: -42

See? There are quite a few rules to follow meticulously!

💡 Intuition: It's a State Machine!

My "aha!" moment for atoi usually comes when I realize it's not just one big transformation, but a sequence of small, specific steps. It's like a little state machine:

State 1: Looking for non-whitespace.
State 2: Looking for a sign (+ or -).
State 3: Accumulating digits.
State 4: Done, apply final checks.

The key insight is that we need to process the string character by character, making decisions and updating our current state (like the sign and the number we've built so far). And the most crucial "gotcha" to watch out for is integer overflow! Since result * 10 can quickly exceed INT_MAX, we need a way to detect and handle this before it actually overflows our int variable.

🚀 Approach: A Step-by-Step Breakdown

Let's break down how we can implement myAtoi in a robust, step-by-step manner. We'll use an iterative approach, which is generally cleaner for managing the sequential steps and overflow checks in this problem.

Step 0: Essential Tools and Constants

We'll need INT_MAX (2,147,483,647) and INT_MIN (-2,147,483,648) from the <climits> header to perform our range checks. We'll also use long long for our intermediate number to prevent overflow before we clamp it to int limits.

Step 1: Skip Leading Whitespace

We'll use an index i to iterate through the string. The first thing we do is advance i past any ' ' characters.

int i = 0;
while (i < s.length() && s[i] == ' ') {
    i++; // Move past the space
}

Step 2: Determine the Sign

After skipping spaces, the next non-space character (if any) could be a sign (+ or -).

Initialize sign = 1 (defaulting to positive).
If we find '-', set sign = -1.
If we find '+', sign remains 1.
In either case, increment i to move past the sign character.

int sign = 1; // Assume positive initially
if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
    sign = (s[i] == '-') ? -1 : 1; // If it's '-', sign is -1, else 1
    i++; // Move past the sign character
}

Step 3: Convert Digits and Handle Overflow (The Heart of the Problem)

This is where we build our number and constantly check if it's getting too big or too small.

We'll use a long long variable, let's call it result, initialized to 0. This is crucial because the number might temporarily exceed INT_MAX before we clamp it.
We'll loop while i is within bounds and s[i] is a digit.
Inside the loop:
1. Extract the digit: int digit = s[i] - '0'; (e.g., '5' - '0' gives 5).
2. Update result: result = result * 10 + digit; (This is how you build a number from digits).
3. Perform Overflow Checks! This is the most critical part. We need to check at each step if result (even though it's long long) indicates that the final clamped int would go out of range.
  - For Positive Numbers: If sign is 1 and our result (which is always positive here) has already surpassed INT_MAX, we know the final answer must be INT_MAX. We can return INT_MAX immediately.
  - For Negative Numbers: If sign is -1 and our result (its absolute value) has surpassed the magnitude of INT_MIN (2147483648), we know the final answer must be INT_MIN. Remember INT_MIN's absolute value is INT_MAX + 1. So, if result > (long long)INT_MAX + 1, we return INT_MIN.
4. Increment i to move to the next character.

long long result = 0; // Use long long to handle potentially large intermediate values

while (i < s.length() && isdigit(s[i])) { // Loop while we have digits
    int digit = s[i] - '0'; // Convert character digit to integer

    result = result * 10 + digit; // Build the number

    // Overflow check for positive numbers
    if (sign == 1 && result > INT_MAX) {
        return INT_MAX;
    }
    // Overflow check for negative numbers
    // Note: INT_MIN is -2147483648, while INT_MAX is 2147483647.
    // So, for negative numbers, the absolute value can be one larger than INT_MAX.
    if (sign == -1 && result > (long long)INT_MAX + 1) { 
        return INT_MIN;
    }

    i++; // Move to the next digit
}

Step 4: Apply Sign and Return

Finally, once we're done parsing all digits (or ran into a non-digit), we apply the determined sign to our result and cast it back to an int. Since we handled all overflows during step 3, this final cast will safely return the correct, clamped 32-bit integer.

return (int)(sign * result);

Combining all these steps gives us a complete and robust atoi function!

💻 Code: My `atoi` Implementation

#include <string>   // For std::string
#include <climits>  // For INT_MAX, INT_MIN
#include <cctype>   // For isdigit (good practice to include explicitly)

class Solution {
public:
    int myAtoi(std::string s) {
        int i = 0;

        // Step 1: Skip leading whitespace
        while (i < s.length() && s[i] == ' ') {
            i++;
        }

        // Step 2: Determine sign
        int sign = 1; // Assume positive initially
        if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i] == '-') ? -1 : 1; // If it's '-', sign is -1, else 1
            i++; // Move past the sign character
        }

        // Step 3: Convert digits and handle overflow
        long long result = 0; // Use long long to handle potentially large intermediate values

        // Loop while we have characters and they are digits
        while (i < s.length() && std::isdigit(s[i])) { 
            int digit = s[i] - '0'; // Convert character digit to integer

            result = result * 10 + digit; // Build the number

            // Critical Overflow Checks!
            // If the number is positive and exceeds INT_MAX
            if (sign == 1 && result > INT_MAX) {
                return INT_MAX;
            }
            // If the number is negative and its absolute value exceeds the magnitude of INT_MIN
            // The magnitude of INT_MIN (-2147483648) is 2147483648, which is INT_MAX + 1.
            if (sign == -1 && result > (long long)INT_MAX + 1) { 
                return INT_MIN;
            }

            i++; // Move to the next digit
        }

        // Step 4: Apply sign and return the final integer
        return (int)(sign * result);
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(N)
- We iterate through the input string s at most once. Each character is processed a constant number of times (whitespace skip, sign check, digit conversion). N is the length of the string.
Space Complexity: O(1)
- We only use a few constant-size variables (i, sign, result, digit). No additional data structures are created that depend on the input size.

✨ Key Takeaways

Solving atoi is more than just converting a string to a number; it's a masterclass in:

Careful Parsing: Breaking down a complex problem into sequential, manageable steps.
Edge Case Handling: Systematically addressing scenarios like leading spaces, signs, non-digit characters, and empty inputs.
Overflow Prevention: Understanding integer limits (INT_MAX, INT_MIN) and using a long long for intermediate calculations to proactively prevent data type overflows, followed by precise clamping.
Clarity: An iterative approach often makes the "state changes" and decision points clearer for problems like atoi.

This problem is a fantastic way to sharpen your attention to detail and write robust code. Keep practicing, and you'll be parsing strings like a pro in no time! Happy coding!

Author Account: aaradhyanegi009
Publishing Time: 2026-05-18 06:32:19

LeetCode Solution: 7. Reverse Integer

AussieCoder — Mon, 18 May 2026 01:00:35 +0000

Cracking LeetCode 7: How to Reverse an Integer Safely (and Why It's Tricky!)

Hey awesome developers! 👋 Welcome back to another exciting LeetCode breakdown with aaradhyanegi009. Today, we're diving into a classic problem that seems simple on the surface but hides a crucial twist: Reversing an Integer. It's a fantastic exercise for understanding integer manipulation and, more importantly, how to deal with the dreaded "integer overflow."

Let's get started!

🚀 Problem Explanation: Reverse Integer (LeetCode #7)

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

Here's the catch:

Signed 32-bit integer range: This means x can be anywhere from -2,147,483,648 to 2,147,483,647.
Overflow Check: If the reversed version of x goes outside this 32-bit signed integer range, you must return 0.
No 64-bit integers (for final result): You're assumed not to be able to store 64-bit integers. This implies that your final return value should fit within a 32-bit integer, and you need clever ways to detect overflow without relying on a larger type for the final result.

Let's look at some examples:

Example 1: x = 123
- Output: 321 (Simple reversal)
Example 2: x = -123
- Output: -321 (Negative sign needs to be preserved)
Example 3: x = 120
- Output: 21 (Trailing zeros become leading zeros and disappear)

💡 Intuition: The "Aha!" Moment

When you think about reversing digits, two main strategies often come to mind:

Mathematical Approach: Repeatedly extract the last digit (x % 10), build the reversed number (reversed = reversed * 10 + digit), and truncate x (x /= 10). This is efficient but makes overflow checking a bit more intricate, as you need to check before each multiplication.
String Conversion Approach: Convert the number to a string, reverse the string, and then convert it back to a number. This often feels more intuitive for reversing sequences and can simplify overflow detection, as you perform the reversal first and then check the final value.

For this problem, especially given the "no 64-bit integers" constraint (which is often interpreted as "don't return a 64-bit integer, but you might use it temporarily for safety checks"), the string conversion approach combined with careful type handling provides a very robust and readable solution.

The "aha!" here is realizing that a long long (which is typically 64-bit) can be your best friend for intermediate calculations and overflow checks, even if your final answer must fit in an int (32-bit). You build the potentially overflowing number in a long long, then compare it against the INT_MAX and INT_MIN boundaries before casting it back to an int. This way, you catch overflows safely.

📋 Approach: Step-by-Step Logic

Our chosen approach leverages string manipulation for the reversal and long long for safe overflow detection.

Preserve the Sign and Get Absolute Value:
- First, we need to know if the original x was negative. We'll store its sign and work with its absolute value. This simplifies the reversal process, as we don't have to worry about the negative sign until the very end.
- We store x in a long long variable (val) right away to prevent any potential overflow issues if x itself is INT_MIN (which behaves strangely with abs() in some contexts).
Convert to String:
- Convert the absolute value of val into a string. This allows us to easily manipulate its digits. For x = 123, num becomes "123". For x = -123, num becomes "123".
Reverse the String:
- Use a standard library function (like std::reverse in C++) to reverse the num string. "123" becomes "321", and "12" becomes "21".
Convert Back to Number (Safely!):
- Convert the reversed string back into a numerical type. Here's where long long shines! We convert it into a long long (res) using stoll() (string to long long). This lets res temporarily hold values larger than INT_MAX or smaller than INT_MIN without crashing, so we can then check them.
Reapply the Original Sign:
- If the original x was negative (checked by x < 0), multiply our res by -1 to restore its negative sign.
Perform Overflow Check:
- Now that we have the final res as a long long, we compare it against the INT_MAX (2,147,483,647) and INT_MIN (-2,147,483,648) limits.
- If res is greater than INT_MAX or less than INT_MIN, it means the reversed integer overflows a 32-bit signed integer. In this case, as per the problem, we return 0.
Return the Result:
- If no overflow occurred, we know res perfectly fits into a 32-bit integer. We cast res to an int and return it.

This approach gracefully handles negative numbers, trailing zeros, and the all-important overflow condition, while respecting the underlying 32-bit integer limits for the final result.

💻 Code

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

#include <string>    // Required for std::string, to_string, stoll
#include <algorithm> // Required for std::reverse
#include <limits>    // Required for INT_MAX, INT_MIN (or just use <climits>)

class Solution {
public:
    int reverse(int x) {
        // Use INT_MAX and INT_MIN from <limits> for clarity
        // Or directly use numeric_limits<int>::max() / min()
        int max_V = std::numeric_limits<int>::max();
        int min_V = std::numeric_limits<int>::min();

        // Use long long to safely store x initially. 
        // This is crucial for handling INT_MIN correctly with abs() if used directly.
        long long val = x; 

        // 1. Convert absolute value of the number to a string
        // abs() ensures we work with positive digits first
        std::string num = std::to_string(std::abs(val)); 

        // 2. Reverse the string
        std::reverse(num.begin(), num.end());

        // 3. Convert the reversed string back to a long long.
        // This allows us to temporarily hold a value that might exceed int limits
        // before we perform the overflow check.
        long long res = std::stoll(num);

        // 4. Reapply the original sign
        if (x < 0) {
            res *= -1;
        }

        // 5. Check for 32-bit integer overflow/underflow
        if (res > max_V || res < min_V) {
            return 0; // Return 0 if the reversed integer is out of range
        }

        // 6. If no overflow, cast the long long result back to int and return
        return static_cast<int>(res);
    }
};

⏱️ Time & Space Complexity Analysis

Let's break down the efficiency of this solution:

Time Complexity: `O(log10(x))` or `O(1)`

std::to_string(std::abs(val)): The time taken to convert an integer to a string is proportional to the number of digits in the integer. If D is the number of digits in x, this is O(D).
std::reverse(num.begin(), num.end()): Reversing a string of length D takes O(D) time.
std::stoll(num): Converting a string back to a long long also takes time proportional to the number of digits, O(D).

For a 32-bit integer, the maximum number of digits is 10 (e.g., 2,147,483,647). Since D is effectively a constant for fixed-size integers, the operations are constant time relative to the number of digits. Therefore, the overall time complexity is often considered O(1) for practical purposes in competitive programming context where the input integer's size is fixed (32-bit). If we consider x to be arbitrarily large, it would be O(log10(x)).

Space Complexity: `O(log10(x))` or `O(1)`

std::string num: We create a string to store the digits of x. The length of this string is D, the number of digits in x.

Similar to time complexity, for a 32-bit integer, D is at most 10, making the space usage effectively constant. Thus, the space complexity is often considered O(1). If x were arbitrarily large, it would be O(log10(x)).

✨ Key Takeaways

String Power: Don't underestimate the power of string conversions for digit-based problems. They can simplify complex logic like reversal and often offer good readability.
Overflow is King: In integer problems, handling overflow is paramount. Always consider the data type limits (INT_MAX, INT_MIN) and how your operations might exceed them.
Temporary long long (or Wider Types): Even if the problem constraints state that the final result must fit into a smaller type (like int), you can often use a wider type (long long) for intermediate calculations or for checking potential overflow before clamping the final result. This is a common and safe pattern.
Edge Cases: Always test with edge cases like negative numbers (-123), numbers ending in zero (120), and boundary values (INT_MAX, INT_MIN, or their reversed versions if they exist).

This problem serves as an excellent reminder that even seemingly simple tasks can have hidden complexities, pushing us to write more robust and error-resistant code. Keep coding, keep learning!

Authored by aaradhyanegi009 | Published on 2026-05-18 06:29:57

LeetCode Solution: 146. LRU Cache

AussieCoder — Sun, 17 May 2026 19:19:15 +0000

LRU Cache: Because Your Computer Has Commitment Issues (LeetCode 146)

Hello, fellow coders and aspiring digital hoarders! Today, we're diving into a LeetCode classic that’s as common in interviews as "tell me about yourself" – the LRU Cache. If you've ever wondered how your web browser remembers your favorite sites, or why some app data seems to magically stay while older stuff vanishes, you're about to find out!

The Problem: Your Computer's Short-Term Memory

Imagine you have a super-important, but very small, desk. You can only fit a capacity number of items on it. When you put a new item on the desk:

If the item is already there, you just update its content and put it on top (making it shiny and new).
If it's new, you add it to the desk.
Crucially: If adding this new item means your desk is now overflowing, you must throw away the item you haven't touched in the longest time. We call this the "Least Recently Used" (LRU) item. Out with the old, in with the slightly less old, maybe!

When you get an item from the desk:

If it's there, great! You pick it up, use it, and then put it back on top of the desk (making it the most recently used).
If it's not there, well, that's just awkward. You return -1.

The catch? Both get and put operations must be ridiculously fast, specifically O(1) on average. Because nobody has time for slow memory.

Intuition: The "Aha!" Moment 💡

At first glance, this problem might seem like a digital version of "Simon Says" with extra steps. You need to:

Find things fast: If you have key 10, you need to grab its value immediately. A plain list would mean searching through everything, which is O(N) – no good for our O(1) requirement. This screams Hash Map! A map (or unordered_map in C++) lets us look up a key and get its value in average O(1) time.
Maintain order and recency: How do we know what's LRU or MRU? A simple array won't work, because moving items around in an array (to make something MRU) is also O(N). We need something where we can easily remove an item from the middle and add it to the end (or beginning) in O(1) time. This, my friends, is the job for a Doubly Linked List! With prev and next pointers, a node can be unlinked and relinked with constant pointer manipulations.

So, the "aha!" moment is realizing we need both of them. The Hash Map gives us O(1) access to any item by its key, and crucially, it will store a pointer to that item's location in our Doubly Linked List. The Doubly Linked List then maintains the usage order, making it trivial to identify the LRU item (the one at the tail) and move an item to the MRU position (the head).

Approach: The Dynamic Duo Strikes Back!

Our strategy is simple yet elegant, like a perfectly optimized pantry:

The Dynamic Duo:
- We'll use a std::unordered_map<int, ListNode*> (let's call it cacheMap) to map each key to its corresponding ListNode in our linked list. This gives us lightning-fast lookups (key -> node).
- We'll use a Doubly Linked List to keep track of the access order. The head of our list will always point to the Most Recently Used (MRU) item, and the tail will point to the Least Recently Used (LRU) item. To simplify things, we'll use "dummy" head and tail nodes that don't store actual data. They just act as bookends, making insertions and deletions much cleaner.
The ListNode Structure:
Each node in our doubly linked list will be a struct ListNode containing:
- key: The actual key stored.
- value: The value associated with the key.
- prev: A pointer to the previous node.
- next: A pointer to the next node.
Core Operations (deleteNode, insertNode):
These are our utility belt items, doing the heavy lifting in O(1):
- deleteNode(node): Takes a node and removes it from its current position in the linked list by updating its neighbors' prev and next pointers. Poof, gone!
- insertNode(node): Takes a node and inserts it right after our dummy head node. This effectively makes it the new MRU item. "Welcome to the front row!"
LRUCache(int capacity):
- Initialize our cacheMap.
- Create our dummy head and tail nodes.
- Link head->next = tail and tail->prev = head. An empty list, ready for action!
int get(int key):
- "Is this key even VIP enough to be in our exclusive club?" Check cacheMap.
- If key isn't found (cacheMap.find(key) == cacheMap.end()), return -1. "Nope, not found. Try harder next time!"
- If found:
  - Retrieve the ListNode* using cacheMap[key].
  - "Found it! Now it's super popular, so move it to the front." Call deleteNode() on it to remove it from its old spot.
  - Call insertNode() on it to place it right after the head.
  - Return the node->value.
void put(int key, int value):
- "Does this key already have a reservation?" Check cacheMap.
- If key is found:
  - Retrieve the ListNode* from cacheMap.
  - Update its value.
  - "Ah, you're back! Let's update your info and put you at the top." deleteNode() and insertNode() to refresh its MRU status.
- If key is not found:
  - "New face! Welcome to the party. Let's add you." Create a new ListNode(key, value).
  - Add it to cacheMap: cacheMap[key] = newNode;.
  - insertNode(newNode) to make it MRU.
  - "Party's getting a bit crowded, isn't it?" Check if (cacheMap.size() > capacity):
    - "Time for some tough decisions. Who's the least social butterfly?" The LRU node is always tail->prev.
    - "Sorry, old friend, your time has come."
    - deleteNode(tail->prev) to remove it from the list.
    - cacheMap.erase(tail->prev->key) to remove it from the map.
    - delete tail->prev; to free up that memory (we're not running a charity!).

Code: The Grand Symphony of Pointers and Maps

#include <unordered_map> // For O(1) average time complexity lookup

// A simple structure for our doubly linked list nodes
struct ListNode {
    int key;
    int value; // Storing the value associated with the key
    ListNode *prev;
    ListNode *next;

    // Constructor: key, value, optional prev/next for convenience
    ListNode(int k, int v, ListNode* p = nullptr, ListNode* n = nullptr) 
        : key(k), value(v), prev(p), next(n) {}
};

class LRUCache {
private:
    std::unordered_map<int, ListNode*> cacheMap; // Maps key to its node in the list
    int capacity; // Maximum number of items the cache can hold
    ListNode *head; // Dummy head node for the doubly linked list
    ListNode *tail; // Dummy tail node for the doubly linked list

    // Helper to remove a node from its current position in the list
    void deleteNode(ListNode* node) {
        // "Hasta la vista, baby!" - The node bids adieu to its neighbors.
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // Helper to insert a node right after the head (making it the Most Recently Used)
    void insertNode(ListNode* node) {
        // "Making a grand entrance!" - The node proudly claims its spot at the front.
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int cap) {
        capacity = cap;
        // Initialize dummy head and tail nodes. Their key/value don't matter.
        // They simplify logic by always having valid 'prev'/'next' for real nodes.
        head = new ListNode(0, 0); 
        tail = new ListNode(0, 0);

        // Link the dummy nodes to each other initially
        head->next = tail;
        tail->prev = head;
    }

    // Destructor to prevent memory leaks, a good practice for C++
    // We allocated nodes with 'new', so we must 'delete' them.
    ~LRUCache() {
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* next = current->next;
            delete current;
            current = next;
        }
    }

    int get(int key) {
        // "Is this key even VIP enough to be in our exclusive club?"
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1; // "Nope, not found. Try harder next time!"
        }

        // Found it! Now it's the coolest kid on the block, move it to the front.
        ListNode* node = cacheMap[key];
        deleteNode(node);
        insertNode(node);
        return node->value; // Return the value, as requested.
    }

    void put(int key, int value) {
        // "Does this key already have a reservation?"
        if (cacheMap.find(key) != cacheMap.end()) {
            // "Ah, you're back! Let's update your info and put you at the top."
            ListNode* node = cacheMap[key];
            node->value = value; // Update the value
            deleteNode(node);
            insertNode(node);
        } else {
            // "New face! Welcome to the party. Let's add you."
            ListNode* newNode = new ListNode(key, value);
            cacheMap[key] = newNode;
            insertNode(newNode);

            // "Party's getting a bit crowded, isn't it?"
            if (cacheMap.size() > capacity) {
                // "Time for some tough decisions. Who's the least social butterfly?"
                // The LRU node is always the one just before the dummy tail.
                ListNode* lruNode = tail->prev;

                // "Sorry, old friend, your time has come." Evict!
                deleteNode(lruNode); // Remove from linked list
                cacheMap.erase(lruNode->key); // Remove from map
                delete lruNode; // And finally, free up that memory!
            }
        }
    }
};

Time & Space Complexity Analysis

"Alright, enough fun, let's talk numbers!"

Time Complexity:
- LRUCache(capacity): O(1). Just initializing a few pointers and our map. No heavy lifting.
- get(key): O(1) on average.
  - Hash map lookup (cacheMap.find or []) is O(1) on average.
  - Our deleteNode and insertNode helpers are pure pointer manipulation, always O(1).
- put(key, value): O(1) on average.
  - Hash map operations (lookup, insert, erase) are O(1) on average.
  - deleteNode and insertNode are O(1).
  - Checking capacity and evicting is also constant time.
Space Complexity:
- O(capacity).
  - Our cacheMap stores up to capacity key -> ListNode* pairs.
  - Our doubly linked list stores up to capacity ListNode objects (plus the two dummy nodes).
- Each ListNode uses constant space for key, value, prev, next.

"So, yes, we achieved that blazing-fast O(1) average time!"

Key Takeaways: The Secrets of the Cache Masters

The Power Couple: When you need fast lookups and ordered removals/insertions, a Hash Map combined with a Doubly Linked List is your go-to pattern. It's like the Batman and Robin of data structures!
Dummy Nodes are MVPs: Those head and tail sentinels might seem unnecessary, but they elegantly handle edge cases (empty list, single item) by ensuring prev and next pointers are always valid, saving you from null-pointer checks and messy conditional logic.
C++ and Memory: Don't forget that if you new something, you eventually need to delete it. Our destructor ~LRUCache() ensures we're not being a memory hoarder. In languages with garbage collection (like Java or Python), this isn't a manual step, but it's crucial for C++.
Thinking beyond simple arrays: Many "move to front" or "remove least X" problems often hint at linked lists or other dynamic structures.

I hope this deep dive into the LRU Cache was as enlightening as it was entertaining! May your caches be ever efficient and your evictions swift. Happy coding!

Submission Details:
Author Account: aaradhyanegi009
Time Published: 2026-05-18 00:48:35

DEV Community: AussieCoder

LeetCode Solution: 8. String to Integer (atoi)

Cracking atoi: How to Convert Strings to Integers with LeetCode 8

🧐 Problem Explanation: The atoi Gauntlet

💡 Intuition: It's a State Machine!

🚀 Approach: A Step-by-Step Breakdown

Step 0: Essential Tools and Constants

Step 1: Skip Leading Whitespace

Step 2: Determine the Sign

Step 3: Convert Digits and Handle Overflow (The Heart of the Problem)

Step 4: Apply Sign and Return

💻 Code: My atoi Implementation

⏱️ Time & Space Complexity Analysis

✨ Key Takeaways

LeetCode Solution: 7. Reverse Integer

Cracking LeetCode 7: How to Reverse an Integer Safely (and Why It's Tricky!)

🚀 Problem Explanation: Reverse Integer (LeetCode #7)

💡 Intuition: The "Aha!" Moment

📋 Approach: Step-by-Step Logic

💻 Code

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log10(x)) or O(1)

Space Complexity: O(log10(x)) or O(1)

✨ Key Takeaways

LeetCode Solution: 146. LRU Cache

LRU Cache: Because Your Computer Has Commitment Issues (LeetCode 146)

The Problem: Your Computer's Short-Term Memory

Intuition: The "Aha!" Moment 💡

Approach: The Dynamic Duo Strikes Back!

Code: The Grand Symphony of Pointers and Maps

Time & Space Complexity Analysis

Key Takeaways: The Secrets of the Cache Masters

Cracking `atoi`: How to Convert Strings to Integers with LeetCode 8

🧐 Problem Explanation: The `atoi` Gauntlet

💻 Code: My `atoi` Implementation

Time Complexity: `O(log10(x))` or `O(1)`

Space Complexity: `O(log10(x))` or `O(1)`