# Awesome Java Leetcode

## Easy

# Title Tag
1 Two Sum Array, Hash Table
7 Reverse Integer Math
9 Palindrome Number Math
13 Roman to Integer Math, String
14 Longest Common Prefix String
20 Valid Parentheses Stack, String
21 Merge Two Sorted Lists Linked List
26 Remove Duplicates from Sorted Array Array, Two Pointers
27 Remove Element Array, Two Pointers
28 Implement strStr() Two Pointers, String
35 Search Insert Position String
38 Count and Say String
53 Maximum Subarray Array, Divide and Conquer, Dynamic Programming
58 Length of Last Word String
66 Plus One Array, Math
69 Sqrt(x) Binary Search, Math
70 Climbing Stairs Dynamic Programming
83 Remove Duplicates from Sorted List Linked List
88 Merge Sorted Array Array, Two Pointers
100 Same Tree Tree, Depth-first Search
101 Symmetric Tree Tree, Depth-first Search, Breadth-first Search
104 Maximum Depth of Binary Tree Tree, Depth-first Search
107 Binary Tree Level Order Traversal II Tree, Breadth-first Search
108 Convert Sorted Array to Binary Search Tree Tree, Depth-first Search
110 Balanced Binary Tree Tree, Depth-first Search
111 Minimum Depth of Binary Tree Tree, Depth-first Search, Breadth-first Search
112 Path Sum Tree, Depth-first Search
118 Pascal’s Triangle Array
119 Pascal’s Triangle II Array
121 Best Time to Buy and Sell Stock Array, Dynamic Programmin
122 Best Time to Buy and Sell Stock II Array, Greedy
543 Diameter of Binary Tree Tree

## Medium

# Title Tag
3 Longest Substring Without Repeating Characters Hash Table, Two Pointers, String
5 Longest Palindromic Substring String
6 ZigZag Conversion String
8 String to Integer (atoi) Math, String
11 Container With Most Water Array, Two Pointers
12 Integer to Roman Math, String
15 3Sum Array, Two Pointers
16 3Sum Closest Array, Two Pointers
17 Letter Combinations of a Phone Number String, Backtracking
18 4Sum Array, Hash Table, Two Pointers
19 Remove Nth Node From End of List Linked List, Two Pointers
22 Generate Parentheses String, Backtracking
24 Swap Nodes in Pairs Linked List
29 Divide Two Integers Math, Binary Search
33 Search in Rotated Sorted Array Arrays, Binary Search
43 Multiply Strings Math, String
49 Group Anagrams Hash Table, String
50 Pow(x, n) Math, Binary Search
56 Merge Intervals Array, Sort
554 Brick Wall Hash Table

## Hard

# Title Tag
4 Median of Two Sorted Arrays Array, Binary Search, Divide and Conquer
10 Regular Expression Matching String, Dynamic Programming, Backtracking
23 Merge k Sorted Lists Linked List, Divide and Conquer, Heap
25 Reverse Nodes in k-Group Linked List
44 Wildcard Matching String, Dynamic Programming, Backtracking, Greedy
57 Insert Interval Array, Sort
68 Text Justification String

# 001 Two Sum

## Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Tags: Array, Hash Table

## Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

# 003 Longest Substring Without Repeating Characters

## Description

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Tags: Hash Table, Two Pointers, String

# 004 Median of Two Sorted Arrays

## Description

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:

Tags: Array, Binary Search, Divide and Conquer

## 思路

1. 当某个数组的数都被取完了，那么直接返回另一个数组的后 k 个元素即可。

2. k = 1 时，也就是只需再找一个数即可，也就是取两者当前较小的那个即可。

# 005 Longest Palindromic Substring

## Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Example:

Tags: String

## 思路 1

1. i == j 时，那么毫无疑问 dp[i][j] = true

2. i + 1 == j 时，那么 dp[i][j] 的值取决于 s[i] == s[j]

3. i + 1 < j 时，那么 dp[i][j] 的值取决于 dp[i + 1][j - 1] && s[i] == s[j]

## 思路 2

### 背景

