出于方便的目的，我从LeetCode上抓取了所有非付费的题目，并保留了截至抓取题目为止的题目提交情况。 如有侵犯到您的权利，请联系我立即删除。 题目为逆序展示

Problem: 322. Coin Change

My Submissions

Question

Total Accepted: 1568 Total Submissions: 6122 Difficulty: Medium

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Example 2: coins = [2], amount = 3 return -1.

Note: You may assume that you have an infinite number of each kind of coin.

Problem: 321. Create Maximum Number

My Submissions

Question

Total Accepted: 897 Total Submissions: 4945 Difficulty: Hard

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9]

Problem: 319. Bulb Switcher

My Submissions

Question

Total Accepted: 3674 Total Submissions: 9981 Difficulty: Medium

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the nth round, you only toggle the last bulb.

Find how many bulbs are on after n rounds.

Example: Given n = 3. At first, the three bulbs are [off, off, off]. After first round, the three bulbs are [on, on, on]. After second round, the three bulbs are [on, off, on]. After third round, the three bulbs are [on, off, off]. So you should return 1, because there is only one bulb is on.

Problem: 318. Maximum Product of Word Lengths

My Submissions

Question

Total Accepted: 4091 Total Submissions: 11218 Difficulty: Medium

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”] Return 16 The two words can be “abcw”, “xtfn”.

Example 2:

Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”] Return 4 The two words can be “ab”, “cd”.

Example 3:

Given [“a”, “aa”, “aaa”, “aaaa”] Return 0 No such pair of words.

Problem: 316. Remove Duplicate Letters

My Submissions

Question

Total Accepted: 3483 Total Submissions: 16906 Difficulty: Medium

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given “bcabc” Return “abc”

Given “cbacdcbc” Return “acdb”

Problem: 315. Count of Smaller Numbers After Self

My Submissions

Question

Total Accepted: 2445 Total Submissions: 9320 Difficulty: Hard

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Problem: 313. Super Ugly Number

My Submissions

Question

Total Accepted: 3670 Total Submissions: 12596 Difficulty: Medium

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

Problem: 312. Burst Balloons

My Submissions

Question

Total Accepted: 2812 Total Submissions: 9222 Difficulty: Hard

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums.

You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167

Problem: 310. Minimum Height Trees

My Submissions

Question

Total Accepted: 3684 Total Submissions: 14954 Difficulty: Medium

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

0 | 1 /
2 3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

0 1 2 \ | / 3 | 4 | 5

return [3, 4]

Hint:Show Hint How many MHTs can a graph have at most?

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Problem: 309. Best Time to Buy and Sell Stock with Cooldown

My Submissions

Question

Total Accepted: 4253 Total Submissions: 12616 Difficulty: Medium

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) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example: prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

Problem: 307. Range Sum Query - Mutable

My Submissions

Question

Total Accepted: 3716 Total Submissions: 23552 Difficulty: Medium

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example: Given nums = [1, 3, 5]

sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.

Problem: 306. Additive Number

My Submissions

Question

Total Accepted: 3813 Total Submissions: 15938 Difficulty: Medium

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example: “112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 “199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Follow up: How would you handle overflow for very large input integers?

Problem: 304. Range Sum Query 2D - Immutable

My Submissions

Question

Total Accepted: 5153 Total Submissions: 24838 Difficulty: Medium

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ]

sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12

Note:

You may assume that the matrix does not change. There are many calls to sumRegion function. You may assume that row1 ≤ row2 and col1 ≤ col2.

Problem: 303. Range Sum Query - Immutable

My Submissions

Question

Total Accepted: 11926 Total Submissions: 50187 Difficulty: Easy

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example: Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

Note:

You may assume that the array does not change. There are many calls to sumRange function.

Problem: 301. Remove Invalid Parentheses

My Submissions

Question

Total Accepted: 5436 Total Submissions: 18739 Difficulty: Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples: “()())()” -> [”()()()”, “(())()”] “(a)())()” -> [“(a)()()”, “(a())()”] “)(“ -> [””]

Problem: 300. Longest Increasing Subsequence

My Submissions

Question

Total Accepted: 11134 Total Submissions: 34553 Difficulty: Medium

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Problem: 299. Bulls and Cows

My Submissions

Question

Total Accepted: 12779 Total Submissions: 47587 Difficulty: Easy

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example: Secret number: “1807” Friend’s guess: “7810”

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example: Secret number: “1123” Friend’s guess: “0111”

In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

Problem: 297. Serialize and Deserialize Binary Tree

My Submissions

Question

Total Accepted: 7530 Total Submissions: 30326 Difficulty: Medium

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree 1 /
2 3 /
4 5

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Problem: 295. Find Median from Data Stream

My Submissions

Question

Total Accepted: 7854 Total Submissions: 39236 Difficulty: Hard

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] , the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far.

For example: add(1) add(2) findMedian() -> 1.5 add(3) findMedian() -> 2

Problem: 292. Nim Game

My Submissions

Question

Total Accepted: 30328 Total Submissions: 60415 Difficulty: Easy

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:Show Hint If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Problem: 290. Word Pattern

My Submissions

Question

Total Accepted: 19481 Total Submissions: 71462 Difficulty: Easy

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true. pattern = “abba”, str = “dog cat cat fish” should return false. pattern = “aaaa”, str = “dog cat cat dog” should return false. pattern = “abba”, str = “dog dog dog dog” should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Problem: 289. Game of Life

My Submissions

Question

Total Accepted: 9517 Total Submissions: 29341 Difficulty: Medium

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells. In thisQuestion, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Problem: 287. Find the Duplicate Number

My Submissions

Question

Total Accepted: 15311 Total Submissions: 42020 Difficulty: Hard

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

Problem: 284. Peeking Iterator

My Submissions

Question

Total Accepted: 11542 Total Submissions: 35886 Difficulty: Medium

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:Show Hint Think of “looking ahead”. You want to cache the next element.Show More Hint Is one variable sufficient? Why or why not?Show More Hint Test your design with call order of peek() before next() vs next() before peek().Show More Hint For a clean implementation, check out Google’s guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Problem: 283. Move Zeroes

My Submissions

Question

Total Accepted: 41512 Total Submissions: 97605 Difficulty: Easy

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array. Minimize the total number of operations.

Problem: 282. Expression Add Operators

My Submissions

Question

Total Accepted: 6063 Total Submissions: 27868 Difficulty: Hard

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: “123”, 6 -> [“1+2+3”, “123”] “232”, 8 -> [“23+2”, “2+32”] “105”, 5 -> [“10+5”,”10-5”] “00”, 0 -> [“0+0”, “0-0”, “00”] “3456237490”, 9191 -> []

