Array

1. 1. Two Sum

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/two-sum/">Two Sum</a>
 */
class TwoSum {
    private final Map<Integer, Integer> cache = new HashMap<>();

    public int[] twoSum(final int[] nums, final int target) {
        for (int i = 0; i < nums.length; i++) {
            final int residual = target - nums[i];
            if (cache.containsKey(residual)) {
                return new int[]{cache.get(residual), i};
            }
            cache.put(nums[i], i);
        }
        return new int[]{};
    }

    @Test
    void givenInput1_whenCheckTheTwoSum_thenItShouldReturn0And1() {
        final int[] nums = new int[]{2, 7, 11, 15};
        final int target = 9;
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
    }

    @Test
    void givenInput2_whenCheckTheTwoSum_thenItShouldReturn1And2() {
        final int[] nums = new int[]{3, 2, 4};
        final int target = 6;
        Assertions.assertArrayEquals(new int[]{1, 2}, twoSum(nums, target));
    }

    @Test
    void givenInput3_whenCheckTheTwoSum_thenItShouldReturn0And1() {
        final int[] nums = new int[]{3, 3};
        final int target = 6;
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
    }
}

2. 121. Best Time to Buy and Sell Stock

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;


class MaxProfit {
    public int maxProfit(final int[] prices) {
        int maxProfit = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if (prices[i] - min > maxProfit) {
                maxProfit = prices[i] - min;
            }
        }
        return maxProfit;
    }

    @Test
    void givenInput1_whenCalculateTheMaxProfit_thenItShouldReturn5() {
        final int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        assertEquals(5, maxProfit(prices));
    }

    @Test
    void givenInput2_whenCalculateTheMaxProfit_thenItShouldReturn0() {
        final int[] prices = new int[]{7, 6, 4, 3, 1};
        assertEquals(0, maxProfit(prices));
    }

}

3. 57. Insert Interval

Insert Interval - Leetcode 57 - Python

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> results = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] tmp = intervals[i];
            if (colide(tmp, newInterval)) {
                newInterval[0] = Math.min(tmp[0], newInterval[0]);
                newInterval[1] = Math.max(tmp[1], newInterval[1]);
            } else if (tmp[1] < newInterval[0]) {
                results.add(tmp);
            } else {
                // tmp[0] > newInterval[1]
                results.add(newInterval);
                results.add(tmp);
                for (int j = i+1; j < intervals.length; j++) {
                    results.add(intervals[j]);
                }
                return results.toArray(new int[results.size()][]);
            }
        }
        results.add(newInterval);
        return results.toArray(new int[results.size()][]);
    }

    private boolean colide(int[] a, int[] b) {
        return a[0] <= b[1] && a[1] >= b[0];
    }
    
    // This is the most concise solution
    private int[][] solution1(int[][] intervals, int[] newInterval) {
        List<int[]> results = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] tmp = intervals[i];
            if (tmp[1] < newInterval[0]) {
                results.add(tmp);
            } else if (newInterval[1] < tmp[0]) {
                results.add(newInterval);
                newInterval = tmp;
            } else {
                newInterval[0] = Math.min(tmp[0], newInterval[0]);
                newInterval[1] = Math.max(tmp[1], newInterval[1]);
            }
        }
        results.add(newInterval);
        return results.toArray(new int[results.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int size = intervals.size();
        for (int i = 0; i < size; i++) {
            vector<int>& tmp = intervals[i];
            if (collide(tmp, newInterval)) {
                newInterval[0] = min(tmp[0], newInterval[0]);
                newInterval[1] = max(tmp[1], newInterval[1]);
            } else if (tmp[1] < newInterval[0]) {
                res.emplace_back(tmp);
            } else {
                // newInterval[1] < tmp[0]
                res.emplace_back(newInterval);
                res.emplace_back(tmp);
                for (int j = i+1; j < size; j++) {
                    res.emplace_back(intervals[j]);
                }
                return res;
            }
        }
        res.emplace_back(newInterval);
        return res;
    }

    bool collide(const vector<int>& a, const vector<int>& b) {
        return a[0] <= b[1] && a[1] >= b[0];
    }
};

4. 15. 3Sum

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return new ArrayList<>(result);
            }
            int head = i+1;
            int tail = nums.length - 1;
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                if (sum == 0) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[head]);
                    tmp.add(nums[tail]);
                    result.add(tmp);
                    head++;
                } else if (sum > 0) {
                    tail--;
                } else {
                    head++;
                }
            }
        }
        return new ArrayList<>(result);
    }
}

