Introduction

Neetcode 150 is a popular collection of Leetcode problems designed to help programmers prepare for coding interviews. However, the tutorial videos may not always provide the most comprehensive explanations for full understanding. Therefore, I’ve decided to document my thought process while solving these problems, in the hope that it might help some of my readers.

Note: This post won't cover all the questions from Neetcode 150. Instead, I'll focus on the ones I found particularly tricky / challenging. I trust in your ability to know the basic logic behind each topic.

Sliding window

  • Key factor:
    1. The use of unordered_map / array to store appearance or index of the chars;
    2. Use l and r
      • l stays, indicating the start of the valid string[only change when certain condition met]
      • r keep moving
    3. Compare arrays for finding permuation or same string but different order.

424.Longest Repeating Character Replacement

  • The key for Longest Repeating is to count the appearance of each letter in current window
  • That leads us to know the maxCurrent in the window
  • To make sure the window is valid, the entire current length is not over k (current length - maxCurrent <= k). If not, move i → decrement vector[i] by 1

Two ways to do:

  1. vector count to keep track of numbers appearance in current window, we know the string only contains uppercase, vector<int> 26 fit

    • Find the max appearance in the current window, to do so, have a function check through the vector to find the maxCurrent everytime
    • To make sure the window is valid, the replacement is not over k (current length - maxCurrent <= k). If not, move i, decrement vector[i] by 1
    • Update Longest

  2. Have maxf only update when a greater num appears.

    • Replace if statement by (j - i + 1 - maxf > k)
    • There is a risk when maxf contains outdated chars because it doesn’t decrease according to i
    • However, it doesn’t hurt for not updating because we are finding the max appearces, the chars that couldn’t exceed the maxf will not be updated in longest anyway.
Hint 1: Create variables
int characterReplacement(string s, int k) {
    vector<int> m (26, 0); // Store the appearance of chars in current string.
    int i = 0; // Begin of the current string, cornorstone of Sliding Window.
    int longest = 0; // The final answer

    int maxf = 0; // Max frequent
}
Hint 2: Update vector and maxf in loop
// Remeber so far we only move j, not i !
for(int j = 0; j < s.length(); ++j){
    m[s[j] - 'A']++; // Find index or 26 letters and increase
    maxf = max(maxf, m[s[j] - 'A']); // Check max
}
Hint 3: Move i
    for(int j = 0; j < s.length(); ++j){
        //...Skip
        // If we remove max appearanc from currentLength and still find more than k non-max chars, shorten the i
        while(i < s.length() && j - i + 1 - maxf > k){
            m[s[i] - 'A']--; // Update current length frequency
            i++;
        }

        longest = max(j - i + 1, longest);
    }
Full Code
int characterReplacement(string s, int k) {
    vector<int> m (26, 0);
    int i = 0;
    int longest = 0;

    int maxf = 0;

    for(int j = 0; j < s.length(); ++j){
        m[s[j] - 'A']++;
        maxf = max(maxf, m[s[j] - 'A']);

        while(i < s.length() && j - i + 1 - maxf > k){
            m[s[i] - 'A']--;
            i++;
        }

        longest = max(j - i + 1, longest);
    }

    return longest;

}

425. Minimum Window Substring

  • Mininum Window: Have two maps check currentWindow size, same thing as sliding window.
  • The key is to
    1. Have a “form” to check if the window is valid (form == 0), once valid, start moving it until the form != 0.
    2. Have an arr[2] = {length, starting} to update the answer.