Problem: 279. Perfect Squares

My Submissions

Question

Total Accepted: 19693 Total Submissions: 65573 Difficulty: Medium

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Problem: 278. First Bad Version

My Submissions

Question

Total Accepted: 24889 Total Submissions: 117499 Difficulty: Easy

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. You should minimize the number of calls to the API.

Problem: 275. H-Index II

My Submissions

Question

Total Accepted: 14628 Total Submissions: 45934 Difficulty: Medium

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:Show Hint Expected runtime complexity is in O(log n) and the input is sorted.

Problem: 274. H-Index

My Submissions

Question

Total Accepted: 20231 Total Submissions: 73712 Difficulty: Medium

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:Show Hint An easy approach is to sort the array first.Show More Hint What are the possible values of h-index?Show More Hint A faster approach is to use extra space.

Problem: 273. Integer to English Words

My Submissions

Question

Total Accepted: 9589 Total Submissions: 55827 Difficulty: Medium

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example, 123 -> “One Hundred Twenty Three” 12345 -> “Twelve Thousand Three Hundred Forty Five” 1234567 -> “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Hint:Show Hint Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.Show More Hint Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.Show More Hint There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

Problem: 268. Missing Number

My Submissions

Question

Total Accepted: 30916 Total Submissions: 81664 Difficulty: Medium

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Problem: 264. Ugly Number II

My Submissions

Question

Total Accepted: 18691 Total Submissions: 74920 Difficulty: Medium

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:Show Hint The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.Show More Hint An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.Show More Hint The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.Show More Hint Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

Problem: 263. Ugly Number

My Submissions

Question

Total Accepted: 34158 Total Submissions: 97889 Difficulty: Easy

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Problem: 260. Single Number III

My Submissions

Question

Total Accepted: 19475 Total Submissions: 47175 Difficulty: Medium

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Problem: 258. Add Digits

My Submissions

Question

Total Accepted: 54338 Total Submissions: 113977 Difficulty: Easy

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up: Could you do it without any loop/recursion in O(1) runtime?

Hint:Show Hint A naive implementation of the above process is trivial. Could you come up with other methods? Show More Hint What are all the possible results?Show More Hint How do they occur, periodically or randomly?Show More Hint You may find this Wikipedia article useful.

Problem: 257. Binary Tree Paths

My Submissions

Question

Total Accepted: 27445 Total Submissions: 108383 Difficulty: Easy

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1 /
2 3
5

All root-to-leaf paths are: [“1->2->5”, “1->3”]

Problem: 242. Valid Anagram

My Submissions

Question

Total Accepted: 46923 Total Submissions: 118869 Difficulty: Easy

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.

Note: You may assume the string contains only lowercase alphabets.

Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?

Problem: 241. Different Ways to Add Parentheses

My Submissions

Question

Total Accepted: 13965 Total Submissions: 44925 Difficulty: Medium

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1 Input: “2-1-1”. ((2-1)-1) = 0 (2-(1-1)) = 2 Output: [0, 2]

Example 2 Input: “23-45” (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10 Output: [-34, -14, -10, -10, 10]

Problem: 240. Search a 2D Matrix II

My Submissions

Question

Total Accepted: 22974 Total Submissions: 72470 Difficulty: Medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

Given target = 5, return true. Given target = 20, return false.

Problem: 239. Sliding Window Maximum

My Submissions

Question

Total Accepted: 18060 Total Submissions: 72025 Difficulty: Hard

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up: Could you solve it in linear time?

Hint:Show Hint How about using a data structure such as deque (double-ended queue)?Show More Hint The queue size need not be the same as the window’s size.Show More Hint Remove redundant elements and the queue should store only elements that need to be considered.

Problem: 238. Product of Array Except Self

My Submissions

Question

Total Accepted: 28049 Total Submissions: 70197 Difficulty: Medium

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Problem: 237. Delete Node in a Linked List

My Submissions

Question

Total Accepted: 51236 Total Submissions: 116806 Difficulty: Easy

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Problem: 236. Lowest Common Ancestor of a Binary Tree

My Submissions

Question

Total Accepted: 27356 Total Submissions: 98473 Difficulty: Medium

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

__3___ /
___5 _1 / \ /
6 _2 0 8 /
7 4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Problem: 235. Lowest Common Ancestor of a Binary Search Tree

My Submissions

Question

Total Accepted: 43975 Total Submissions: 116065 Difficulty: Easy

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

__6___ /
___2 _8 / \ /
0 _4 7 9 /
3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Problem: 234. Palindrome Linked List

My Submissions

Question

Total Accepted: 31382 Total Submissions: 122565 Difficulty: Easy

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

Problem: 233. Number of Digit One

My Submissions

Question

Total Accepted: 13805 Total Submissions: 60241 Difficulty: Medium

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:Show Hint Beware of overflow.

Problem: 232. Implement Queue using Stacks

My Submissions

Question

Total Accepted: 27978 Total Submissions: 82738 Difficulty: Easy

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.

pop() – Removes the element from in front of queue.

peek() – Get the front element.

empty() – Return whether the queue is empty.

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Problem: 231. Power of Two

My Submissions

Question

Total Accepted: 45268 Total Submissions: 134853 Difficulty: Easy

Given an integer, write a function to determine if it is a power of two.

Problem: 230. Kth Smallest Element in a BST

My Submissions

Question

Total Accepted: 29466 Total Submissions: 85524 Difficulty: Medium

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:Show Hint Try to utilize the property of a BST.Show More Hint What if you could modify the BST node’s structure?Show More Hint The optimal runtime complexity is O(height of BST).

Problem: 229. Majority Element II

My Submissions

Question

Total Accepted: 19020 Total Submissions: 77657 Difficulty: Medium

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:Show Hint How many majority elements could it possibly have?Show More Hint Do you have a better hint? Suggest it!

Problem: 228. Summary Ranges

My Submissions

Question

Total Accepted: 31322 Total Submissions: 142888 Difficulty: Easy

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2”,”4->5”,”7”].

Problem: 227. Basic Calculator II

My Submissions

Question

Total Accepted: 15045 Total Submissions: 66827 Difficulty: Medium

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples: “3+2*2” = 7 “ 3/2 “ = 1 “ 3+5 / 2 “ = 5

Note: Do not use the eval built-in library function.

Problem: 226. Invert Binary Tree

My Submissions

Question

Total Accepted: 57803 Total Submissions: 136421 Difficulty: Easy

Invert a binary tree. 4 /
2 7 / \ /
1 3 6 9