5. 238. Product of Array Except Self

class Solution {
    public int[] productExceptSelf(int[] nums) {
        return solution2(nums);
    }

    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public int[] solution1(int[] nums) {
        int length = nums.length;
        int[] before = new int[length];
        before[0] = 1;
        for (int i = 1; i < length; i++) {
            before[i] = before[i-1] * nums[i-1];
        }
        int[] after = new int[length];
        after[length - 1] = 1;
        for (int i = length-2; i >= 0; i--) {
            after[i] = after[i+1] * nums[i+1];
        }
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = before[i] * after[i];
        }
        return result;
    }

    // Time Complexity: O(N)
    // Space Complexity: O(1)
    public int[] solution2(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];
        result[0] = 1;
        for (int i = 1; i < length; i++) {
            result[i] = result[i-1] * nums[i-1];
        }
        int after = 1;
        for (int i = length - 1; i>=0; i--) {
            result[i] = result[i] * after;
            after = nums[i] * after;
        }
        return result;
    }
}

6. Combination Sum

Using backtrack, not sure if there is other solutions like the memorization or dp.

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, current, 0, results);
        return results;
    }

    private void backtrack(int[] candidates, int target, List<Integer> current, int index, List<List<Integer>> results) {
        if (target == 0) {
            results.add(new ArrayList<>(current));
        }
        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            } else {
                current.add(candidates[i]);
                backtrack(candidates, target - candidates[i], current, i, results);
                current.remove(current.size() - 1);
            }
        }
    }
}

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> current;
        std::sort(candidates.begin(), candidates.end()); // Sort candidates for early exit and duplicate handling
        backtrack(candidates, target, current, 0, results);
        return results;
    }

    void backtrack(const vector<int>& candidates, const int target, vector<int>& current, const int index, vector<vector<int>>& results) {
        if (target == 0) {
            results.push_back(current); // copy
            return;
        }

        for (int i = index; i < candidates.size(); i++) {
            if (candidates[i] > target) {
                break;
            }
            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], current, i, results);
            // remove the last added candidate
            current.pop_back();
        }
    }
};

7. 56. Merge Intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return 0;
            }
            return a[0] > b[0] ? 1 : -1;
        });
        int[] tmp = intervals[0];
        List<int[]> result = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            if (cur[0] > tmp[1]) {
                result.add(tmp);
                tmp = cur;
            } else if (cur[1] < tmp[0]) {
                result.add(cur);
            } else {
                tmp = new int[] {Math.min(tmp[0], cur[0]), Math.max(tmp[1], cur[1])};
            }
        }
        result.add(tmp);
        return result.toArray(new int[result.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        vector<vector<int>> res;
        vector<int> tmp = intervals[0];
        for (int i = 1; i < intervals.size(); i++) {
            vector<int>& cur = intervals[i];
            if (tmp[0] > cur[1]) {
                res.emplace_back(cur);
            } else if (tmp[1] < cur[0]) {
                res.emplace_back(tmp);
                tmp = cur;
            } else {
                tmp[0] = min(tmp[0], cur[0]);
                tmp[1] = max(tmp[1], cur[1]);
            }
        }
        res.emplace_back(tmp);
        return res;
    }
};

8. Majority Element

class Solution {
    public int majorityElement(int[] nums) {
        return solution3(nums);
    }

    // sort
    private int solution1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    // Moore Voting Algorithm
    // https://leetcode.com/problems/majority-element/
    private int solution2(int[] nums) {
        int count = 0;
        int candidate = 0;

        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count++;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }

    private int solution3(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int target = nums.length / 2;
        for (int i = 0; i < nums.length; i++) {
            int prev = map.computeIfAbsent(nums[i], k -> 0);
            int cur = ++prev;
            if (cur > target) {
                return nums[i];
            }
            map.put(nums[i], cur);
        }
        return 0;
    }
}

// - []  Capture nothing (or, a scorched earth strategy?)
// - [&] Capture any referenced variable by reference
// - [=] Capture any referenced variable by making a copy
// - [=, &foo]   Capture any referenced variable by making a copy, but capture variable foo by reference
// - [bar]   Capture bar by making a copy; don't copy anything else
// - [this]  Capture the this pointer of the enclosing class

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return solution3(nums);
    }

