LeetCode | Learn for Master - Part 7
• ### 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.

• ### 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:

Analysis:

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:

• ### 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:

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

Analysis

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

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

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?

• ### Leetcode – Word Ladder solution In Java

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.

Analysis

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.

• ### Leetcode – LRU cache solution in Java

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.

Analysis

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.

• ### 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,

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

Analysis

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.