to 4 /
7 2 / \ /
9 6 3 1

Trivia: This problem was inspired by this original tweet by Max Howell: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Problem: 225. Implement Stack using Queues

My Submissions

Question

Total Accepted: 26398 Total Submissions: 87140 Difficulty: Easy

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.

pop() – Removes the element on top of the stack.

top() – Get the top element.

empty() – Return whether the stack is empty.

Notes:

You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11): The class name of the Java function had been updated to MyStack instead of Stack.

Problem: 224. Basic Calculator

My Submissions

Question

Total Accepted: 19378 Total Submissions: 97811 Difficulty: Medium

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples: “1 + 1” = 2 “ 2-1 + 2 “ = 3 “(1+(4+5+2)-3)+(6+8)” = 23

Note: Do not use the eval built-in library function.

Problem: 223. Rectangle Area

My Submissions

Question

Total Accepted: 26100 Total Submissions: 92168 Difficulty: Easy

Find the total area covered by two rectilinear rectangles in a 2D plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Problem: 222. Count Complete Tree Nodes

My Submissions

Question

Total Accepted: 23327 Total Submissions: 100230 Difficulty: Medium

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Problem: 221. Maximal Square

My Submissions

Question

Total Accepted: 20391 Total Submissions: 92772 Difficulty: Medium

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

For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

Return 4.

Problem: 220. Contains Duplicate III

My Submissions

Question

Total Accepted: 19439 Total Submissions: 110495 Difficulty: Medium

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Problem: 219. Contains Duplicate II

My Submissions

Question

Total Accepted: 38863 Total Submissions: 137975 Difficulty: Easy

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Problem: 218. The Skyline Problem

My Submissions

Question

Total Accepted: 11521 Total Submissions: 57930 Difficulty: Hard

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000]. The input list is already sorted in ascending order by the left x position Li. The output list must be sorted by the x position. There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

Problem: 216. Combination Sum III

My Submissions

Question

Total Accepted: 20718 Total Submissions: 63057 Difficulty: Medium

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Ensure that numbers within the set are sorted in ascending order.

Example 1: Input: k = 3, n = 7 Output: [[1,2,4]]

Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]

Problem: 215. Kth Largest Element in an Array

My Submissions

Question

Total Accepted: 33665 Total Submissions: 111849 Difficulty: Medium

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.

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

Problem: 214. Shortest Palindrome

My Submissions

Question

Total Accepted: 14133 Total Submissions: 77009 Difficulty: Hard

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example: Given “aacecaaa”, return “aaacecaaa”. Given “abcd”, return “dcbabcd”.

Problem: 213. House Robber II

My Submissions

Question

Total Accepted: 18737 Total Submissions: 64882 Difficulty: Medium

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Problem: 212. Word Search II

My Submissions

Question

Total Accepted: 12853 Total Submissions: 74996 Difficulty: Hard

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example, Given words = [“oath”,”pea”,”eat”,”rain”] and board = [ [‘o’,’a’,’a’,’n’], [‘e’,’t’,’a’,’e’], [‘i’,’h’,’k’,’r’], [‘i’,’f’,’l’,’v’] ]

Return [“eat”,”oath”].

Note: You may assume that all inputs are consist of lowercase letters a-z.

click to show hint.

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words’ prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

Problem: 211. Add and Search Word - Data structure design

My Submissions

Question

Total Accepted: 16539 Total Submissions: 81964 Difficulty: Medium

Design a data structure that supports the following two operations:

void addWord(word) bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example: addWord(“bad”) addWord(“dad”) addWord(“mad”) search(“pad”) -> false search(“bad”) -> true search(“.ad”) -> true search(“b..”) -> true

Note: You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Problem: 210. Course Schedule II

My Submissions

Question

Total Accepted: 17366 Total Submissions: 84553 Difficulty: Medium

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. Topological sort could also be done via BFS.

Problem: 209. Minimum Size Subarray Sum

My Submissions

Question

Total Accepted: 26261 Total Submissions: 103788 Difficulty: Medium

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Problem: 208. Implement Trie (Prefix Tree)

My Submissions

Question

Total Accepted: 24480 Total Submissions: 98376 Difficulty: Medium

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

Problem: 207. Course Schedule

My Submissions

Question

Total Accepted: 26698 Total Submissions: 108185 Difficulty: Medium

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. Topological sort could also be done via BFS.

Problem: 206. Reverse Linked List

My Submissions

Question

Total Accepted: 69193 Total Submissions: 188901 Difficulty: Easy

Reverse a singly linked list.

click to show more hints.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Problem: 205. Isomorphic Strings

My Submissions

Question

Total Accepted: 40005 Total Submissions: 145228 Difficulty: Easy

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.

Note: You may assume both s and t have the same length.

Problem: 204. Count Primes

My Submissions

Question

Total Accepted: 45100 Total Submissions: 201155 Difficulty: Easy

Description: Count the number of prime numbers less than a non-negative number, n.

“Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0.

We start off with a table of n numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well? Show More Hint 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, … can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off? Show More Hint In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, … Now what should be the terminating loop condition? Show More Hint It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3? Show More Hint Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.

The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } // Loop’s ending condition is i * i < n instead of i < sqrt(n) // to avoid repeatedly calling an expensive function sqrt(). for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; }

Problem: 203. Remove Linked List Elements

My Submissions

Question

Total Accepted: 44984 Total Submissions: 166033 Difficulty: Easy

Remove all elements from a linked list of integers that have value val.

Example Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5

Problem: 202. Happy Number

My Submissions

Question

Total Accepted: 47053 Total Submissions: 135383 Difficulty: Easy

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

Problem: 201. Bitwise AND of Numbers Range

My Submissions

Question

Total Accepted: 25678 Total Submissions: 90848 Difficulty: Medium

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Problem: 200. Number of Islands

My Submissions

Question

Total Accepted: 29814 Total Submissions: 117349 Difficulty: Medium

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1: 11110110101100000000 Answer: 1 Example 2: 11000110000010000011 Answer: 3

Problem: 199. Binary Tree Right Side View

My Submissions

Question

Total Accepted: 29569 Total Submissions: 94028 Difficulty: Medium

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree, 1 <— /
2 3 <— \
5 4 <—

You should return [1, 3, 4].

Problem: 198. House Robber

My Submissions

Question

Total Accepted: 47046 Total Submissions: 145636 Difficulty: Easy

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Problem: 191. Number of 1 Bits

My Submissions

Question

Total Accepted: 66617 Total Submissions: 176245 Difficulty: Easy

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

Problem: 190. Reverse Bits

My Submissions

Question