1. s = “babad”，最长回文长度为 3，可以是 bab 或者 aba

2. s = “cbbda”，最长回文长度为 2，即 bb

3. s = “abcde”，最长回文长度为 1，即单个字符本身。

1975 年，一个叫 Manacher 的人发明了 Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 O(n)，下面我以我理解的思路来讲解其原理。

### 分析

str # l # o # l # l # o # o # l #
len[] 1 2 1 4 l 2 5 2 1 2 5 2 1 2 1

# 006 ZigZag Conversion

## Description

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Tags: String

# 007 Reverse Integer

## Description

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Example 2:

Example 3:

Note:

Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Tags: Math

# 008 String to Integer (atoi)

## Description

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Spoilers:

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Tags: Math, String

# 009 Palindrome Number

## Description

Determine whether an integer is a palindrome. Do this without extra space.

Spoilers:

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Tags: Math

# 010 Regular Expression Matching

## Description

Implement regular expression matching with support for '.' and '*'.

Tags: String, Dynamic Programming, Backtracking

## 思路 0

• 如果 sp 都为空，那么返回 true

• 如果 p 的长度为 1，当 s 的长度也为 1，并且他们首位匹配则返回 true，否则返回 false

• 如果 p 的第二个字符不为 ‘*’，如果 s 为空，那就返回 false，首位匹配则返回递归调用他们去掉首位的子字符串，否则返回 false

• 如果 p 的第二个字符为 ‘*’，循环当 s 不为空，且首位匹配，如果递归调用是否匹配 s 字符串和 p 去掉前两位的子字符串，则返回 true，否则 s 去掉首字母继续循环；

• 返回递归调用 s 字符串和 p 去掉前两位的子字符串是否匹配。

## 思路 1

• 如果 sp 都为空，那么返回 true

• 如果 p 的第二个字符为 *，由于 * 前面的字符个数可以为任意，那么我们先递归调用个数为 0 的情况；或者当 s 不为空，如果他们的首字母匹配，那么我们就递归调用去掉去掉首字母的 s 和完整的 p

• 如果 p 的第二个字符不为 *，那么我们就老老实实判断第一个字符是否匹配并且递归调用他们去掉首位的子字符串。

## 思路 2

• 如果 p[j - 1] == '*', dp[i][j] = dp[i][j - 2] || (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') && dp[i - 1][j];

• 如果 p[j - 1] != '*'dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]);

# 011 Container With Most Water

## Description

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Tags: Array, Two Pointers

# 012 Integer to Roman

## Description

Given an integer, convert it to a roman numeral.

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

Tags: Math, String

## 思路

• 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；

• 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；

• 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9。

# 013 Roman to Integer

## Description

Given a roman numeral, convert it to an integer.

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

Tags: Math, String

## 思路

• 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；

• 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；

• 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9。

# 014 Longest Common Prefix

## Description

Write a function to find the longest common prefix string amongst an array of strings.

Tags: String

# 015 3Sum

## Description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Tags: Array, Two Pointers

# 016 3Sum Closest

## Description

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Tags: Array, Two Pointers

# 017 Letter Combinations of a Phone Number

## Description

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Tags: String, Backtracking

# 018 4Sum

## Description

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Tags: Array, Hash Table, Two Pointers

# 019 Remove Nth Node From End of List

## Description

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Note:

Given n will always be valid.

Try to do this in one pass.

# 020 Valid Parentheses

## Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Tags: Stack, String

# 021 Merge Two Sorted Lists

## Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

# 022 Generate Parentheses

## Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

Tags: String, Backtracking

# 023 Merge k Sorted Lists

## Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Tags: Linked List, Divide and Conquer, Heap

# 024 Swap Nodes in Pairs

## Description

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

# 025 Reverse Nodes in k-Group

## Description

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

# 026 Remove Duplicates from Sorted Array

## Description

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Tags: Array, Two Pointers

# 027 Remove Element

## Description

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 by modifying the input array in-place with O(1) extra memory.

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

Example:

Tags: Array, Two Pointers

# 028 Implement strStr()