Step:

  1. Create two maps (dict, currentWindow), store target string into dict
  2. Create arr for answer, “form” and i
  3. Increment in currentWindow, if (dict also contain the letter and two numbers are the same), decrease “form”;
  4. While form == 0, update arr and remove s[i] from currentWindow. Same as step 3
    • if dict has it and dict[i] > currentWindow[i], increase the form. (Means the letter in currentWindow is less than / not in requirement)
    • Return arr, or “”
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> dict;
        unordered_map<char, int> currentWindow;

        for(const char& c : t){
            dict[c]++;
        }

        int i = 0;
        int form = dict.size();
        int arr [] = {-1, 0};

        for(int j = 0; j < s.length(); ++j){
            currentWindow[s[j]]++;
            if(dict.count(s[j]) && dict[s[j]] == currentWindow[s[j]]){
                form--;
            }

            while(i <= j && form == 0){
                if(arr[0] == -1 || j - i + 1 < arr[0]){
                    arr[0] = j - i + 1;
                    arr[1] = i;
                }
                currentWindow[s[i]]--;
                if(dict.count(s[i]) && dict[s[i]] > currentWindow[s[i]]){
                    ++form;
                }

                ++i;
            }
        }

        return arr[0] == -1? "" : s.substr(arr[1], arr[0]);
    }
};

426. Sliding Window Maximum

  • The key for Sliding Window Maximum is if a num is maxCurrent, we don’t need any number before it. And if the incoming number is greater than deque back, we can smash it

Step:

  1. Create a deque to store index
  2. If deque not empty and incoming is greater, smash anything is smaller
  3. Check if dq front is out of bound (i > dq.front()) if(j + 1 >= k) push_back result and move the i. (The if statement checks if j+1 < k, which we haven’t insert enough elements to meet the window size, j is index, ex. If k = 3, j at least should be 2 in index)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> sta; // store index
        int i = 0;
        vector<int> answer;
        for(int j = 0; j < nums.size(); ++j){
            while(!sta.empty() && nums[sta.back()] <= nums[j]){
                sta.pop_back();
            }
            sta.push_back(j);
            if(sta.front() < i){
                sta.pop_front();
            }

            if(j - i + 1 >= k){
                answer.push_back(nums[sta.front()]);
                ++i;
            }
        }
        return answer;
    }
};

Stack

155. Min Stack

  • The key of Min Stack is to use two stacks: nums and min_stack. The nums stack stores all the values, while the min_stack only stores the current minimum values and updates when a new value <= stack.top.

  • You might wonder, “What about when the incoming value is greater than the top of the stack? Shouldn’t it be stored in min_stack too?” The answer is no. You might think that if a larger value should be stored somewhere at the bottom of min_stack so that when all the smaller numbers are popped, this larger value will be needed. But that’s not true. When pop() is called, larger numbers will be popped before smaller ones, so there’s no need to store them in min_stack.

There are two approaches to solving this:

  1. Create nums and min_stack.

    • For Push(): push the value into nums and push into min_stack only if the condition is met.

    • For Pop(): pop from min_stack only if nums.top() == min_stack.top().

  2. Consider a scenario where the input is something like // 2 2 2 2 2. We don’t want to store all these values in the stack. Instead, create a pair<int, appearance> to keep track of the numbers and their frequencies.

class MinStack {
public:
stack<int> sta;
stack<int> min_track;
    MinStack() {
    }

    void push(int val) {
        if(min_track.empty() || val <= min_track.top()){
            min_track.push(val);
        }
        sta.push(val);
    }

    void pop() {
        if(!min_track.empty() && min_track.top() == sta.top()){
            min_track.pop();
        }
        sta.pop();
    }

    int top() {
        return sta.top();
    }

    int getMin() {
        return min_track.top();
    }
};

150. Evaluate Reverse Polish Notation

  • Polish Notation should be straightforward, the key is pushed back numbers to stack every time the calculation is done!
  • If we encounter a symbol, then we do the calculation from stack.

Step:

  1. Create a stack

    • Check if val is digit, if so, push to stack and continue; If(token.size() > 1 || isdigit(token[0]))
    • If we skip step 2, then val is an operator. Perform the operator and store it back to stack.
    • Eventually the stack will have only one num (the answer), return stack.top()
int evalRPN(vector<string>& tokens) {
    stack<int> sta; // stores number;
    for(string& s : tokens){
        if(isdigit(s[0]) || (s[0] == '-' && s.length() > 1)){
            sta.push(stoi(s));
            continue;
        }

        int num_1 = sta.top(); sta.pop();
        if(s == "+") sta.top() += num_1;
        if(s == "-") sta.top() -= num_1;
        if(s == "*") sta.top() *= num_1;
        if(s == "/") sta.top() /= num_1;
    }

    return sta.top();
}