Total Accepted: 47206 Total Submissions: 161853 Difficulty: Easy

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up: If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Problem: 189. Rotate Array

My Submissions

Question

Total Accepted: 54521 Total Submissions: 276250 Difficulty: Easy

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].

Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint] Hint: Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

Problem: 188. Best Time to Buy and Sell Stock IV

My Submissions

Question

Total Accepted: 19344 Total Submissions: 94060 Difficulty: Hard

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 at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Problem: 187. Repeated DNA Sequences

My Submissions

Question

Total Accepted: 33198 Total Submissions: 145022 Difficulty: Medium

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example, Given s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”,

Return: [“AAAAACCCCC”, “CCCCCAAAAA”].

Problem: 179. Largest Number

My Submissions

Question

Total Accepted: 36078 Total Submissions: 204947 Difficulty: Medium

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Problem: 174. Dungeon Game

My Submissions

Question

Total Accepted: 19586 Total Submissions: 99830 Difficulty: Hard

table.dungeon, .dungeon th, .dungeon td { border:3px solid black; }

.dungeon th, .dungeon td { text-align: center; height: 70px; width: 70px; }

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3 -5 -10 1 10 30 -5 (P)

Notes:

The knight’s health has no upper bound. Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Problem: 173. Binary Search Tree Iterator

My Submissions

Question

Total Accepted: 35658 Total Submissions: 111070 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.

Problem: 172. Factorial Trailing Zeroes

My Submissions

Question

Total Accepted: 45525 Total Submissions: 147024 Difficulty: Easy

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Problem: 171. Excel Sheet Column Number

My Submissions

Question

Total Accepted: 57221 Total Submissions: 145777 Difficulty: Easy

Related toQuestion Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number.

For example: A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28

Problem: 169. Majority Element

My Submissions

Question

Total Accepted: 82351 Total Submissions: 213129 Difficulty: Easy

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Problem: 168. Excel Sheet Column Title

My Submissions

Question

Total Accepted: 46707 Total Submissions: 232891 Difficulty: Easy

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

Problem: 166. Fraction to Recurring Decimal

My Submissions

Question

Total Accepted: 23815 Total Submissions: 168605 Difficulty: Medium

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”. Given numerator = 2, denominator = 1, return “2”. Given numerator = 2, denominator = 3, return “0.(6)”.

Problem: 165. Compare Version Numbers

My Submissions

Question

Total Accepted: 40630 Total Submissions: 248167 Difficulty: Easy

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

Problem: 0.1 < 1.1 < 1.2 < 13.37

Problem: 164. Maximum Gap

My Submissions

Question

Total Accepted: 26471 Total Submissions: 103348 Difficulty: Hard

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Problem: 162. Find Peak Element

My Submissions

Question

Total Accepted: 50677 Total Submissions: 155681 Difficulty: Medium

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note: Your solution should be in logarithmic complexity.

Problem: 160. Intersection of Two Linked Lists

My Submissions

Question

Total Accepted: 55413 Total Submissions: 186020 Difficulty: Easy

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory.

Problem: 155. Min Stack

My Submissions

Question

Total Accepted: 55336 Total Submissions: 263295 Difficulty: Easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.

pop() – Removes the element on top of the stack.

top() – Get the top element.

getMin() – Retrieve the minimum element in the stack.

Problem: 154. Find Minimum in Rotated Sorted Array II

My Submissions

Question

Total Accepted: 42397 Total Submissions: 127545 Difficulty: Hard

Follow up for “Find Minimum in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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).

Find the minimum element.

The array may contain duplicates.

Problem: 153. Find Minimum in Rotated Sorted Array

My Submissions

Question

Total Accepted: 73048 Total Submissions: 209952 Difficulty: Medium

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).

Find the minimum element.

You may assume no duplicate exists in the array.

Problem: 152. Maximum Product Subarray

My Submissions

Question

Total Accepted: 47761 Total Submissions: 228120 Difficulty: Medium

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

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Problem: 151. Reverse Words in a String

My Submissions

Question

Total Accepted: 85542 Total Submissions: 553501 Difficulty: Medium

Given an input string, reverse the string word by word.

For example, Given s = “the sky is blue”, return “blue is sky the”.

Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

What constitutes a word? A sequence of non-space characters constitutes a word. Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. How about multiple spaces between two words? Reduce them to a single space in the reversed string.

Problem: 150. Evaluate Reverse Polish Notation

My Submissions

Question

Total Accepted: 56518 Total Submissions: 251737 Difficulty: Medium

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: [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9 [“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

Problem: 149. Max Points on a Line

My Submissions

Question

Total Accepted: 50407 Total Submissions: 367938 Difficulty: Hard

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Problem: 148. Sort List

My Submissions

Question

Total Accepted: 60460 Total Submissions: 256339 Difficulty: Medium

Sort a linked list in O(n log n) time using constant space complexity.

Problem: 147. Insertion Sort List

My Submissions

Question

Total Accepted: 60397 Total Submissions: 215434 Difficulty: Medium

Sort a linked list using insertion sort.

Problem: 146. LRU Cache

My Submissions

Question

Total Accepted: 58523 Total Submissions: 376625 Difficulty: Hard

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.

Problem: 145. Binary Tree Postorder Traversal

My Submissions

Question

Total Accepted: 83672 Total Submissions: 246042 Difficulty: Hard

Given a binary tree, return the postorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3}, 1
2 / 3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Problem: 144. Binary Tree Preorder Traversal

My Submissions

Question

Total Accepted: 99709 Total Submissions: 261865 Difficulty: Medium

Given a binary tree, return the preorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3}, 1
2 / 3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Problem: 143. Reorder List

My Submissions

Question

Total Accepted: 55796 Total Submissions: 255129 Difficulty: Medium

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

Problem: 142. Linked List Cycle II

My Submissions

Question

Total Accepted: 62892 Total Submissions: 199906 Difficulty: Medium

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

Problem: 141. Linked List Cycle

My Submissions

Question

Total Accepted: 86861 Total Submissions: 236871 Difficulty: Medium

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

Problem: 140. Word Break II

My Submissions

Question

Total Accepted: 47520 Total Submissions: 254211 Difficulty: Hard

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

Problem: 139. Word Break

My Submissions

Question

Total Accepted: 73009 Total Submissions: 304807 Difficulty: Medium

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = “leetcode”, dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

Problem: 138. Copy List with Random Pointer

My Submissions

Question

Total Accepted: 54785 Total Submissions: 212553 Difficulty: Hard

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Problem: 137. Single Number II

My Submissions

Question