private: 
    int solution1(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b){ return a < b; });
        return nums[nums.size()/2];
    }    

    int solution2(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
            if (count == 0) {
                candidate = *it;
                count++;
            } else if (*it != candidate) {
                count--;
            } else {
                count++;
            }
        }
        return candidate;
    }

    int solution3(vector<int>& nums) {
        unordered_map<int, int> m;
        int target = nums.size()/2;
        for (int i : nums) {
            // if m[i] not existing, the default value is 0 in this case
            m[i]++;
            if (m[i] > target) {
                return i;
            }
        }
        return 0;
    }
};

229. Majority Element II

Boyer-Moore Majority Voting Algorithm

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int candidate1 {0}, candidate2 {0}, count1 {0}, count2 {0};
        for (const auto& x : nums) {
            if (x == candidate1) {
                count1++;
            } else if (x == candidate2) {
                count2++;
            } else if (!count1) {
                candidate1 = x;
                count1++;
            } else if (!count2) {
                candidate2 = x;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = count2 = 0;

        for (const auto& x : nums) {
            if (x == candidate1) {
                count1++;
            } else if (x == candidate2) {
                count2++;
            }
        }

        vector<int> res;
        if (count1 > nums.size()/3) res.push_back(candidate1);
        if (count2 > nums.size()/3) res.push_back(candidate2);

        return res;
    }
};

9. 75. Sort Colors

class Solution {
    // Dutch National Flag algorithm
    public void sortColors(int[] nums) {
        int head = 0;
        int mid = 0;
        int tail = nums.length - 1;
        while (mid <= tail) {
            if (nums[mid] == 0 && nums[head] != 0) {
                int tmp = nums[head];
                nums[head++] = nums[mid];
                nums[mid++] = tmp;
            } else if (nums[mid] == 0 && nums[head] == 0) {
                mid++;
                head++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int tmp = nums[tail];
                nums[tail] = nums[mid];
                nums[mid] = tmp;
                tail--;
            }
        }
    }
}

10. Contains Duplicate

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return solution4(nums);
    }

private:
    bool solution1(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }    

    bool solution2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i-1]) {
                return true;
            }
        }
        return false;
    }

    bool solution3(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (s.count(nums[i]) > 0) {
                return true;
            }
            s.insert(nums[i]);
        }
        return false;
    }

    bool solution4(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i]] > 0) {
                return true;
            }
            m[nums[i]]++;
        }
        return false;
    }
};

class Solution {
    public boolean containsDuplicate(int[] nums) {
        return solution4(nums);
    }

    private boolean solution1(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean solution2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return true;
            }
        }
        return false;
    }

    private boolean solution3(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (s.contains(nums[i])) {
                return true;
            }
            s.add(nums[i]);
        }
        return false;
    }

    private boolean solution4(int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (m.containsKey(nums[i])) {
                return true;
            }
            m.put(nums[i], 1);
        }
        return false;
    }
}

11. 11. Container With Most Water

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(area, maxArea);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
};

912. Sort an Array

// bubble sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int lastExchangeIndex = 0; // optimization 2
        int sortedBoarder = nums.size() - 1; // optimization 2
        
        for (int i = 0; i < nums.size() -  1; i++) { // note that we need to minus 1
            bool sorted = true; // optimization 1
            for (int j = 0; j < sortedBoarder; j++) { // note that we need to minus (i+1) for optimization
                if (nums[j] > nums[j+1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    sorted = false;
                    lastExchangeIndex = j;
                }
            }
            sortedBoarder = lastExchangeIndex;
            if (sorted) {
                break;
            }
        }
        return nums;
    }
};

// cocktail
//TODO

// quick sort - double sides
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }

    void quickSort(vector<int>& nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(nums, start, end);
        quickSort(nums, start, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, end);
    }

    // return the pivot index
    int partition(vector<int>& nums, int start, int end) {
        int pivot = nums[start];
        int left = start;
        int right = end;

        while(left < right) { // check left < right
            while(left < right && nums[right] > pivot) { // note we check left < right again
                right--;
            }
            while(left < right && nums[left] <= pivot) { // note we check left < right again
                left++;
            }
            if (left < right) { // note we check left < right again
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }

        nums[start] = nums[left];
        nums[left] = pivot;
        return left;
    }
};

