LeetCode Medium Problems: A Friendly Guide

Screenshot:-

LeetCode medium problems can be a bit more challenging, but they are great for honing your problem-solving skills. Today, we'll go through five medium-level LeetCode problems: Add Two Numbers, Longest Substring Without Repeating Characters, Container With Most Water, 3Sum, and Group Anagrams. We'll explain the approach for each problem and provide the solution in an easy-to-understand way. Let's get started!

Activity 1: Add Two Numbers

Problem: Given two non-empty linked lists representing two non-negative integers, where the digits are stored in reverse order, add the two numbers and return the sum as a linked list.

Approach:

1. Understanding the problem: We need to add two numbers represented by linked lists and return the sum as a linked list.

2. Plan: Use a dummy node to simplify the process. Traverse both linked lists, add corresponding digits, and handle carry-over.

Code:

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        int carry = 0;

        while (l1 != NULL || l2 != NULL || carry != 0) {
            int sum = carry;
            if (l1 != NULL) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                sum += l2->val;
                l2 = l2->next;
            }
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }
        return dummy.next;
    }
};

// Test cases
void printList(ListNode* node) {
    while (node != NULL) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    Solution sol;
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode* result = sol.addTwoNumbers(l1, l2);
    printList(result);  // Output: 7 0 8
    return 0;
}

Important Points:

• Use a dummy node to simplify the addition process.

• Handle carry-over by adding it to the next sum.

• Traverse both linked lists and add corresponding digits.

Activity 2: Longest Substring Without Repeating Characters

Problem: Given a string, return the length of the longest substring without repeating characters.

Approach:

1. Understanding the problem: We need to find the length of the longest substring without repeating characters.

2. Plan: Use a sliding window approach with two pointers and a hash set to track characters in the current window.

Code:

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.size(); right++) {
            while (charSet.find(s[right]) != charSet.end()) {
                charSet.erase(s[left]);
                left++;
            }
            charSet.insert(s[right]);
            maxLength = max(maxLength, right - left + 1);
        }
        return maxLength;
    }
};

// Test cases
int main() {
    Solution sol;
    string str = "abcabcbb";
    cout << "Length: " << sol.lengthOfLongestSubstring(str) << endl;  // Output: 3
    return 0;
}

Important Points:

• Use a sliding window approach to maintain the longest substring without repeating characters.

• Use a hash set to track characters in the current window.

• Adjust the window size by moving the left pointer when a duplicate character is found.

Activity 3: Container With Most Water

Problem: Given an array of non-negative integers representing the height of lines, find two lines that together with the x-axis form a container that holds the most water.

Approach:

1. Understanding the problem: We need to find the maximum area of water that can be contained.

2. Plan: Use two pointers, one at the beginning and one at the end of the array, and calculate the area while moving the pointers towards each other.

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
};

// Test cases
int main() {
    Solution sol;
    vector<int> height = {1,8,6,2,5,4,8,3,7};
    cout << "Max Area: " << sol.maxArea(height) << endl;  // Output: 49
    return 0;
}

Important Points:

• Use two pointers to calculate the area and move them towards each other.

• Calculate the area using the shorter height between the two pointers.

• Update the maximum area as you find larger areas.

Activity 4: 3Sum

Problem: Given an array of integers, find all unique triplets that sum to zero.

Approach:

1. Understanding the problem: We need to find unique triplets in the array that sum to zero.

2. Plan: Sort the array and use a three-pointer approach to find the triplets. Avoid duplicates by skipping repeated elements.

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;  // Skip duplicates
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;  // Skip duplicates
                    while (left < right && nums[right] == nums[right - 1]) right--;  // Skip duplicates
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};

// Test cases
int main() {
    Solution sol;
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> result = sol.threeSum(nums);

    for (const auto& triplet : result) {
        cout << "[";
        for (int num : triplet) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }
    // Output: [-1 -1 2], [-1 0 1]
    return 0;
}

Important Points:

• Sort the array to simplify finding triplets.

• Use a three-pointer approach to find triplets that sum to zero.

• Avoid duplicates by skipping repeated elements.

Activity 5: Group Anagrams

Problem: Given an array of strings, group anagrams together.

Approach:

1. Understanding the problem: We need to group strings that are anagrams of each other.

2. Plan: Use a hash map to group strings by their sorted version.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagramMap;
        for (const string& str : strs) {
            string sortedStr = str;
            sort(sortedStr.begin(), sortedStr.end());
            anagramMap[sortedStr].push_back(str);
        }

        vector<vector<string>> result;
        for (const auto& pair : anagramMap) {
            result.push_back(pair.second);
        }
        return result;
    }
};

// Test cases
int main() {
    Solution sol;
    vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = sol.groupAnagrams(strs);

    for (const auto& group : result) {
        cout << "[";
        for (const string& str : group) {
            cout << str << " ";
        }
        cout << "]" << endl;
    }
    // Output: [eat tea ate], [tan nat], [bat]
    return 0;
}

Important Points:

• Use a hash map to group strings by their sorted version.

• Sort each string and use it as a key in the hash map.

• Collect the grouped anagrams from the hash map.

Conclusion

By solving these medium-level LeetCode problems, we've practiced advanced problem-solving skills and learned how to handle edge cases in more complex algorithms. Each problem required a different approach, from linked lists to hash maps, and applying these techniques will improve your coding abilities.

Feel free to try out the provided code snippets and test them with your own cases. Happy coding!

---

I hope this friendly guide helps you understand how to solve these LeetCode problems. If you have any questions or need further clarification, feel free to ask!