2020-12-22

LeetCode - Algorithms - 137. Single Number II

Problem

Java

Bitwise

We can design the digital logic what we need so the only one can still be extracted.

class Solution {
    public int singleNumber(int[] nums) {
        int lowBits = 0, highBits = 0;
        for (int num : nums) {
            lowBits = ~highBits & (lowBits ^ num);
            highBits = ~lowBits & (highBits ^ num);
        }
        return lowBits;        
    }
}

Submission Detail

14 / 14 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number II.
Memory Usage: 38.8 MB, less than 49.17% of Java online submissions for Single Number II.

2020-12-21

LeetCode - Algorithms - 27. Remove Element

Problem

27. Remove Element

javascript

Array.prototype.splice()

1

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    for(var i = 0; i < nums.length; i++){                 
        if ( nums[i] === val) { 
            nums.splice(i, 1); 
            i--; 
        }
    }
    return nums.length;
};

Submission Detail

113 / 113 test cases passed.
Runtime: 76 ms, faster than 85.28% of JavaScript online submissions for Remove Element.
Memory Usage: 38.6 MB, less than 69.26% of JavaScript online submissions for Remove Element.

2

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var index=nums.indexOf(val);
    while (index !== -1) {
        index = nums.indexOf(val);
        if (index!==-1)
            nums.splice(index, 1);
    }
    return nums.length;
};

Submission Detail

113 / 113 test cases passed.
Runtime: 80 ms, faster than 65.29% of JavaScript online submissions for Remove Element.
Memory Usage: 38.6 MB, less than 48.89% of JavaScript online submissions for Remove Element.

3

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let index
    while((index = nums.indexOf(val)) > -1) 
    {
      nums.splice(index, 1)
    }
    return nums.length;
};

Submission Detail

113 / 113 test cases passed.
Runtime: 80 ms, faster than 65.29% of JavaScript online submissions for Remove Element.
Memory Usage: 38.9 MB, less than 18.66% of JavaScript online submissions for Remove Element.

Two Pointers

Translation of © Solution - Approach 1: Two Pointers

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var i=0;
    for(var j=0;j<nums.length;j++) {
        if (nums[j]!=val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
};

Submission Detail

113 / 113 test cases passed.
Runtime: 76 ms, faster than 85.28% of JavaScript online submissions for Remove Element.
Memory Usage: 38.7 MB, less than 48.89% of JavaScript online submissions for Remove Element.

Java

Two Pointers

1

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
}

Submission Detail

113 / 113 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Element.
Memory Usage: 37.6 MB, less than 48.38% of Java online submissions for Remove Element.

2

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        for (int i = 0; i < n; ) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                n--;
            } else
                i++;
        }
        return n;
    }
}

Submission Detail

113 / 113 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Element.
Memory Usage: 37.7 MB, less than 48.38% of Java online submissions for Remove Element.

The Fastest Way to Remove a Specific Item from an Array in JavaScript

2020-12-20

LeetCode - Algorithms - 1143. Longest Common Subsequence

Problem

1143. Longest Common Subsequence

The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

For the general case of an arbitrary number of input sequences, the problem is NP-hard. When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming.

The LCS problem has an optimal substructure: the problem can be broken down into smaller, simpler subproblems, which can in turn be broken down into simpler subproblems, and so on, until, finally, the solution becomes trivial. LCS in particular has overlapping subproblems: the solutions to high-level subproblems often reuse solutions to lower level subproblems. Problems with these two properties are amenable to dynamic programming approaches, in which subproblem solutions are memoized, that is, the solutions of subproblems are saved for reuse.

Java

Hunt–Szymanski algorithm

