LeetCode | Learn for Master - Part 5
  • Leetcode – Roman to Integer (Java)

    Given a roman numeral, convert it to an integer.

    Input is guaranteed to be within the range from 1 to 3999.


    The rules to transfer a roman to an integer can be understood using the following examples:

    So for any two Roman letters in the form: Left Right

    if the left is smaller than the right, the result will be right – left.

    if the left is larger or equal to the right, the result will right + left.

    See this link for more examples of the roman numbers.

    [Read More...]
  • binary search – first bad version

    You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

    Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

    You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version.

    [Read More...]
  • LeetCode – Merge Sorted Array without extra space

    Given two sorted integer arrays A and B, merge B into A as one sorted array.

    You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.


    We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array. 

    We cannot start the merge from the beginning of the two arrays,

    [Read More...]
  • LeetCode – Find the kth largest element in an unsorted array (Java)

    Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

    For example,
    Given [3,2,1,5,6,4] and k = 2, return 5.

    You may assume k is always valid, 1 ≤ k ≤ array’s length.


    It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort. 

    Min Heap Based Method

    A better method is use a min heap or PriorityQueue with size K.  

    [Read More...]
  • LeetCode – Median of Two Sorted Arrays Java Solution

    There are two sorted arrays nums1 and nums2 of size m and n respectively.

    Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

    Example 1:

    Example 2:


    It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn). 

    For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm. 

    [Read More...]
  • Leetcode Isomorphic Strings solution Java

    Given two strings s and t, determine if they are isomorphic.

    Two strings are isomorphic if the characters in s can be replaced to get t.

    All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

    For example,
    Given “egg”, “add”, return true.

    Given “foo”, “bar”, return false.

    Given “paper”, “title”, return true.


    We can use a HashTable to map the letter from String1 to String2. 

    [Read More...]
  • LeetCode- Evaluate Reverse Polish Notation (Java)

    [LeetCode] Evaluate Reverse Polish Notation (RPN)
     Evaluate the value of an arithmetic expression in Reverse Polish Notation.
    Valid operators are +, -, *, /. Each operand may be an integer or another expression.
    Some examples:


    Evaluate RPN is the second step to build a calculator. Once we have converted the infix expression into the RPN,  we need to evaluate RPN to get the result. 

    The basic idea to evaluate reverse polish notation is to use a stack to process the strings.

    We scan the array of the RPN expression.

    [Read More...]
  • Leetcode – Reverse Words in a String II (Java)

    Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
    The input string does not contain leading or trailing spaces and the words are always separated by a single space.
    For example,
    Given s = "the sky is blue",
    return "blue is sky the".
    Could you do it in-place without allocating extra space?


    This problem is similar to the rotate array to right by k steps problem. 

    There are two steps:

    1. use the space ‘ ‘ to determine the boundary of words.
    [Read More...]
  • Leetcode- Rotate Array to right by K steps (java)

    Rotate an array of n elements to the right by k steps.

    For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

    How many different ways do you know to solve this problem?


    It is easy to use an intermediate array to solve this problem. Suppose the original array is A, the new array is B, we will copy 

    A[0:n-k -1] to B[k:n-1], and A[n – k:n-1] to B[0:k – 1], then we copy all the elements in B back to Array A using System.arrayCopy.

    [Read More...]
  • LeetCode – Binary Search Tree Iterator (Java)

    Binary Search Tree Iterator

    • Difficulty: Medium

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    Calling next() will return the next smallest number in the BST.

    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    Source: https://leetcode.com/problems/binary-search-tree-iterator/

    In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

    [Read More...]
Page 5 of 7« First...34567