Total Accepted: 70448 Total Submissions: 194082 Difficulty: Medium

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Problem: 136. Single Number

My Submissions

Question

Total Accepted: 105436 Total Submissions: 221275 Difficulty: Medium

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Problem: 135. Candy

My Submissions

Question

Total Accepted: 45921 Total Submissions: 212626 Difficulty: Hard

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Problem: 134. Gas Station

My Submissions

Question

Total Accepted: 53141 Total Submissions: 200435 Difficulty: Medium

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

Problem: 133. Clone Graph

My Submissions

Question

Total Accepted: 55418 Total Submissions: 225790 Difficulty: Medium

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following: 1 /
/
0 — 2 /
_/

Problem: 132. Palindrome Partitioning II

My Submissions

Question

Total Accepted: 43778 Total Submissions: 209736 Difficulty: Hard

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”, Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

Problem: 131. Palindrome Partitioning

My Submissions

Question

Total Accepted: 55055 Total Submissions: 201180 Difficulty: Medium

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,

Return [ [“aa”,”b”], [“a”,”a”,”b”] ]

Problem: 130. Surrounded Regions

My Submissions

Question

Total Accepted: 44187 Total Submissions: 286985 Difficulty: Medium

Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example, X X X X X O O X X X O X X O X X

After running your function, the board should be: X X X X X X X X X X X X X O X X

Problem: 129. Sum Root to Leaf Numbers

My Submissions

Question

Total Accepted: 64392 Total Submissions: 205001 Difficulty: Medium

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example, 1 /
2 3

The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Problem: 128. Longest Consecutive Sequence

My Submissions

Question

Total Accepted: 55596 Total Submissions: 180441 Difficulty: Hard

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Problem: 127. Word Ladder

My Submissions

Question

Total Accepted: 62065 Total Submissions: 318165 Difficulty: Medium

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time Each intermediate word must exist in the word list

For example,

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Note:

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

Problem: 126. Word Ladder II

My Submissions

Question

Total Accepted: 36587 Total Submissions: 272519 Difficulty: Hard

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each intermediate word must exist in the word list

For example,

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Return [ [“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”] ]

Note:

All words have the same length. All words contain only lowercase alphabetic characters.

Problem: 125. Valid Palindrome

My Submissions

Question

Total Accepted: 81055 Total Submissions: 354521 Difficulty: Easy

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not a palindrome.

Note: Have you consider that the string might be empty? This is a goodQuestion to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Problem: 124. Binary Tree Maximum Path Sum

My Submissions

Question

Total Accepted: 55573 Total Submissions: 248026 Difficulty: Hard

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example: Given the below binary tree, 1 /
2 3

Return 6.

Problem: 123. Best Time to Buy and Sell Stock III

My Submissions

Question

Total Accepted: 48064 Total Submissions: 191039 Difficulty: Hard

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 at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Problem: 122. Best Time to Buy and Sell Stock II

My Submissions

Question

Total Accepted: 71250 Total Submissions: 175947 Difficulty: Medium

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).

Problem: 121. Best Time to Buy and Sell Stock

My Submissions

Question

Total Accepted: 78935 Total Submissions: 228622 Difficulty: Medium

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.

Problem: 120. Triangle

My Submissions

Question

Total Accepted: 58194 Total Submissions: 202376 Difficulty: Medium

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Problem: 119. Pascal’s Triangle II

My Submissions

Question

Total Accepted: 61324 Total Submissions: 199368 Difficulty: Easy

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?

Problem: 118. Pascal’s Triangle

My Submissions

Question

Total Accepted: 67930 Total Submissions: 214463 Difficulty: Easy

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

For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Problem: 117. Populating Next Right Pointers in Each Node II

My Submissions

Question

Total Accepted: 52005 Total Submissions: 160574 Difficulty: Hard

Follow up for problem “Populating Next Right Pointers in Each Node”. What if the given tree could be any binary tree? Would your previous solution still work?

Note: You may only use constant extra space.

For example, Given the following binary tree, 1 /
2 3 / \
4 5 7

After calling your function, the tree should look like: 1 -> NULL /
2 -> 3 -> NULL / \
4-> 5 -> 7 -> NULL

Problem: 116. Populating Next Right Pointers in Each Node

My Submissions

Question

Total Accepted: 73365 Total Submissions: 201903 Difficulty: Medium

Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example, Given the following perfect binary tree, 1 /
2 3 / \ /
4 5 6 7

After calling your function, the tree should look like: 1 -> NULL /
2 -> 3 -> NULL / \ /
4->5->6->7 -> NULL

Problem: 115. Distinct Subsequences

My Submissions

Question

Total Accepted: 44627 Total Submissions: 160577 Difficulty: Hard

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example: S = “rabbbit”, T = “rabbit”

Return 3.

Problem: 114. Flatten Binary Tree to Linked List

My Submissions

Question

Total Accepted: 68944 Total Submissions: 231042 Difficulty: Medium

Given a binary tree, flatten it to a linked list in-place.

For example, Given 1 /
2 5 / \
3 4 6

The flattened tree should look like: 1
2
3
4
5
6

click to show hints.

Hints: If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

Problem: 113. Path Sum II

My Submissions

Question

Total Accepted: 66380 Total Submissions: 243085 Difficulty: Medium

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example: Given the below binary tree and sum = 22, 5 /
4 8 / /
11 13 4 / \ /
7 2 5 1

return [ [5,4,11,2], [5,8,4,5] ]

Problem: 112. Path Sum

My Submissions

Question

Total Accepted: 83136 Total Submissions: 273272 Difficulty: Easy

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, 5 /
4 8 / /
11 13 4 / \
7 2 1

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

Problem: 111. Minimum Depth of Binary Tree

My Submissions

Question

Total Accepted: 85565 Total Submissions: 287370 Difficulty: Easy

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.

Problem: 110. Balanced Binary Tree

My Submissions

Question

Total Accepted: 88143 Total Submissions: 268079 Difficulty: Easy

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.

Problem: 109. Convert Sorted List to Binary Search Tree

My Submissions

Question

Total Accepted: 58937 Total Submissions: 201880 Difficulty: Medium

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Problem: 108. Convert Sorted Array to Binary Search Tree

My Submissions

Question

Total Accepted: 62403 Total Submissions: 175306 Difficulty: Medium

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

Problem: 107. Binary Tree Level Order Traversal II

My Submissions

Question

Total Accepted: 64115 Total Submissions: 197960 Difficulty: Easy

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,#,#,15,7}, 3 /
9 20 /
15 7

return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 106. Construct Binary Tree from Inorder and Postorder Traversal

My Submissions

Question

