LeetCode | Learn for Master - Part 6
  • Leetcode – Best Time to Buy and Sell Stock (Java)

    Say you have an array for which the ith element is the price of a given stock on day i.

    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

    Example 1:

    Example 2:

    We scan the table, and record the minimum price in the range [0, i – 1], so the potential max profit is prices[i] – min(prices[0, i-1])
    The following is the implementation in Java:


    [Read More...]
  • Leetcode – Excel Sheet Column Number (Java)

    Given a column title as appear in an Excel sheet, return its corresponding column number.

    For example:

    Related to this question Excel Sheet Column Title

    This is a normal number system conversion problem.  Think about how we convert a binary number to a decimal number?

    1101001 = 1* 2 ^6 + 1 * 2^5 ..

    We can easily have the following implementation:


    [Read More...]
  • An efficient Prime number generation algorithm (Java)

    Given a number n, print all primes smaller than or equal to n. 

    For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.

    The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is not too large.

    Leetcode. Count Primes: https://leetcode.com/problems/count-primes/

    Here is the basic idea of this algorithm:

    1. Build a table or an array with n numbers from 1 to n. 
    [Read More...]
  • Leetcode – Largest Rectangle in Histogram Java

    Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

    Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

    The largest rectangle is shown in the shaded area, which has area = 10 unit.

    For example,
    Given heights = [2,1,5,6,2,3],
    return 10.


    A simple solution is to expand for each bar to its both left and right side until the bar is lower. 

    [Read More...]
  • Leetcode – Maximal Rectangle solution 1 (Java)

    Maximum Rectangle area for a 0 1 matrix.

    Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

    Source: https://leetcode.com/problems/maximal-rectangle/
    This is a hard one from Facebook.
    The key to solve this problem is to first build a matrix ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure. 
     leetcode maximal rectangle
    We have:

    We can fill up the matrix ones[][] using dynamic programming. The formula is :

    How to use the ones[][] matrix to calculate the maximum area?

    [Read More...]
  • Leetcode – Word Ladder solution In Java

    leetcode word   ladder

    Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

    One shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.


    From each word, we can change its letter one by one, thus a bread first search tree is constructed. The problem becomes to find the shortest path from the start word to the end word.

    [Read More...]
  • Leetcode – LRU cache solution in Java

    LRU cache figure

    Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

    get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
    set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.


    The popular method to implement an LRU cache is to use a bounded Queue. 

    The key to for implementing an LRU is to put any recently used data at the head of the queue.

    [Read More...]
  • Leetcode – Paint House II solution (Java)

    There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different.

    You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x k cost matrix.

    For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2,

    [Read More...]
  • Leetcode – Meeting Rooms II (Java)

    Meeting Rooms II
    Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

    For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

    This is a follow up question for the Meeting Rooms one. 


    This problem can be solved using the greedy method. We sort the intervals using the start time, then we try to merge the next one that has the smallest start time ts from the remaining intervals with the previous interval that has smallest end time te. 

    [Read More...]
  • LeetCode – Excel Sheet Column Title solution in Java

    Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:

    1 -> A
    2 -> B
    3 -> C

    26 -> Z
    27 -> AA
    28 -> AB

    To convert a number from a system with base m to Decimal number system, we can use the following formula:

    xyz = x * m^2 + y * m^1 + z * m^0.

    For instance, the binary number 1010 = 1 * 2^3 + 1 * 2^1 = 10. 

    Now to convert a number N in decimal system to a system with base m,

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