// quick sort -  single side
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }

    void quickSort(vector<int>& nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(nums, start, end);
        quickSort(nums, start, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, end);
    }

    // return the pivot index
    int partition(vector<int>& nums, int start, int end) {
        int pivot = nums[start];
        int mark = start;
        for (int i = start; i <= end; i++) {
            if (nums[i] < pivot) {
                mark++;
                int tmp = nums[i];
                nums[i] = nums[mark];
                nums[mark] = tmp;
            }
        }

        nums[start] = nums[mark];
        nums[mark] = pivot;
        return mark;
    }
};

// insertion sort - suitable for almost sorted data
// Insertion sort has a running time of O(n) at best when the list is already sorted or nearly-sorted, and O(n2) at worst when the list is in reverse.

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            int insertValue = nums[i];
            int j = i - 1;
            for (; j >= 0 && insertValue < nums[j]; j--) {
                nums[j+1] = nums[j];
            }
            nums[j+1] = insertValue;
        }
    }
};

Maximum number of overlapping Intervals

package com.damonyuan.matchingengine.service;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

public class RoomManagerImpl implements RoomManager {
    @Override
    public int getRooms(int[] checkIn, int[] checkOut) {
        if (checkIn == null || checkOut == null) {
            throw new RuntimeException("invalid input");
        }
        if (checkIn.length != checkOut.length) {
            throw new RuntimeException("invalid length");
        }
        if (checkIn.length == 0) {
            return 0;
        }

        return solution3(checkIn, checkOut);
    }

    // using ranges and brute-force
    private static int solution3(int[] checkIn, int[] checkOut) {
        final List<int[]> ranges = new ArrayList<>();
        for (int i = 0; i < checkIn.length; i++) {
            ranges.add(new int[] {checkIn[i], checkOut[i]});
        }
        ranges.sort(Comparator.comparingInt(a -> a[0]));
        int start = ranges.get(0)[0];
        int end = 0;
        for (int[] range : ranges) {
            end = Math.max(range[1], end);
        }

        int res = 0;
        for (int i = start; i <= end; i++) {
            int count = 0;
            for (int[] range : ranges) {
                if (i >= range[0] && i <= range[1]) {
                    count++;
                }
            }
            res = Math.max(res, count);
        }
        return res;
    }

    // using a stack
    private static int solution2(int[] checkIn, int[] checkOut) {
        final List<Integer> absSortedInAndOut = getAbsSortedCombinedList(checkIn, checkOut);
        int res = 0;
        final Stack<Integer> s = new Stack<>();
        for (int e : absSortedInAndOut) {
            if (e > 0) {
                s.push(e);
                res = Math.max(res, s.size());
            } else {
                s.pop();
            }
        }
        return res;
    }

    // using a variable
    private static int solution1(int[] checkIn, int[] checkOut) {
        final List<Integer> absSortedInAndOut = getAbsSortedCombinedList(checkIn, checkOut);
        int res = 0;
        int rooms = 0;
        for (int e : absSortedInAndOut) {
            if (e > 0) {
                rooms++;
                res = Math.max(rooms, res);
            } else {
                rooms--;
            }
        }
        return res;
    }

    private static List<Integer> getAbsSortedCombinedList(int[] checkIn, int[] checkOut) {
        final List<Integer> inAndOut = new ArrayList<>();
        for (int i : checkIn) {
            inAndOut.add(i);
        }
        for (int o : checkOut) {
            inAndOut.add(-o);
        }
        inAndOut.sort(Comparator.comparingInt(Math::abs));
        return inAndOut;
    }
}

class Solution {
public:
    int getRooms(vector<int>& checkIn, vector<int>& checkOut) {
        if (checkIn.size() != checkOut.size()) {
            throw std::invalid_argument("invalid length");
        }
        vector<int> combined;
        for (const int i : checkIn) {
            combined.emplace_back(i);
        }
        for (const int o : checkOut) {
            combined.emplace_back(-o);
        }
        sort(combined.begin(), combined.end(), [](const int a, const int b) {
            return abs(a) < abs(b);
        });
        int res = 0;
        int count = 0;
        for (const int& i : combined) {
            if (i > 0) {
                count++;
                res = max(res, count);
            } else {
                count--;
            }
        }
        return res;
    }
};