Total Accepted: 45989 Total Submissions: 164834 Difficulty: Medium

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Problem: 105. Construct Binary Tree from Preorder and Inorder Traversal

My Submissions

Question

Total Accepted: 51797 Total Submissions: 189711 Difficulty: Medium

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Problem: 104. Maximum Depth of Binary Tree

My Submissions

Question

Total Accepted: 109748 Total Submissions: 235519 Difficulty: Easy

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.

Problem: 103. Binary Tree Zigzag Level Order Traversal

My Submissions

Question

Total Accepted: 49723 Total Submissions: 181668 Difficulty: Medium

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7}, 3 /
9 20 /
15 7

return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 102. Binary Tree Level Order Traversal

My Submissions

Question

Total Accepted: 81076 Total Submissions: 263116 Difficulty: Easy

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

For example: Given binary tree {3,9,20,#,#,15,7}, 3 /
9 20 /
15 7

return its level order traversal as: [ [3], [9,20], [15,7] ]

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 101. Symmetric Tree

My Submissions

Question

Total Accepted: 86236 Total Submissions: 263548 Difficulty: Easy

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

For example, this binary tree is symmetric: 1 /
2 2 / \ /
3 4 4 3

But the following is not: 1 /
2 2 \
3 3

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

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 100. Same Tree

My Submissions

Question

Total Accepted: 100282 Total Submissions: 236933 Difficulty: Easy

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

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

Problem: 99. Recover Binary Search Tree

My Submissions

Question

Total Accepted: 45197 Total Submissions: 178085 Difficulty: Hard

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 98. Validate Binary Search Tree

My Submissions

Question

Total Accepted: 74367 Total Submissions: 364561 Difficulty: Medium

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 97. Interleaving String

My Submissions

Question

Total Accepted: 42998 Total Submissions: 198273 Difficulty: Hard

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = “aabcc”, s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.

Problem: 96. Unique Binary Search Trees

My Submissions

Question

Total Accepted: 70207 Total Submissions: 193218 Difficulty: Medium

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example, Given n = 3, there are a total of 5 unique BST’s.

1 3 3 2 1 \ / / / \
3 2 1 1 3 2 / / \
2 1 2 3

Problem: 95. Unique Binary Search Trees II

My Submissions

Question

Total Accepted: 46182 Total Submissions: 160086 Difficulty: Medium

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example, Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1 \ / / / \
3 2 1 1 3 2 / / \
2 1 2 3

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 94. Binary Tree Inorder Traversal

My Submissions

Question

Total Accepted: 101066 Total Submissions: 266224 Difficulty: Medium

Given a binary tree, return the inorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3}, 1
2 / 3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 /
2 3 / 4
5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

Problem: 93. Restore IP Addresses

My Submissions

Question

Total Accepted: 47215 Total Submissions: 212678 Difficulty: Medium

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

Problem: 92. Reverse Linked List II

My Submissions

Question

Total Accepted: 59325 Total Submissions: 221721 Difficulty: Medium

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Problem: 91. Decode Ways

My Submissions

Question

Total Accepted: 56806 Total Submissions: 337416 Difficulty: Medium

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Problem: 90. Subsets II

My Submissions

Question

Total Accepted: 55740 Total Submissions: 191775 Difficulty: Medium

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.

For example, If nums = [1,2,2], a solution is:

[ [2], [1], [1,2,2], [2,2], [1,2], [] ]

Problem: 89. Gray Code

My Submissions

Question

Total Accepted: 49736 Total Submissions: 143843 Difficulty: Medium

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Problem: 88. Merge Sorted Array

My Submissions

Question

Total Accepted: 80670 Total Submissions: 273585 Difficulty: Easy

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.

Problem: 87. Scramble String

My Submissions

Question

Total Accepted: 40074 Total Submissions: 156611 Difficulty: Hard

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great /
gr eat / \ /
g r e at /
a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat /
rg eat / \ /
r g e at /
a t

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae /
rg tae / \ /
r g ta e /
t a

We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Problem: 86. Partition List

My Submissions

Question

Total Accepted: 54908 Total Submissions: 193537 Difficulty: Medium

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

Problem: 85. Maximal Rectangle

My Submissions

Question

Total Accepted: 36072 Total Submissions: 158365 Difficulty: Hard

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

Problem: 84. Largest Rectangle in Histogram

My Submissions

Question

Total Accepted: 51263 Total Submissions: 219472 Difficulty: Hard

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 height = [2,1,5,6,2,3], return 10.

Problem: 83. Remove Duplicates from Sorted List

My Submissions

Question

Total Accepted: 92554 Total Submissions: 260015 Difficulty: Easy

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.

Problem: 82. Remove Duplicates from Sorted List II

My Submissions

Question

Total Accepted: 60619 Total Submissions: 233969 Difficulty: Medium

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

Problem: 81. Search in Rotated Sorted Array II

My Submissions

Question

Total Accepted: 52613 Total Submissions: 167389 Difficulty: Medium

Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Problem: 80. Remove Duplicates from Sorted Array II

My Submissions

Question

Total Accepted: 61253 Total Submissions: 194438 Difficulty: Medium

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?

For example, Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

Problem: 79. Word Search

My Submissions

Question

Total Accepted: 59916 Total Submissions: 276225 Difficulty: Medium

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example, Given board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ]

word = “ABCCED”, -> returns true, word = “SEE”, -> returns true, word = “ABCB”, -> returns false.

Problem: 78. Subsets

My Submissions

Question

Total Accepted: 76551 Total Submissions: 257851 Difficulty: Medium

Given a set of distinct integers, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

Problem: 77. Combinations

My Submissions

Question

Total Accepted: 62217 Total Submissions: 191115 Difficulty: Medium

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example, If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

Problem: 76. Minimum Window Substring

My Submissions

Question

Total Accepted: 49218 Total Submissions: 245196 Difficulty: Hard

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example, S = “ADOBECODEBANC” T = “ABC”

Minimum window is “BANC”.

Note: If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Problem: 75. Sort Colors

My Submissions

Question

Total Accepted: 80137 Total Submissions: 238370 Difficulty: Medium

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.

click to show follow up.

Follow up: 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, then 1’s and followed by 2’s. Could you come up with an one-pass algorithm using only constant space?

Problem: 74. Search a 2D Matrix

My Submissions

Question

Total Accepted: 64936 Total Submissions: 198493 Difficulty: Medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

Given target = 3, return true.

Problem: 73. Set Matrix Zeroes

My Submissions

Question

Total Accepted: 54719 Total Submissions: 168658 Difficulty: Medium

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?

Problem: 72. Edit Distance

My Submissions

