Problem

703. Kth Largest Element in a Stream

Java

priority queue - Java collections framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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.

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)

Problem

268. Missing Number

Java

leetcode solution

© Approach 3 Bit Manipulation

1
2
3
4
5
6
7
8
9

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

© Bitwise operators — Facts and Hacks - Compute XOR from 1 to n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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.

Problem

136. Single Number

Java

Hash Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5

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.

Problem

976. Largest Perimeter Triangle

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

Problem

1137. N-th Tribonacci Number

Java

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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.

Problem

1360. Number of Days Between Two Dates

Java

Origin-based algorithm

© Algorithms for calculating the difference of dates in days - 4. Origin-based Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

© FSI’s Experience with Language Learning

The following language learning timelines reflect 70 years of experience in teaching languages to U.S. diplomats, and illustrate the time usually required for a student to reach “Professional Working Proficiency” in the language, or a score of “Speaking-3/Reading-3” on the Interagency Language Roundtable scale. These timelines are based on what FSI has observed as the average length of time for a student to achieve proficiency, though the actual time can vary based on a number of factors, including the language learner’s natural ability, prior linguistic experience, and time spent in the classroom.

Category I Languages: 24-30 weeks (600-750 class hours)

Languages more similar to English.

• Danish (24 weeks)
• Dutch (24 weeks)
• French (30 weeks)
• Italian (24 weeks)
• Norwegian (24 weeks)
• Portuguese (24 weeks)
• Romanian (24 weeks)
• Spanish (24 weeks)
• Swedish (24 weeks)

Category II Languages: Approximately 36 weeks (900 class hours)

• German
• Haitian Creole
• Indonesian
• Malay
• Swahili

Category III Languages: Approximately 44 weeks (1100 class hours)

“Hard languages” – Languages with significant linguistic and/or cultural differences from English. This list is not exhaustive.

• Albanian
• Amharic
• Armenian
• Azerbaijani
• Bengali
• Bulgarian
• Burmese
• Czech
• Dari
• Estonian
• Farsi
• Finnish
• Georgian
• Greek
• Hebrew
• Hindi
• Hungarian
• Icelandic
• Kazakh
• Khmer
• Kurdish
• Kyrgyz
• Lao
• Latvian
• Lithuanian
• Macedonian
• Mongolian
• Nepali
• Polish
• Russian
• Serbo-Croatian
• Sinhala
• Slovak
• Slovenian
• Somali
• Tagalog
• Tajiki
• Tamil
• Telugu
• Thai
• Tibetan
• Turkish
• Turkmen
• Ukrainian
• Urdu
• Uzbek
• Vietnamese

Category IV Languages: 88 weeks (2200 class hours)

“Super-hard languages” – Languages which are exceptionally difficult for native English speakers.

• Arabic
• Chinese – Cantonese
• Chinese – Mandarin
• Japanese
• Korean

IELTS Academic mean performance by first language

IELTS Academic mean performance by nationality

• IELTS Test taker performance 2019
• IELTS Demographic data 2019

Problem

167. Two Sum II - Input array is sorted

Java

Brute-force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int[] idxArr = {0, 0};
        for (int i = 0; i < N; i++)
            for (int j = N - 1; j > i; j--) {
                if (numbers[j] + numbers[i] == target) {
                    idxArr[0] = i + 1;
                    idxArr[1] = j + 1;
                    return idxArr;
                }
            }
        return idxArr;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 191 ms, faster than 7.92% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.6 MB, less than 16.46% of Java online submissions for Two Sum II - Input array is sorted.

binary search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int index1 = 0, index2 = 0;
        for (int i = 0; i < N / 2 + 1; i++) {
            index1 = i;
            int diff = target - numbers[i];
            int lo = 0;
            int hi = i - 1;
            if (diff >= numbers[i]) {
                lo = i + 1;
                hi = N - 1;
            }
            index2 = search_rank(numbers, lo, hi, diff);
            if (index2 > -1) {
                index1++;
                index2++;
                break;
            }
        }
        return new int[]{index1, index2};
    }

    public int search_rank(int[] nums, int lo, int hi, int target) {
        // Array must be sorted.
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid - 1;
            else if (target > nums[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 2 ms, faster than 21.89% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.2 MB, less than 45.66% of Java online submissions for Two Sum II - Input array is sorted.

Two Pointer

Algorithm Two Pointer Technique:

The two pointer technique is a useful tool to utilize when searching for pairs in a sorted array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        for (int lo = 0, hi = N - 1; lo < hi; ) {
            if (numbers[lo] + numbers[hi] > target)
                hi--;
            else if (numbers[lo] + numbers[hi] < target) {
                lo++;
            } else {
                return new int[]{lo + 1, hi + 1};
            }
        }
        return new int[]{0, 0};
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 39.4 MB, less than 33.74% of Java online submissions for Two Sum II - Input array is sorted.

This land is your land, This land is my land,
From Bonavista, to Vancouver Island
From the Arctic Circle to the Great Lakes waters,
This land was made for you and me.

As I went walking that ribbon of highway,
I saw above me that endless skyway;
I saw below me that golden valley
This land was made for you and me.

I roamed and I rambled and I followed my footsteps,
To the sparkling sands of her diamond deserts;
While all around me a voice was sounding,
Saying this land was made for you and me.

The sun came shining, and I was strolling,
And the wheat fields waving and the dust clouds rolling;
As the fog was lifting, a voice was chanting,
This land was made for you and me.

This land is your land, this land is my land,
From Bonavista to Vancouver Island;
From the Arctic Circle to the Great Lakes waters,
This land was made for you and me.

• This Land Is Your Land
• Woody Guthrie
• This version was written and popularized by Canadian folk music group The Travellers in 1955.

• This Land is Your Land (Canadian Lyrics by The Travellers)
• The Travellers: This Land is Your Land (Canadian version)