Skip to content
System Design School

16-Hour Algorithms Cpp/Java

16-Hour Algorithms Course - C++ and Java Implementations

Hour 1-2: Foundation & Two Pointers

Problem 1: Two Sum (LeetCode #1)

C++ Implementation:

#include <vector>
#include <unordered_map>
using namespace std;


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashMap;


        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (hashMap.find(complement) != hashMap.end()) {
                return {hashMap[complement], i};
            }
            hashMap[nums[i]] = i;
        }


        return {};
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashMap = new HashMap<>();


        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (hashMap.containsKey(complement)) {
                return new int[]{hashMap.get(complement), i};
            }
            hashMap.put(nums[i], i);
        }


        return new int[]{};
    }
}

Problem 2: Valid Palindrome (LeetCode #125)

C++ Implementation:

#include <string>
#include <cctype>
using namespace std;


class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.length() - 1;


        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }


            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }


            left++;
            right--;
        }


        return true;
    }
};

Java Implementation:

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;


        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }


            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }


            left++;
            right--;
        }


        return true;
    }
}

Problem 3: Container With Most Water (LeetCode #11)

C++ Implementation:

#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 width = right - left;
            int area = width * min(height[left], height[right]);
            maxArea = max(maxArea, area);


            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }


        return maxArea;
    }
};

Java Implementation:

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;


        while (left < right) {
            int width = right - left;
            int area = width * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, area);


            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }


        return maxArea;
    }
}

Problem 4: 3Sum (LeetCode #15)

C++ Implementation:

#include <vector>
#include <algorithm>
using namespace std;


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


        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;


            int left = i + 1, right = n - 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++;
                    while (left < right && nums[right] == nums[right - 1]) right--;


                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }


        return result;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;


        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;


            int left = i + 1, right = n - 1;


            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];


                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));


                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;


                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }


        return result;
    }
}

Hour 3-4: Sliding Window & String Manipulation

Problem 5: Longest Substring Without Repeating Characters (LeetCode #3)

C++ Implementation:

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        unordered_map<char, int> charMap;
        int left = 0, maxLength = 0;


        for (int right = 0; right < n; right++) {
            if (charMap.find(s[right]) != charMap.end() && charMap[s[right]] >= left) {
                left = charMap[s[right]] + 1;
            }
            charMap[s[right]] = right;
            maxLength = max(maxLength, right - left + 1);
        }


        return maxLength;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Map<Character, Integer> charMap = new HashMap<>();
        int left = 0, maxLength = 0;


        for (int right = 0; right < n; right++) {
            if (charMap.containsKey(s.charAt(right)) && charMap.get(s.charAt(right)) >= left) {
                left = charMap.get(s.charAt(right)) + 1;
            }
            charMap.put(s.charAt(right), right);
            maxLength = Math.max(maxLength, right - left + 1);
        }


        return maxLength;
    }
}

Problem 6: Minimum Window Substring (LeetCode #76)

C++ Implementation:

#include <string>
#include <unordered_map>
#include <climits>
using namespace std;


class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";


        unordered_map<char, int> tCount;
        for (char c : t) tCount[c]++;


        int required = tCount.size();
        int left = 0, right = 0;
        int formed = 0;
        unordered_map<char, int> windowCounts;


        int minLen = INT_MAX, minLeft = 0, minRight = 0;


        while (right < s.length()) {
            char c = s[right];
            windowCounts[c]++;


            if (tCount.find(c) != tCount.end() && windowCounts[c] == tCount[c]) {
                formed++;
            }


            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }


                char leftChar = s[left];
                windowCounts[leftChar]--;


                if (tCount.find(leftChar) != tCount.end() && windowCounts[leftChar] < tCount[leftChar]) {
                    formed--;
                }


                left++;
            }


            right++;
        }


        return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";


        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }


        int required = tCount.size();
        int left = 0, right = 0;
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();


        int minLen = Integer.MAX_VALUE, minLeft = 0, minRight = 0;


        while (right < s.length()) {
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);


            if (tCount.containsKey(c) && windowCounts.get(c).intValue() == tCount.get(c).intValue()) {
                formed++;
            }


            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }


                char leftChar = s.charAt(left);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);


                if (tCount.containsKey(leftChar) && windowCounts.get(leftChar) < tCount.get(leftChar)) {
                    formed--;
                }


                left++;
            }


            right++;
        }


        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }
}