## Description

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Example 2:

Tags:** Two Pointers, String

# 029 Divide Two Integers

## Description

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Tags: Math, Binary Search

# 033 Search in Rotated Sorted Array

## Description

Suppose an array sorted in ascending order 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.

Tags: Arrays, Binary Search

# 035 Search Insert Position

## Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Example 2:

Example 3:

Example 1:

Tags: Array, Binary Search

# 038 Count and Say

## Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Example 2:

Tags: String

# 043 Multiply Strings

## Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

1. The length of both num1 and num2 is < 110.

2. Both num1 and num2 contains only digits 0-9.

3. Both num1 and num2 does not contain any leading zero.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Tags: Math, String

# 044 Wildcard Matching

## Description

Implement wildcard pattern matching with support for '?' and '*'.

Tags: String, Dynamic Programming, Backtracking, Greedy

## 思路 1

• 如果 p[j - 1] != '*'P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');

• 如果 p[j - 1] == '*'P[i][j] = P[i][j - 1] || P[i - 1][j]

# 049 Group Anagrams

## Description

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

Note: All inputs will be in lower-case.

Tags: Hash Table, String

# 050 Pow(x, n)

## Description

Implement pow(x, n).

Example 1:

Example 2:

Tags: Math, Binary Search

# 053 Maximum Subarray

## Description

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Tags: Array, Divide and Conquer, Dynamic Programming

# 056 Merge Intervals

## Description

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

Tags: Array, Sort

# 057 Insert Interval

## Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Tags: Array, Sort

## 思路

1. 首先把有序区间中小于待插入区间的部分加入到结果中；

2. 其次是插入待插入区间，如果有交集的话取两者交集的端点值；

3. 最后把有序区间中大于待插入区间的部分加入到结果中；

# 058 Length of Last Word

## Description

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Tags: String

# 066 Plus One

## Description

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Tags: Array, Math

## Description

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

Tags: Math, String

# 068 Text Justification

## Description

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,

words: ["This", "is", "an", "example", "of", "text", "justification."]

L: 16.

Return the formatted lines as:

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?

In this case, that line should be left-justified.

Tags: String

# 069 Sqrt(x)

## Description

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

Tags: Binary Search, Math

# 070 Climbing Stairs

## Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Example 2:

Tags: Dynamic Programming

# 083Remove Duplicates from Sorted List

## Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

# 088 Merge Sorted Array

## Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Tags: Array, Two Pointers

# 100 Same Tree

## Description

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Example 2:

Example 3:

Tags: Tree, Depth-first Search

# 101 Symmetric Tree

## Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:

Bonus points if you could solve it both recursively and iteratively.

Tags: Tree, Depth-first Search, Breadth-first Search

# 104 Maximum Depth of Binary Tree

## Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Tags: Tree, Depth-first Search

# 107 Binary Tree Level Order Traversal II

## Description

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

# 108 Convert Sorted Array to Binary Search Tree

## Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Tags: Tree, Depth-first Search

## 思路

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3. 任意节点的左、右子树也分别为二叉查找树；

4. 没有键值相等的节点。

# 110 Balanced Binary Tree

## Description

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Tags: Tree, Depth-first Search

# 111 Minimum Depth of Binary Tree

## Description

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Tags: Tree, Depth-first Search, Breadth-first Search

# 112 Path Sum

## Description

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Tags: Tree, Depth-first Search

# 118 Pascal’s Triangle

## Description

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,

Return

Tags: Array

# 119 Pascal’s Triangle II

## Description

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,

Return [1,3,3,1].

Note:

Could you optimize your algorithm to use only O(k) extra space?

Tags: Array

# 121 Best Time to Buy and Sell Stock

## Description

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:

Tags: Array, Dynamic Programmin

# 122 Best Time to Buy and Sell Stock II

## Description

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Tags: Array, Greedy

# 543 Diameter of Binary Tree

## Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Tags: Tree

# 554 Brick Wall

## Description

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Explanation:

Note:

1. The width sum of bricks in different rows are the same and won’t exceed INT_MAX.

2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

Tags: Hash Table