22. Generate Parentheses

  • For generate parentheses We should know that we need “open” and “close” to both equal to n to push
  • Whenever open == close, ex: () / (( )) // () (), we could only add an open bracket.
  • Therefore we should visit open bracket first Only adding a close bracket if close < open, means we have extra open to be matched.

Step:

  1. Backtracking, we should create a helper function (vector answer, string temp, int n, int open, int close)
  2. If open and close both == n, push into answer
  3. If open < n, temp push an open bracket and helper(open + 1), finally remove temp.back
  4. If open > close, same thing, but push close bracket.
void helper(vector<string>& answer, string s, int left, int right){
    if(left == 0 && right == 0){
        answer.push_back(s);
        return;
    }

    if(left == right){
        helper(answer, s + "(", left - 1, right);
    }else if(left < right){
        if(left != 0) helper(answer, s + "(", left - 1, right);
        if(right != 0) helper(answer, s + ")", left, right - 1);
    }

}
vector<string> generateParenthesis(int n) {
    vector<string> answer;
    helper(answer, "", n, n);
    return answer;
}

23. Daily Temperatures

  • For Daily Temperatures, I’m correct with monolithic stack in the first place and obtained a solution by myself. The key is having a pair {temperature, index} in the stack. And pop only if currentTemp is higher [warmer], else push into stack

Step:

  1. Create a stack and vector for answer
  2. If sta not empty && currentTemp > sta.top()
    • answer[sta.top().second] = the gap in days
    • pop from stack
  3. Else, push into stack
vector<int> dailyTemperatures(vector<int>& temperatures) {
    stack<int> sta;
    vector<int> answer (temperatures.size(), 0);

    for(int i = 0; i < temperatures.size(); ++i){
        while(!sta.empty() && temperatures[i] > temperatures[sta.top()]){
            answer[sta.top()] = (i - sta.top());
            sta.pop();
        }
        sta.push(i);
    }

    return answer;
}

24. Car Fleet

  • The key of Car Fleet that we are dealing with the time cars get to the destination based on position and speed. Then if two cars spend the same time getting to the final, they will meet. Or the car behind spends less time (faster) to reach, they will also meet.

Step:

  1. Create a vector<position, double time> and store all the values
  2. Sort the vector based on position
  3. Make a fleet counter and maxTime
  4. Start from the back where the car is the closest to destination, and
    • if the time it spends is greater than maxTime
    • means the currentTime is not catching the previous carfleet, we should therefore increment the carfleet by one and update maxTime
class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, double>> cars(position.size());
        //(destination - position[i] / speed[i])
        for(int i = 0; i < position.size(); ++i){
            double time = (double)(target - position[i]) / speed[i];
            cars[i] = {position[i], time};
        }
        sort(cars.begin(), cars.end());

        int carFleet = 0;
        double maxTime = 0.0;
        for(int i = cars.size() - 1; i >= 0; --i){
            double time = cars[i].second;
            if(time > maxTime){
                maxTime = time;
                carFleet++;
            }
        }

        return carFleet;
    }
};

84. Largest Rectangle in Histogram

  • The idea for Largest Rectangle is we should know how far a unit can expand, and we should maintain it in the stack before that happens. And until when we reach a smaller height, we reach the end point, then we should pop from the stack and calculate the width (the initial point to expanding end) and height(initial height).

  • For the currentHeight, because we pop from stack until reaching a smaller unit where currentHeight cannot expand, we make that as our initial height for current.