Translation of © Hunt-Szymanski Algorithm(Match-List, 1977)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        return huntSzymanski_lcs(text1.toCharArray(), text2.toCharArray(), LEN1, LEN2);    
    }
    
    private int huntSzymanski_lcs(char[] stringA, char[] stringB, int m, int n) {
        final int alphabet_size = 256;
        int i, j, k, LCS, high, low, mid;
        int[][] matchlist = new int[alphabet_size][];
        int[] L;
        for (i = 0; i < alphabet_size; i++) {
            matchlist[i] = new int[n + 2];
        }
        L = new int[n + 1];

        // make the matchlist
        for (i = 0; i < m; i++) {
            if (matchlist[stringA[i]][0] == 0) {
                matchlist[stringA[i]][0] = 0;

                for (k = 1, j = n - 1; j >= 0; j--) {
                    if (stringA[i] == stringB[j]) {
                        matchlist[stringA[i]][k] = j + 1;
                        k++;
                    }
                    matchlist[stringA[i]][k] = -1;
                }
            }
        }

        // finding the LCS
        for (LCS = 0, i = 0; i < m; i++) {
            for (j = 0; matchlist[stringA[i]][j] != -1; j++) {
                // if the number bigger then the biggest number in the L, LCS + 1
                if (matchlist[stringA[i]][j] > L[LCS]) {
                    LCS++;
                    L[LCS] = matchlist[stringA[i]][j];
                }
                // else, do the binary search to find the place to insert the number
                else {
                    high = LCS;
                    low = 0;
                    k = 0;
                    while (true) {
                        mid = low + ((high - low) / 2);
                        if (L[mid] == matchlist[stringA[i]][j]) {
                            k = 1;
                            break;
                        }
                        if (high - low <= 1) {
                            mid = high;
                            break;
                        }
                        if (L[mid] > matchlist[stringA[i]][j]) {
                            high = mid;
                        } else if (L[mid] < matchlist[stringA[i]][j]) {
                            low = mid;
                        }
                    }
                    if (k == 0) {
                        L[mid] = matchlist[stringA[i]][j];
                    }
                }
            }
        }
        return LCS;
    }    
}

Submission Detail

43 / 43 test cases passed.
Runtime: 12 ms, faster than 32.13% of Java online submissions for Longest Common Subsequence.
Memory Usage: 39.2 MB, less than 92.10% of Java online submissions for Longest Common Subsequence.

Dynamic Programming

bottom-up approach

Oftentimes I found Wikipedia is helpful when doing leetcode algorithm problems.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        int[][] C = new int[LEN1 + 1][LEN2 + 1];
        for (int i = 1; i <= LEN1; i++) {
            for (int j = 1; j <= LEN2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    C[i][j] = C[i - 1][j - 1] + 1;
                } else {
                    C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
                }
            }
        }
        return C[LEN1][LEN2];     
    }
}

Submission Detail

43 / 43 test cases passed.
Runtime: 18 ms, faster than 17.54% of Java online submissions for Longest Common Subsequence.
Memory Usage: 42.8 MB, less than 51.59% of Java online submissions for Longest Common Subsequence.

top-down approach (momoized version)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        Map<String, Integer> map = new HashMap<String, Integer>();
        return lcsLength(text1, text2, LEN1, LEN2, map);
    }
    
    private int lcsLength(String X, String Y, int m, int n, Map<String, Integer> lookup) {
        // return if we have reached the end of either string
        if (m == 0 || n == 0)
            return 0;

        // construct an unique map key from dynamic elements of the input
        String key = m + "|" + n;

        // if sub-problem is seen for the first time, solve it and
        // store its result in a map
        if (!lookup.containsKey(key)) {
            // if last character of X and Y matches
            if (X.charAt(m - 1) == Y.charAt(n - 1)) {
                lookup.put(key, lcsLength(X, Y, m - 1, n - 1, lookup) + 1);

            } else {
                // else if last character of X and Y don't match
                lookup.put(key, Integer.max(lcsLength(X, Y, m, n - 1, lookup), lcsLength(X, Y, m - 1, n, lookup)));
            }
        }

        // return the subproblem solution from the map
        return lookup.get(key);
    }   
}

Submission Detail

43 / 43 test cases passed.
Runtime: 295 ms, faster than 5.04% of Java online submissions for Longest Common Subsequence.
Memory Usage: 167 MB, less than 5.04% of Java online submissions for Longest Common Subsequence.

javascript

Dynamic Programming

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    var LEN1 = text1.length, LEN2 = text2.length;
    var C = [];
    for (var i = 0; i <= LEN1; i++) {
        C.push([]);
        for (var j = 0; j <= LEN2; j++) {
            C[i].push(0);
        }
    }
    for (var i = 1; i <= LEN1; i++) {
        for (var j = 1; j <= LEN2; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                C[i][j] = C[i - 1][j - 1] + 1;
            } else {
                C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
            }
        }
    }
    return C[LEN1][LEN2];    
};

Submission Detail

43 / 43 test cases passed.
Runtime: 116 ms, faster than 60.08% of JavaScript online submissions for Longest Common Subsequence.
Memory Usage: 53.4 MB, less than 22.63% of JavaScript online submissions for Longest Common Subsequence.

