yitonghe00

// Array + Brutal force solution
// Time: O(n ^ 2), 212ms
// Space: O(1), 40.6mb
class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        
        for(int i = 0; i < nums.length; i++) {
            int sum = 0;
            for(int j = 0; i + j < nums.length; j++) {

yitonghe00

// Array solution: if A[i] > A[i + 1], A can't be increasing; if A[i] < A[i + 1], A can't be decreasing
// Time: O(n) for 2 pass, 1ms
// Space: O(1), 44.2mb
class Solution {
    public boolean isMonotonic(int[] A) {
        return increasing(A) || decreasing(A);
    }
    
    private boolean increasing(int[] A) {
        for(int i = 0; i < A.length - 1; i++) {

yitonghe00

// String solution
// Time: O(L + N ^ 2) where L = S.length() and N = words.length, 2ms
// Space: O(L + N ^ 2), 38.3mb
class Solution {
    public String toGoatLatin(String S) {
        Set<Character> vowel = new HashSet<>();
        for(char c : "aeiouAEIOU".toCharArray()) vowel.add(c);
        
        StringBuilder ans = new StringBuilder();
        String ending = "a";

yitonghe00

// Array solution: Sliding window and look back (from last) + remove out of window nums (from first)
// Time: O(n) for every element is added and removed once, 10ms
// Space: O(k), 49.3mb
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Corner case
        if(nums == null || k <= 0) return new int[0];
        
        // Deque of indices of potential max in window (first max, second max, ...)
        Deque<Integer> deque = new ArrayDeque<>();

yitonghe00

// Array + DP solution: keep the min & second min of last row
// Time: O(nk), 2ms
// Space: O(1) by overwriting the input, 40.9mb
class Solution {
    public int minCostII(int[][] costs) {
        // Corner case
        if(costs == null || costs.length == 0) return 0;
        
        // Find the min and second min in the first row
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE, minIndex = -1;

yitonghe00

// Array + DP solutoin: prefix and postfix product array, idea like 42 trap water #2
// Time: O(n), 1ms
// Space: O(n), 47.7mb
class Solution {
    public int[] productExceptSelf(int[] nums) {
        // Build array of prefix and postfix product
        int len = nums.length;
        int[] prefix = new int[len];
        int[] postfix = new int[len];
        

yitonghe00

// Math + Array solution
// Time: O(max(n, logK)), 3ms
// Space: O(1), 43.1mb
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> ans = new LinkedList<>();
        
        for(int i = A.length - 1; i >= 0 || K > 0; i--) {
            int sum = K;
            if(i >= 0) sum += A[i];

yitonghe00

// Math + Array solution: multiply the digits and put the result in specific indices
// Time: O(l1 + l2), 3ms
// Space: O(l1 + l2), 38.6mb
class Solution {
    public String multiply(String num1, String num2) {
        // Multiply the string into an array
        int l1 = num1.length(), l2 = num2.length();
        int[] ans = new int[l1 + l2];
        
        for(int i1 = l1 - 1; i1 >= 0; i1--) {

yitonghe00

// Array solution: modify the original array or create a new array for carry digit
// Time: O(n), 0ms
// Space: O(n), 37.5mb
class Solution {
    public int[] plusOne(int[] digits) {
        // Add one on original array
        for(int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] < 9) {
                digits[i]++;
                return digits;

yitonghe00

// String + Hash table solution: handling of two string of different length
// Time: O(n * l), 0ms
// Space: O(1), 43.5mb
class Solution {
    int[] table;    // table[alien] = order
    
    public boolean isAlienSorted(String[] words, String order) {
        // Create the mapping table
        table = new int[26];
        for(int i = 0; i < order.length(); i++) {