Step:

  1. Create a stack <start, height>, maxArea for answer
  2. When stack is not empty and currentHeight is smaller, we pop the stack and update maxArea and start position of currentHeight
  3. Then push {start position, currentHeight} to stack
  4. After the loop, there are elements left in the stack which means these are heights that can expand till the end. Therefore we should update the maxArea by height * width (width is endpoint - start)
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<pair<int, int>> sta; // <start, height>
        int maxArea = 0;
        for(int i = 0; i < heights.size(); ++i){
            int start = i;
            while(!sta.empty() && heights[i] < sta.top().second){
                int width = i - sta.top().first;
                int height = sta.top().second;

                maxArea = max(maxArea, height * width);
                start = sta.top().first;

                sta.pop();
            }
            sta.push({start,heights[i]});
        }

        int n = heights.size();
        while(!sta.empty()){
            pair<int, int> p = sta.top();
            sta.pop();
            maxArea = max(maxArea, p.second * (n - p.first));
        }
        return maxArea;
    }
};

Binary Search

74. Search a 2D Matrix

  • The key of 2D Matrix is to recognize that not only is each row ordered, but each horizontal line is also ordered. This allows us to perform a binary search on the horizontal lines to find the target row, followed by a normal binary search within that row.
  • Therefore we downgrade a 2D matrix to a 1D array for binary search.

Step:

  1. Create an row variable
  2. Check if the target > last element in each row
    • if so, increase the row
    • else break
  3. Check edge case when target is way bigger than the entire matrix and therefore not in it, return false
  4. Create left and right, perform binary search
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    // Look for the row we want, downgrade our searching range from matrix to an array
    int row = 0;
    while(row < matrix.size()){
        if(target > matrix[row].back()){
            ++row;
        }else{
            break;
        }
    }

    // Check edge case target exceed the last element in matrix
    if(row >= matrix.size()){
        return false;
    }
    vector<int>& arr = matrix[row]; //target row

    // Simple binary search
    int left = 0, right = arr.size() - 1;
    while(left <= right){
        int mid = (right - left) / 2 + left;
        if(arr[mid] == target){
            return true;
        }else if(arr[mid] < target){
            left = mid + 1;;
        }else{
            right = mid - 1;
        }
    }
    return false;
}

875. Koko Eating Bananas

  • The key of Koko Eating Bananas is that we should decide what k bananas Koko eats, it can eat anywhere from 1 to the max in the piles, because anymore it will stop eating for one round.
  • Therefore do a binary search based on 1 to max

Step:

  1. Create low = 1, high to be maxPile, answer
  2. Create an hour counting, put it long int for number floating, binary search through the array.
    • If the hour is within time, update the answer to be minimum of (mid, answer)
  3. Hour can be calculated as:
    • hour += pile / mid + (pile % mid != 0) Or
    • hour += ceil((double) pile / mid) Or
    • hour += (pile + speed - 1) / speed
  4. Return answer;
int helper(vector<int>& piles, int speed){
    int hour = 0;
    for(int pile : piles){
        hour += (pile + speed - 1) / speed; // clever solution
    }
    return hour;
};
int minEatingSpeed(vector<int>& piles, int h) {
    // find max
    int maxEat = 0;
    for(int pile : piles){
        maxEat = max(maxEat, pile);
    }
    int left = 1, right = maxEat;
    int answer = maxEat;
    while(left <= right){
        int mid = (right - left) / 2 + left;
        int time = helper(piles, mid);
        if(time > h){
            left = mid + 1;
        }else{
            answer = mid;
            right = mid - 1;
        }
    }
    return answer;
}

153. Find Minimum in Rotated Sorted Array

  • For Find Minimum in Rotated Array, I am right in the first place:

    1. in a normal situation: left < mid < right, if rotation happens, where mid > right : “4 5 6 7 1 2 3”, left = mid + 1.
    2. Else, it means mid <= right, which is a normal array or “6 7 1 2 3” where mid is the number. Set right = mid;

  • Also for the while condition, we do left < right, we don’t need to check left == right. Because if left even equals to right, we found the minimum value

Step:

  1. Create left and right
  2. while(left < right), if (mid > right)
    • left = mid + 1.
    • Else right = mid;
  3. Return nums[left] or nums[right]
