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

• ### Leetcode – paint house I solution (Java)

Paint House I
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs is the cost of painting house 0 with color red; costs is the cost of painting house 1 with color green,

• ### Leetcode – Graph valid tree solution based on Union find set

Graph Valid Tree
Given n nodes labeled from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2],

• ### Leetcode – Meeting rooms solution in Java

Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

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

Analysis

We can sort the intervals using the start time. Then we check whether there is conflict.  For instance. for this two pairs,  [0, 30],[5, 10] As 5 is smaller than 30, the person cannot attend both.

When we do the check, we should record the latest end time before the current interval. For current interval,

• ### Leetcode – Color Sort

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,

• ### LeetCode- Search in Rotated Sorted Array Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array. Using the idea of binary search, we can reduce the search space based on which range the target value is located.

We first get the mid index of the array,

• ### Leetcode problems classified by company

1 Two Sum 23.0% Easy
21 Merge Two Sorted Lists 35.4% Easy
23 Merge k Sorted Lists 23.3% Hard
33 Search in Rotated Sorted Array 30.2% Hard
34 Search for a Range 29.1% Medium
46 Permutations 35.7% Medium
47 Permutations II 28.0% Medium
50 Pow(x, n) 27.9% Medium
53 Maximum Subarray 36.6% Medium
56 Merge Intervals 25.3% Hard
57 Insert Interval 23.8% Hard
65 Valid Number 12.1% Hard
68 Text Justification 16.1% Hard
76 Minimum Window Substring 21.2% Hard
101 Symmetric Tree 33.9% Easy
102 Binary Tree Level Order Traversal 32.7% Easy
103 Binary Tree Zigzag Level Order Traversal 28.6% Medium
104 Maximum Depth of Binary Tree 47.8% Easy
149 Max Points on a Line 14.2% Hard
150 Evaluate Reverse Polish Notation 23.5% Medium
152 Maximum Product Subarray 22.1% Medium
156 Binary Tree Upside Down 38.3% Medium
170 Two Sum III –

• ### LeetCode – Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

1. Try two pointers.
• ### LeetCode – Count Numbers with Unique Digits (Python)

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

1. A direct way is to use the backtracking approach.
2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
• ### LeetCode – Water and Jug Problem

leetcode Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

Operations allowed:

• Fill any of the jugs completely.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

1
2

Input: x = 2,