Problem 7: Sliding Window Maximum (LeetCode #239)

C++ Implementation:

#include <vector>
#include <deque>
using namespace std;


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;


        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }


            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }


            dq.push_back(i);


            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }


        return result;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();


        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }


            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }


            dq.offerLast(i);


            if (i >= k - 1) {
                result.add(nums[dq.peekFirst()]);
            }
        }


        return result.stream().mapToInt(i -> i).toArray();
    }
}

Problem 8: Longest Repeating Character Replacement (LeetCode #424)

C++ Implementation:

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;


class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;
        unordered_map<char, int> count;


        for (int right = 0; right < s.length(); right++) {
            count[s[right]]++;
            maxCount = max(maxCount, count[s[right]]);


            while (right - left + 1 - maxCount > k) {
                count[s[left]]--;
                left++;
            }


            maxLength = max(maxLength, right - left + 1);
        }


        return maxLength;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;
        Map<Character, Integer> count = new HashMap<>();


        for (int right = 0; right < s.length(); right++) {
            count.put(s.charAt(right), count.getOrDefault(s.charAt(right), 0) + 1);
            maxCount = Math.max(maxCount, count.get(s.charAt(right)));


            while (right - left + 1 - maxCount > k) {
                count.put(s.charAt(left), count.get(s.charAt(left)) - 1);
                left++;
            }


            maxLength = Math.max(maxLength, right - left + 1);
        }


        return maxLength;
    }
}

Hour 5-6: Arrays & Matrix Manipulation

Problem 9: Rotate Image (LeetCode #48)

C++ Implementation:

#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();


        // Transpose matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }


        // Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                swap(matrix[i][left], matrix[i][right]);
                left++;
                right--;
            }
        }
    }
};

Java Implementation:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;


        // Transpose matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }


        // Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

Problem 10: Spiral Matrix (LeetCode #54)

C++ Implementation:

#include <vector>
using namespace std;


class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};


        vector<int> result;
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;


        while (top <= bottom && left <= right) {
            // Traverse right
            for (int col = left; col <= right; col++) {
                result.push_back(matrix[top][col]);
            }
            top++;


            // Traverse down
            for (int row = top; row <= bottom; row++) {
                result.push_back(matrix[row][right]);
            }
            right--;


            if (top <= bottom) {
                // Traverse left
                for (int col = right; col >= left; col--) {
                    result.push_back(matrix[bottom][col]);
                }
                bottom--;
            }


            if (left <= right) {
                // Traverse up
                for (int row = bottom; row >= top; row--) {
                    result.push_back(matrix[row][left]);
                }
                left++;
            }
        }


        return result;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new ArrayList<>();


        List<Integer> result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;


        while (top <= bottom && left <= right) {
            // Traverse right
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++;


            // Traverse down
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--;


            if (top <= bottom) {
                // Traverse left
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--;
            }


            if (left <= right) {
                // Traverse up
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++;
            }
        }


        return result;
    }
}

Problem 11: Set Matrix Zeroes (LeetCode #73)

C++ Implementation:

#include <vector>
using namespace std;


class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;


        // Check if first row has zero
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }


        // Check if first column has zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }


        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }


        // Set zeros based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }


        // Handle first row and column
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }


        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

Java Implementation:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;


        // Check if first row has zero
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }


        // Check if first column has zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }


        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }


        // Set zeros based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }


        // Handle first row and column
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }


        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

Problem 12: Product of Array Except Self (LeetCode #238)

C++ Implementation:

#include <vector>
using namespace std;


class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);


        // Left pass
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }


        // Right pass
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * right;
            right = right * nums[i];
        }


        return result;
    }
};

Java Implementation:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];


        // Left pass
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }


        // Right pass
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * right;
            right = right * nums[i];
        }


        return result;
    }
}

Hour 7-8: Linked Lists & Fast/Slow Pointers

Problem 13: Reverse Linked List (LeetCode #206)

C++ Implementation:

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


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;


        while (current != nullptr) {
            ListNode* nextTemp = current->next;
            current->next = prev;
            prev = current;
            current = nextTemp;
        }


        return prev;
    }
};