Question

Total Accepted: 49300 Total Submissions: 179018 Difficulty: Hard

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character b) Delete a character c) Replace a character

Problem: 71. Simplify Path

My Submissions

Question

Total Accepted: 42767 Total Submissions: 204272 Difficulty: Medium

Given an absolute path for a file (Unix-style), simplify it.

For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c”

click to show corner cases.

Corner Cases:

Did you consider the case where path = “/../”? In this case, you should return “/”. Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”. In this case, you should ignore redundant slashes and return “/home/foo”.

Problem: 70. Climbing Stairs

My Submissions

Question

Total Accepted: 85779 Total Submissions: 240749 Difficulty: Easy

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?

Problem: 69. Sqrt(x)

My Submissions

Question

Total Accepted: 77413 Total Submissions: 319042 Difficulty: Medium

Implement int sqrt(int x).

Compute and return the square root of x.

Problem: 68. Text Justification

My Submissions

Question

Total Accepted: 28104 Total Submissions: 182282 Difficulty: Hard

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: [ “This is an”, “example of text”, “justification. “ ]

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

click to show corner cases.

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.

Problem: 67. Add Binary

My Submissions

Question

Total Accepted: 67579 Total Submissions: 261265 Difficulty: Easy

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

For example, a = “11” b = “1” Return “100”.

Problem: 66. Plus One

My Submissions

Question

Total Accepted: 78376 Total Submissions: 245469 Difficulty: Easy

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

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

Problem: 65. Valid Number

My Submissions

Question

Total Accepted: 38693 Total Submissions: 327653 Difficulty: Hard

Validate if a given string is numeric.

Some examples: “0” => true “ 0.1 “ => true “abc” => false “1 a” => false “2e10” => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10): The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

Problem: 64. Minimum Path Sum

My Submissions

Question

Total Accepted: 58252 Total Submissions: 173948 Difficulty: Medium

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Problem: 63. Unique Paths II

My Submissions

Question

Total Accepted: 54084 Total Submissions: 188832 Difficulty: Medium

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Problem: 62. Unique Paths

My Submissions

Question

Total Accepted: 71420 Total Submissions: 206001 Difficulty: Medium

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Problem: 61. Rotate List

My Submissions

Question

Total Accepted: 56627 Total Submissions: 255114 Difficulty: Medium

Given a list, rotate the list to the right by k places, where k is non-negative.

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

Problem: 60. Permutation Sequence

My Submissions

Question

Total Accepted: 45260 Total Submissions: 189006 Difficulty: Medium

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

“123” “132” “213” “231” “312” “321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Problem: 59. Spiral Matrix II

My Submissions

Question

Total Accepted: 43796 Total Submissions: 131305 Difficulty: Medium

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example, Given n = 3,

You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

Problem: 58. Length of Last Word

My Submissions

Question

Total Accepted: 76422 Total Submissions: 270685 Difficulty: Easy

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.

For example, Given s = “Hello World”, return 5.

Problem: 57. Insert Interval

My Submissions

Question

Total Accepted: 48710 Total Submissions: 214593 Difficulty: Hard

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].

Problem: 56. Merge Intervals

My Submissions

Question

Total Accepted: 54124 Total Submissions: 226906 Difficulty: Hard

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].

Problem: 55. Jump Game

My Submissions

Question

Total Accepted: 64771 Total Submissions: 235134 Difficulty: Medium

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Problem: 54. Spiral Matrix

My Submissions

Question

Total Accepted: 47844 Total Submissions: 221876 Difficulty: Medium

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

You should return [1,2,3,6,9,8,7,4,5].

Problem: 53. Maximum Subarray

My Submissions

Question

Total Accepted: 89988 Total Submissions: 253206 Difficulty: Medium

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.

click to show more practice.

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.

Problem: 52. N-Queens II

My Submissions

Question

Total Accepted: 38214 Total Submissions: 101277 Difficulty: Hard

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Problem: 51. N-Queens

My Submissions

Question

Total Accepted: 45837 Total Submissions: 174906 Difficulty: Hard

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle: [ [“.Q..”, // Solution 1 “…Q”, “Q…”, “..Q.”],

[”..Q.”, // Solution 2 “Q…”, “…Q”, “.Q..”] ]

Problem: 50. Pow(x, n)

My Submissions

Question

Total Accepted: 75365 Total Submissions: 274109 Difficulty: Medium

Implement pow(x, n).

Problem: 49. Group Anagrams

My Submissions

Question

Total Accepted: 59327 Total Submissions: 231226 Difficulty: Medium

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Return: [ [“ate”, “eat”,”tea”], [“nat”,”tan”], [“bat”] ]

Note:

For the return value, each inner list’s elements must follow the lexicographic order. All inputs will be in lower-case.

Problem: 48. Rotate Image

My Submissions

Question

Total Accepted: 55425 Total Submissions: 166495 Difficulty: Medium

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place?

Problem: 47. Permutations II

My Submissions

Question

Total Accepted: 56596 Total Submissions: 211593 Difficulty: Medium

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

Problem: 46. Permutations

My Submissions

Question

Total Accepted: 79662 Total Submissions: 236000 Difficulty: Medium

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Problem: 45. Jump Game II

My Submissions

Question

Total Accepted: 54862 Total Submissions: 222335 Difficulty: Hard

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Problem: 44. Wildcard Matching

My Submissions

Question

Total Accepted: 46813 Total Submissions: 283901 Difficulty: Hard

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

’?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “”) → true isMatch(“aa”, “a”) → true isMatch(“ab”, “?”) → true isMatch(“aab”, “ca*b”) → false

Problem: 43. Multiply Strings

My Submissions

Question

Total Accepted: 49457 Total Submissions: 223359 Difficulty: Medium

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Problem: 42. Trapping Rain Water

My Submissions

Question

Total Accepted: 55673 Total Submissions: 178934 Difficulty: Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Problem: 41. First Missing Positive

My Submissions

Question

Total Accepted: 54802 Total Submissions: 235755 Difficulty: Hard

Given an unsorted integer array, find the first missing positive integer.

For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Problem: 40. Combination Sum II

My Submissions

Question

Total Accepted: 55521 Total Submissions: 210541 Difficulty: Medium

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]

Problem: 39. Combination Sum

My Submissions

Question

Total Accepted: 73134 Total Submissions: 248652 Difficulty: Medium

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]

Problem: 38. Count and Say

My Submissions

Question

Total Accepted: 65347 Total Submissions: 241359 Difficulty: Easy

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, …

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 sequence.

Note: The sequence of integers will be represented as a string.

Problem: 37. Sudoku Solver