2020-12-18

LeetCode - Algorithms - 703. Kth Largest Element in a Stream

Problem

703. Kth Largest Element in a Stream

Java

priority queue - Java collections framework

import java.util.PriorityQueue;

class KthLargest {
    private int k;
    private PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<Integer>(k);
        for(int i : nums) {
            minHeap.offer(i);
            if (minHeap.size()>k)
                minHeap.poll();
        }        
    }
    
    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size()>k)
            minHeap.poll();
        return minHeap.peek();        
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

Submission Detail

10 / 10 test cases passed.
Runtime: 17 ms, faster than 49.28% of Java online submissions for Kth Largest Element in a Stream.
Memory Usage: 44.3 MB, less than 60.24% of Java online submissions for Kth Largest Element in a Stream.

2020-12-17

On Hearing a Symphony of Beethoven

by Edna St. Vincent Millay

Sweet sounds, oh, beautiful music, do not cease!
Reject me not into the world again.
With you alone is excellence and peace,
Mankind made plausible, his purpose plain.
Enchanted in your air benign and shrewd,
With limbs a-sprawl and empty faces pale,
The spiteful and the stingy and the rude
Sleep like the scullions in the fairy-tale.
This moment is the best the world can give:
The tranquil blossom on the tortured stem.
Reject me not, sweet sounds; oh, let me live,
Till Doom espy my towers and scatter them,
A city spell-bound under the aging sun.
Music my rampart, and my only one.

On Hearing a Symphony of Beethoven
One of the most significant facts, for the understanding of Beethoven, is that his work shows an organic development up until the very end… The greatest music Beethoven ever wrote is to be found in the last string quartets, and the music of every decade before the final period was greater than its predecessor. (Shakespeare, Newton, and Beethoven: Or, Patterns of Creativity, a talk by Subrahmanyan Chandrasekhar)

2020-12-16

LeetCode - Algorithms - 268. Missing Number

Problem

268. Missing Number

Java

leetcode solution

class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int r = N;
        for (int i = 0; i < N; i++)
            r ^= i ^ nums[i];
        return r;        
    }
}

Submission Detail

122 / 122 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Number.
Memory Usage: 47.8 MB, less than 5.40% of Java online submissions for Missing Number.

2

class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int x = computeXOR(N);
        x = 0 ^ x;
        int y = nums[0];
        for (int i = 1; i < N; i++) {
            y = y ^ nums[i];
        }
        return x ^ y;        
    }
    
    private int computeXOR(int n) {
        if (n % 4 == 0) return n;
        if (n % 4 == 1) return 1;
        if (n % 4 == 2) return n + 1;
        else return 0;
    }
}

Submission Detail

122 / 122 test cases passed.
Runtime: 1 ms, faster than 40.83% of Java online submissions for Missing Number.
Memory Usage: 48 MB, less than 5.40% of Java online submissions for Missing Number.

2020-12-15

LeetCode - Algorithms - 136. Single Number

Problem

136. Single Number

Java

Hash Set

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> c = new HashSet<Integer>();
        for (int i : nums) {
            if (c.contains(i))
                c.remove(i);
            else
                c.add(i);
        }
        return c.iterator().next();        
    }
}

Submission Detail

61 / 61 test cases passed.
Runtime: 8 ms, faster than 42.20% of Java online submissions for Single Number.
Memory Usage: 39.8 MB, less than 22.36% of Java online submissions for Single Number.

sorting

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        final int N = nums.length;
        if (N == 1)
            return nums[0];
        if (nums[0] != nums[1])
            return nums[0];
        if (nums[N - 1] != nums[N - 2])
            return nums[N - 1];
        for (int i = 1; i < N - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];       
    }
}

Submission Detail

61 / 61 test cases passed.
Runtime: 5 ms, faster than 54.05% of Java online submissions for Single Number.
Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.

XOR Bitwise

n ^ n = 0

n ^ 0 = n

class Solution {
    public int singleNumber(int[] nums) {
        int r = nums[0];
        for (int i = 1; i < nums.length; i++) {
            r = r ^ nums[i];
        }
        return r;       
    }
}

Submission Detail

61 / 61 test cases passed.
Runtime: 1 ms, faster than 94.97% of Java online submissions for Single Number.
Memory Usage: 39.1 MB, less than 79.60% of Java online submissions for Single Number.