Java Implementation:

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;


        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }


        return prev;
    }
}

Problem 14: Linked List Cycle II (LeetCode #142)

C++ Implementation:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }


        ListNode* slow = head;
        ListNode* fast = head;


        // Phase 1: Detect cycle
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }


        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }


        // Phase 2: Find cycle start
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }


        return slow;
    }
};

Java Implementation:

class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }


        ListNode slow = head;
        ListNode fast = head;


        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }


        if (fast == null || fast.next == null) {
            return null;
        }


        // Phase 2: Find cycle start
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }


        return slow;
    }
}

Problem 15: Merge Two Sorted Lists (LeetCode #21)

C++ Implementation:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;


        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }


        current->next = (list1 != nullptr) ? list1 : list2;


        return dummy->next;
    }
};

Java Implementation:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;


        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }


        current.next = (list1 != null) ? list1 : list2;


        return dummy.next;
    }
}

Problem 16: Remove Nth Node From End of List (LeetCode #19)

C++ Implementation:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;


        // Move first n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            first = first->next;
        }


        // Move both pointers until first reaches end
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }


        // Remove the nth node
        second->next = second->next->next;


        return dummy->next;
    }
};

Java Implementation:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;


        // Move first n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }


        // Move both pointers until first reaches end
        while (first != null) {
            first = first.next;
            second = second.next;
        }


        // Remove the nth node
        second.next = second.next.next;


        return dummy.next;
    }
}

Hour 9-10: Stack & Queue Patterns

Problem 17: Valid Parentheses (LeetCode #20)

C++ Implementation:

#include <string>
#include <stack>
#include <unordered_map>
using namespace std;


class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char, char> mapping = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };


        for (char c : s) {
            if (mapping.find(c) != mapping.end()) {
                char topElement = stk.empty() ? '#' : stk.top();
                if (!stk.empty()) stk.pop();


                if (mapping[c] != topElement) {
                    return false;
                }
            } else {
                stk.push(c);
            }
        }


        return stk.empty();
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');


        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) {
                char topElement = stack.empty() ? '#' : stack.pop();


                if (mapping.get(c) != topElement) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }


        return stack.empty();
    }
}

Problem 18: Daily Temperatures (LeetCode #739)

C++ Implementation:

#include <vector>
#include <stack>
using namespace std;


class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> result(n, 0);
        stack<int> stk;


        for (int i = 0; i < n; i++) {
            while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
                int prevIndex = stk.top();
                stk.pop();
                result[prevIndex] = i - prevIndex;
            }
            stk.push(i);
        }


        return result;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();


        for (int i = 0; i < n; i++) {
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                int prevIndex = stack.pop();
                result[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }


        return result;
    }
}

Problem 19: Largest Rectangle in Histogram (LeetCode #84)

C++ Implementation:

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;


class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        int maxArea = 0;
        int index = 0;


        while (index < heights.size()) {
            if (stk.empty() || heights[index] >= heights[stk.top()]) {
                stk.push(index);
                index++;
            } else {
                int top = stk.top();
                stk.pop();
                int width = stk.empty() ? index : index - stk.top() - 1;
                int area = heights[top] * width;
                maxArea = max(maxArea, area);
            }
        }


        while (!stk.empty()) {
            int top = stk.top();
            stk.pop();
            int width = stk.empty() ? index : index - stk.top() - 1;
            int area = heights[top] * width;
            maxArea = max(maxArea, area);
        }


        return maxArea;
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int index = 0;


        while (index < heights.length) {
            if (stack.empty() || heights[index] >= heights[stack.peek()]) {
                stack.push(index);
                index++;
            } else {
                int top = stack.pop();
                int width = stack.empty() ? index : index - stack.peek() - 1;
                int area = heights[top] * width;
                maxArea = Math.max(maxArea, area);
            }
        }


        while (!stack.empty()) {
            int top = stack.pop();
            int width = stack.empty() ? index : index - stack.peek() - 1;
            int area = heights[top] * width;
            maxArea = Math.max(maxArea, area);
        }


        return maxArea;
    }
}