class Solution {
public:
    int findMin(vector<int>& nums) {
        //find the rotation point
        // suppose: Left < right
        // left < mid < right

        // right < mid: 4 5 6 7 1 2 3, left = mid + 1
        // right > mid: 8 2 3 4 5 6 7, right = mid

        int left = 0, right = nums.size() - 1, mid = 0;

        while(left < right){
            mid = (right - left) / 2 + left;
            if(nums[right] >= nums[mid]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        return nums[left];


        //binary search

    }
};

33. Search in Rotated Sorted Array

  • There are two ways to do Search in Rotated Sorted Array.
    1. One as we know, find the minimum rotation starter, and see if the target is a left or right sorted array.
    2. Another way is to do everything in one shot, which determines if the array is left sorted or right sorted. Here only explain the situation of second method which is harder

Step:

  1. Create left and right ptr
  2. while(left <= right), if(mid == target), return mid.
    • If (left <= mid), it’s left sorted “//1 2 3 4 5 6 7 or //3 4 5 6 7 1 2”, we need to figure out if the target is on the left or right.
    • If (target > nums[mid] || target < nums[left]) left = mid + 1.
    • Else right = mid - 1;
      1. Because mid > left, so if target > mid, that means target is also > left, we eliminate the entire left side, so we should go to right.
      2. If target <= mid, it could be the second case where mid = 6, and we have nums on left and right meet the condition, so if target < left, we go right.
  3. Right side the same idea.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;

            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > nums[right]){
                if(target >= nums[left] && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(target <= nums[right] && target > nums[mid]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }

//4 5 6 7 0 1 2
//3 4 5 6 7 0 1

//5 6 7 0 1 2 4
//6 7 0 1 3 4 5

        }
        return -1;
    }
};


//0 1 2 3 4 5 6 7
//4 5 6 7 0 1 2 3

4. Median of Two Sorted Arrays

  • There are three approaches for Median of Two Sorted Arrays:
    1. Merge the two arrays and perform a binary search. This takes O(m + n) time.
    2. Start from the beginning of both arr1 and arr2. Since we are looking for the median (the middle value), we can compare values one by one and move the pointer forward until we reach log(m+n) comparisons.
    3. Perform a binary search in the smaller array, which is the method I will explain.

Steps:

  1. Compare the two arrays and place the smaller array first. This is important because performing the search on the smaller array helps to eliminate the case where one array is empty.

  2. Create high and low pointers for the binary search on arr1.

  3. While low <= high, create a mid pointer for arr1 and a corresponding mid pointer for arr2. The total + 1 adjustment accounts for odd numbers, as we want to find the middle number.

  4. Define left1 as arr1[i - 1] and right1 as arr1[i] (the middle value in arr1). Define left2 as arr2[j - 1] and right2 as arr2[j](the middle value in arr2).

  5. By the nature of sorted arrays, left1 < right1 and left2 < right2 by default.

    • We should check if left1 <= right2 and left2 <= right1.
    • If both conditions are met, we’ve found the left sorted partition. Update the result based on whether the total length is odd or even, then exit the loop.

  6. If left1 > right1, it means the current partition is too large, so adjust by setting right = i - 1. Otherwise, if left2 > right1, it indicates that arr1 is too small, so expand the search by setting left = i + 1.

class Solution {
public:
int p1 = 0, p2 = 0;

    int mergeSort(vector<int>& nums1, vector<int>& nums2){
        if(p1 < nums1.size() && p2 < nums2.size()){
            return nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        }else if(p1 < nums1.size()){
            return nums1[p1++];
        }else{
            return nums2[p2++];
        }

        return -1;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();

        if((m+n) % 2 == 0){
            for(int i = 0; i < (m+n) / 2 - 1; ++i){
                mergeSort(nums1, nums2);
            }
            return (double)(mergeSort(nums1, nums2) + mergeSort(nums1, nums2)) / 2;
        }else{
            for(int i = 0; i < (m+n) / 2; ++i){
                mergeSort(nums1, nums2);
            }

            return mergeSort(nums1, nums2);
        }
    }
};