java8 stream + xor bitwise

class Solution {
    public int singleNumber(int[] nums) {
        return Arrays.stream(nums).reduce(0, (a, b) -> a^b);      
    }
}

Submission Detail

61 / 61 test cases passed.
Runtime: 2 ms, faster than 55.66% of Java online submissions for Single Number.
Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.

2020-12-14

LeetCode - Algorithms - 976. Largest Perimeter Triangle

Problem

976. Largest Perimeter Triangle

Java

1

class Solution {    
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        int a, b, c;
        for (int i = A.length - 1; i >= 2; i--) {
            a = A[i - 2];
            b = A[i - 1];
            c = A[i];
            if (a + b > c) {
                return a + b + c;
            }
        }
        return 0;       
    }
}

Submission Detail

84 / 84 test cases passed.
Runtime: 6 ms, faster than 99.79% of Java online submissions for Largest Perimeter Triangle.
Memory Usage: 39.4 MB, less than 76.17% of Java online submissions for Largest Perimeter Triangle.

2020-12-12

LeetCode - Algorithms - 1137. N-th Tribonacci Number

Problem

1137. N-th Tribonacci Number

Java

DP

class Solution {
    public int tribonacci(int n) {
        int T = 0;
        int T1 = 0, T2 = 1, T3 = 1;
        if (n == 0)
            T = 0;
        if (n == 1)
            T = 1;
        if (n == 2)
            T = 1;
        for (int i = 3; i <= n; i++) {
            T = T1 + T2 + T3;
            T1 = T2;
            T2 = T3;
            T3 = T;
        }
        return T;
    }
}

Submission Detail

39 / 39 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for N-th Tribonacci Number.
Memory Usage: 35.8 MB, less than 47.18% of Java online submissions for N-th Tribonacci Number.

2020-12-11

LeetCode - Algorithms - 1360. Number of Days Between Two Dates

Problem

1360. Number of Days Between Two Dates

Java

Origin-based algorithm

class Solution {
    final static int[] daysUpToMonth = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    final static int[] daysUpToMonthLeapYear = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};

    public boolean isLeapYear(int year) {
        return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0));
    }
    
    public int GetDaysOffsetFromOrigin(int year, int month, int day) {
        if (isLeapYear(year)) {
            year--;
            int numOfLeapsYear = year / 4 - year / 100 + year / 400;
            return year * 365 + numOfLeapsYear + daysUpToMonthLeapYear[month - 1] + day - 1;
        } else {
            year--;
            int numOfLeapsYear = year / 4 - year / 100 + year / 400;
            return year * 365 + numOfLeapsYear + daysUpToMonth[month - 1] + day - 1;
        }
    }    
    
    public int daysBetweenDates(String date1, String date2) {
        int y1 = Integer.parseInt(date1.substring(0, 4));
        int m1 = Integer.parseInt(date1.substring(5, 7));
        int d1 = Integer.parseInt(date1.substring(8, 10));

        int y2 = Integer.parseInt(date2.substring(0, 4));
        int m2 = Integer.parseInt(date2.substring(5, 7));
        int d2 = Integer.parseInt(date2.substring(8, 10));

        int daysOffset = GetDaysOffsetFromOrigin(y1, m1, d1);
        int daysOffset2 = GetDaysOffsetFromOrigin(y2, m2, d2);

        int diff = daysOffset2 - daysOffset;

        return diff >= 0 ? diff : -diff;        
    }
}

Submission Detail

105 / 105 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Number of Days Between Two Dates.
Memory Usage: 37.1 MB, less than 71.69% of Java online submissions for Number of Days Between Two Dates.

jdk

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

import static java.time.temporal.ChronoUnit.DAYS;

class Solution {
    public int daysBetweenDates(String date1, String date2) {
        DateTimeFormatter dft = DateTimeFormatter.ofPattern("yyyy-MM-dd");
        LocalDate d1 = LocalDate.parse(date1, dft);
        LocalDate d2 = LocalDate.parse(date2, dft);
        long diff = DAYS.between(d1, d2);
        int d = new Long(diff).intValue();
        return d >= 0 ? d : -d;        
    }
}

Submission Detail

105 / 105 test cases passed.
Runtime: 14 ms, faster than 13.23% of Java online submissions for Number of Days Between Two Dates.
Memory Usage: 38.4 MB, less than 21.16% of Java online submissions for Number of Days Between Two Dates.