Problem 20: Implement Queue using Stacks (LeetCode #232)

C++ Implementation:

#include <stack>
using namespace std;


class MyQueue {
private:
    stack<int> stack1; // for enqueue
    stack<int> stack2; // for dequeue


public:
    MyQueue() {}


    void push(int x) {
        stack1.push(x);
    }


    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int result = stack2.top();
        stack2.pop();
        return result;
    }


    int peek() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }


    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

Java Implementation:

import java.util.*;


class MyQueue {
    private Stack<Integer> stack1; // for enqueue
    private Stack<Integer> stack2; // for dequeue


    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }


    public void push(int x) {
        stack1.push(x);
    }


    public int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }


    public int peek() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }


    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}

Hour 11-12: Binary Search & Sorted Arrays

Problem 21: Binary Search (LeetCode #704)

C++ Implementation:

#include <vector>
using namespace std;


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


        while (left <= right) {
            int mid = left + (right - left) / 2;


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


        return -1;
    }
};

Java Implementation:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;


        while (left <= right) {
            int mid = left + (right - left) / 2;


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


        return -1;
    }
}

Problem 22: Search in Rotated Sorted Array (LeetCode #33)

C++ Implementation:

#include <vector>
using namespace std;


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


        while (left <= right) {
            int mid = left + (right - left) / 2;


            if (nums[mid] == target) {
                return mid;
            }


            if (nums[left] <= nums[mid]) { // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }


        return -1;
    }
};

Java Implementation:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;


        while (left <= right) {
            int mid = left + (right - left) / 2;


            if (nums[mid] == target) {
                return mid;
            }


            if (nums[left] <= nums[mid]) { // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }


        return -1;
    }
}

Problem 23: Find Minimum in Rotated Sorted Array (LeetCode #153)

C++ Implementation:

#include <vector>
using namespace std;


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


        while (left < right) {
            int mid = left + (right - left) / 2;


            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }


        return nums[left];
    }
};

Java Implementation:

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;


        while (left < right) {
            int mid = left + (right - left) / 2;


            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }


        return nums[left];
    }
}

Problem 24: Search a 2D Matrix (LeetCode #74)

C++ Implementation:

#include <vector>
using namespace std;


class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }


        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;


        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];


            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }


        return false;
    }
};

Java Implementation:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }


        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;


        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];


            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }


        return false;
    }
}

Hour 13-14: Trees & Depth-First Search

Problem 25: Maximum Depth of Binary Tree (LeetCode #104)

C++ Implementation:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }


        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);


        return 1 + max(leftDepth, rightDepth);
    }
};

Java Implementation:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }


        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);


        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Problem 26: Validate Binary Search Tree (LeetCode #98)

C++ Implementation:

#include <climits>
using namespace std;


class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }


private:
    bool validate(TreeNode* node, long minVal, long maxVal) {
        if (node == nullptr) {
            return true;
        }


        if (node->val <= minVal || node->val >= maxVal) {
            return false;
        }


        return validate(node->left, minVal, node->val) &&
               validate(node->right, node->val, maxVal);
    }
};

Java Implementation:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }


    private boolean validate(TreeNode node, long minVal, long maxVal) {
        if (node == null) {
            return true;
        }


        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }


        return validate(node.left, minVal, node.val) &&
               validate(node.right, node.val, maxVal);
    }
}

Problem 27: Lowest Common Ancestor of a Binary Search Tree (LeetCode #235)

C++ Implementation:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root != nullptr) {
            if (p->val < root->val && q->val < root->val) {
                root = root->left;
            } else if (p->val > root->val && q->val > root->val) {
                root = root->right;
            } else {
                return root;
            }
        }
        return nullptr;
    }
};

Java Implementation:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}

Problem 28: Binary Tree Right Side View (LeetCode #199)

C++ Implementation:

#include <vector>
using namespace std;


class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        rightViewDFS(root, 0, result);
        return result;
    }


private:
    void rightViewDFS(TreeNode* node, int level, vector<int>& result) {
        if (node == nullptr) {
            return;
        }


        if (level == result.size()) {
            result.push_back(node->val);
        }


        rightViewDFS(node->right, level + 1, result);
        rightViewDFS(node->left, level + 1, result);
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        rightViewDFS(root, 0, result);
        return result;
    }


    private void rightViewDFS(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }


        if (level == result.size()) {
            result.add(node.val);
        }


        rightViewDFS(node.right, level + 1, result);
        rightViewDFS(node.left, level + 1, result);
    }
}

