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)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

© https://www.techiedelight.com/longest-common-subsequence/

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
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

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
/**
 * @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.

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

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.

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)

LeetCode - Algorithms - 268. Missing Number

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.

LeetCode - Algorithms - 136. Single 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.

LeetCode - Algorithms - 976. Largest Perimeter Triangle

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.

LeetCode - Algorithms - 1137. N-th Tribonacci Number

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.

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

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.

Language difficulty ranking for English speaker by FSI

© 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

Reading Listening Writing Speaking Overall
English 6.7 7.2 6.2 7.1 6.9
Italian 7.4 7.0 5.9 6.6 6.8
French 6.9 6.9 5.9 6.6 6.7
German 7.7 7.9 6.3 7.4 7.4
Indonesian 6.7 6.7 5.8 6.3 6.4
Russian 6.7 6.8 5.9 6.5 6.5
Chinese 6.2 6.0 5.5 5.5 5.9
Japanese 6.1 5.9 5.5 5.5 5.8
Korean 6.3 6.3 5.6 5.8 6.0

IELTS Academic mean performance by nationality

Reading Listening Writing Speaking Overall
Canada 6.9 7.2 6.1 7.2 6.9
Italy 7.3 7.0 5.9 6.6 6.8
France 7.1 7.0 5.9 6.6 6.7
Germany 7.7 7.9 6.3 7.4 7.4
Russian Federation 6.9 7.0 6.0 6.7 6.7
Indonesia 6.7 6.8 5.8 6.3 6.5
Malaysia 7.1 7.4 6.1 6.8 6.9
Philippines 6.8 7.3 6.1 6.8 6.8
India 5.9 6.5 5.8 6.0 6.1
Japan 6.1 5.9 5.5 5.5 5.8
Korea, Republic of 6.3 6.3 5.6 5.8 6.0
Hong Kong. SAR of China 6.9 7.1 6.0 6.3 6.6
Taiwan, China 6.3 6.3 5.6 6.0 6.1
China 6.2 5.9 5.5 5.4 5.8

LeetCode - Algorithms - 167. Two Sum II - Input array is sorted

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.
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.