My Submissions

Question

Total Accepted: 42654 Total Submissions: 181171 Difficulty: Hard

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

Problem: 36. Valid Sudoku

My Submissions

Question

Total Accepted: 58518 Total Submissions: 202591 Difficulty: Easy

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Problem: 35. Search Insert Position

My Submissions

Question

Total Accepted: 86385 Total Submissions: 237549 Difficulty: Medium

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.

Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

Problem: 34. Search for a Range

My Submissions

Question

Total Accepted: 67828 Total Submissions: 241190 Difficulty: Medium

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Problem: 33. Search in Rotated Sorted Array

My Submissions

Question

Total Accepted: 83474 Total Submissions: 283927 Difficulty: Hard

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.

Problem: 32. Longest Valid Parentheses

My Submissions

Question

Total Accepted: 52805 Total Submissions: 242469 Difficulty: Hard

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Problem: 31. Next Permutation

My Submissions

Question

Total Accepted: 53919 Total Submissions: 210768 Difficulty: Medium

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

Problem: 30. Substring with Concatenation of All Words

My Submissions

Question

Total Accepted: 46372 Total Submissions: 229931 Difficulty: Hard

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given: s: “barfoothefoobarman” words: [“foo”, “bar”]

You should return the indices: [0,9]. (order does not matter).

Problem: 29. Divide Two Integers

My Submissions

Question

Total Accepted: 55328 Total Submissions: 363090 Difficulty: Medium

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

If it is overflow, return MAX_INT.

Problem: 28. Implement strStr()

My Submissions

Question

Total Accepted: 84084 Total Submissions: 355481 Difficulty: Easy

Implement strStr().

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

Problem: 27. Remove Element

My Submissions

Question

Total Accepted: 92309 Total Submissions: 283931 Difficulty: Easy

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

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

Problem: 26. Remove Duplicates from Sorted Array

My Submissions

Question

Total Accepted: 101227 Total Submissions: 314798 Difficulty: Easy

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 in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Problem: 25. Reverse Nodes in k-Group

My Submissions

Question

Total Accepted: 49568 Total Submissions: 188038 Difficulty: Hard

Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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

Problem: 24. Swap Nodes in Pairs

My Submissions

Question

Total Accepted: 75397 Total Submissions: 223571 Difficulty: Medium

Given a linked list, swap every two adjacent nodes and return its head.

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.

Problem: 23. Merge k Sorted Lists

My Submissions

Question

Total Accepted: 68769 Total Submissions: 310593 Difficulty: Hard

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

Problem: 22. Generate Parentheses

My Submissions

Question

Total Accepted: 71029 Total Submissions: 204881 Difficulty: Medium

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:

”((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Problem: 21. Merge Two Sorted Lists

My Submissions

Question

Total Accepted: 98061 Total Submissions: 289329 Difficulty: Easy

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.

Problem: 20. Valid Parentheses

My Submissions

Question

Total Accepted: 84387 Total Submissions: 302639 Difficulty: Easy

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.

Problem: 19. Remove Nth Node From End of List

My Submissions

Question

Total Accepted: 86466 Total Submissions: 308454 Difficulty: Easy

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

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid. Try to do this in one pass.

Problem: 18. 4Sum

My Submissions

Question

Total Accepted: 57545 Total Submissions: 254350 Difficulty: Medium

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:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d) The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)

Problem: 17. Letter Combinations of a Phone Number

My Submissions

Question

Total Accepted: 63649 Total Submissions: 235333 Difficulty: Medium

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.

Input:Digit string “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

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

Problem: 16. 3Sum Closest

My Submissions

Question

Total Accepted: 61537 Total Submissions: 220576 Difficulty: Medium

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.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Problem: 15. 3Sum

My Submissions

Question

Total Accepted: 91482 Total Submissions: 517003 Difficulty: Medium

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:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is: (-1, 0, 1) (-1, -1, 2)

Problem: 14. Longest Common Prefix

My Submissions

Question

Total Accepted: 78882 Total Submissions: 295159 Difficulty: Easy

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

Problem: 13. Roman to Integer

My Submissions

Question

Total Accepted: 65630 Total Submissions: 178063 Difficulty: Easy

Given a roman numeral, convert it to an integer.

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

Problem: 12. Integer to Roman

My Submissions

Question

Total Accepted: 51173 Total Submissions: 140932 Difficulty: Medium

Given an integer, convert it to a roman numeral.

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

Problem: 11. Container With Most Water

My Submissions

Question

Total Accepted: 62393 Total Submissions: 188326 Difficulty: Medium

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.

Problem: 10. Regular Expression Matching

My Submissions

Question

Total Accepted: 65833 Total Submissions: 309366 Difficulty: Hard

Implement regular expression matching with support for ‘.’ and ‘*’.

’.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a”) → true isMatch(“aa”, “.”) → true isMatch(“ab”, “.”) → true isMatch(“aab”, “ca*b”) → true

Problem: 9. Palindrome Number

My Submissions

Question

Total Accepted: 97306 Total Submissions: 322951 Difficulty: Easy

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

click to show 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.

Problem: 8. String to Integer (atoi)

My Submissions

Question

Total Accepted: 80085 Total Submissions: 610953 Difficulty: Easy

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.

Update (2015-02-10): The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert… click to show requirements for atoi.

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.

Problem: 7. Reverse Integer

My Submissions

Question

Total Accepted: 113664 Total Submissions: 484244 Difficulty: Easy

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some goodQuestions to ask before coding. Bonus points for you if you have already thought through this!

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10): Test cases had been added to test the overflow behavior.

Problem: 6. ZigZag Conversion

My Submissions

Question

Total Accepted: 69154 Total Submissions: 305977 Difficulty: Easy

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) P A H N A P L S I I G Y I R

And then read line by line: “PAHNAPLSIIGYIR”

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

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Problem: 5. Longest Palindromic Substring

My Submissions

Question

Total Accepted: 84866 Total Submissions: 389482 Difficulty: Medium

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Problem: 4. Median of Two Sorted Arrays

My Submissions

Question

Total Accepted: 77417 Total Submissions: 435589 Difficulty: Hard

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)).

Problem: 3. Longest Substring Without Repeating Characters

My Submissions

Question

Total Accepted: 114939 Total Submissions: 546895 Difficulty: Medium

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Problem: 2. Add Two Numbers

My Submissions

Question

Total Accepted: 109472 Total Submissions: 506997 Difficulty: Medium

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

Problem: 1. Two Sum

My Submissions

Question

Total Accepted: 168568 Total Submissions: 843669 Difficulty: Medium

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2