Hour 15-16: Dynamic Programming Foundations

Problem 29: Climbing Stairs (LeetCode #70)

C++ Implementation:

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }


        int prev2 = 1;
        int prev1 = 2;


        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }


        return prev1;
    }
};

Java Implementation:

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }


        int prev2 = 1;
        int prev1 = 2;


        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }


        return prev1;
    }
}

Problem 30: House Robber (LeetCode #198)

C++ Implementation:

#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() == 1) {
            return nums[0];
        }


        int prev2 = nums[0];
        int prev1 = max(nums[0], nums[1]);


        for (int i = 2; i < nums.size(); i++) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }


        return prev1;
    }
};

Java Implementation:

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }


        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);


        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }


        return prev1;
    }
}

Problem 31: Longest Increasing Subsequence (LeetCode #300)

C++ Implementation:

#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }


        vector<int> dp(nums.size(), 1);


        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }


        return *max_element(dp.begin(), dp.end());
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }


        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);


        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }


        return Arrays.stream(dp).max().getAsInt();
    }
}

Problem 32: Coin Change (LeetCode #322)

C++ Implementation:

#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;


        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }


        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Java Implementation:

import java.util.*;


class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;


        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }


        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Study Strategy & Implementation Notes

Time & Space Complexity Summary

ProblemTime ComplexitySpace Complexity
Two SumO(n)O(n)
Valid PalindromeO(n)O(1)
Container With Most WaterO(n)O(1)
3SumO(n²)O(1)
Longest Substring Without RepeatingO(n)O(min(m,n))
Minimum Window SubstringO(|s| + |t|)O(|s| + |t|)
Sliding Window MaximumO(n)O(k)
Character ReplacementO(n)O(1)
Rotate ImageO(n²)O(1)
Spiral MatrixO(m×n)O(1)
Set Matrix ZeroesO(m×n)O(1)
Product of Array Except SelfO(n)O(1)
Reverse Linked ListO(n)O(1)
Linked List Cycle IIO(n)O(1)
Merge Two Sorted ListsO(n + m)O(1)
Remove Nth Node From EndO(n)O(1)
Valid ParenthesesO(n)O(n)
Daily TemperaturesO(n)O(n)
Largest Rectangle in HistogramO(n)O(n)
Queue using StacksO(1) amortizedO(n)
Binary SearchO(log n)O(1)
Search in Rotated Sorted ArrayO(log n)O(1)
Find Minimum in Rotated ArrayO(log n)O(1)
Search a 2D MatrixO(log(m×n))O(1)
Maximum Depth of Binary TreeO(n)O(h)
Validate Binary Search TreeO(n)O(h)
Lowest Common Ancestor BSTO(h)O(1)
Binary Tree Right Side ViewO(n)O(h)
Climbing StairsO(n)O(1)
House RobberO(n)O(1)
Longest Increasing SubsequenceO(n²)O(n)
Coin ChangeO(amount × n)O(amount)

Key Implementation Patterns

  1. Two Pointers: Use for array problems requiring linear time solutions
  2. Sliding Window: Maintain window boundaries and expand/contract based on conditions
  3. Hash Maps: Store indices or counts for O(1) lookups
  4. Stack: Use for problems requiring LIFO operations or monotonic sequences
  5. Binary Search: Apply to sorted arrays or search spaces
  6. DFS/Recursion: Natural for tree problems and backtracking
  7. Dynamic Programming: Break down into subproblems with optimal substructure

Language-Specific Notes

C++:

  • Use vector for dynamic arrays, unordered_map for hash tables
  • nullptr for null pointers, auto for type inference
  • STL algorithms like sort, max, min are highly optimized

Java:

  • Use ArrayList for dynamic arrays, HashMap for hash tables
  • null for null references, generics for type safety
  • Collections framework provides robust data structures and algorithms

This comprehensive implementation covers all 32 problems from the 16-hour algorithms course with both C++ and Java solutions, following the exact algorithms specified in the course material.